BFS Scheduler Lost Some Charm With Linux 3.11

[phoronix]

Phoronix: BFS Scheduler Lost Some Charm With Linux 3.11

It appears that the out-of-tree BFS scheduler lost some of its charm with the Linux 3.11 kernel release where CFS is now running faster...

http://www.phoronix.com/vr.php?view=MTUwNDI

[lano1106]

BFS is a specialised scheduler

I'm not very familiar the benchmarks used for this demonstration but I'm not surprised. BFS is a specialized scheduler for typical desktop load.

What is a typical load? Just do top on your current desktop. It should have about, 3-5 running processes and about 100 sleeping processes.

CFS is trying very hard to be a very smart scheduler but the cost is complexity. BFS is about 10K lines of code, CFS is possibly 10x this size. BFS is O(n) CFS is O(1).

It is very easy to make BFS look bad, just highlight its weakness which is to have much more running processes or threads than the system has cores. I suspect this is what happens for the Apache benchmark.

CK wanted a simple scheduler that perform best for typical loads.

BFS packager for ArchLinux does benchmark BFS at each major kernel release. His benchmarks includes:

kernel compiling
file compression
video encoding

All of this is of course in an environnment with a controlled number of runnign processes. Last time I checked, for these everyday tasks, BFS still had the edge.

[mark45]

There we go again, Michael, it's not about speed, it's about responsiveness.

I'm on Fedora 20 amd64 and a few days ago my PC started hugely stuttering (the mouse and even the music playing in the background!) while I was finishing copying 11GB of data to a 16GB USB flash drive.
And that's without doing anything in the background and it's got 4GB of RAM & Intel Core i5, I guess the default Linux scheduler is part of this pathetic behaviour.

I'd love to try out BFS to see if it fixes this bug #1 on Linux which has been there for ages, there are even songs about it, not kidding.

So I don't give a flying fuck if BFS is a little slower, responsiveness is what kills the Linux desktop experience.

[mrugiero]

kernel compiling
file compression
video encoding

Is that a typical desktop load? File compression I kind of understand, but I do not think a random desktop user will encode video or compile the kernel too often.

[AnonymousCoward]

Is that a typical desktop load? File compression I kind of understand, but I do not think a random desktop user will encode video or compile the kernel too often.

We talk about arch users here, so yeah. I for example compile kernels quite often and video encoding is also something I do regularly. Although I might stop compiling kernels when 3.12 is in [core], but we'll see.

[lano1106]

Is that a typical desktop load? File compression I kind of understand, but I do not think a random desktop user will encode video or compile the kernel too often.

Correct. What these tests highlights is that with CPU bound processes and with a small number of running processes such as found in typical desktop load, BFS is more efficient due to its simplicity.

The other quality of a scheduler is responsiveness. Honestly, I do not know how this can be measured but by looking at the code, for BFS, I can understand what to expect when a process wakes up from sleeping state and it will be picked up very fast.

With CFS and all its tricks, it is opaque to me what really will happen and I guess not a lot of people can predict easily how CFS behave in regards to responsiveness.

[mrugiero]

We talk about arch users here, so yeah. I for example compile kernels quite often and video encoding is also something I do regularly. Although I might stop compiling kernels when 3.12 is in [core], but we'll see.

No, we talk about a test that you say proves it performs better (or rather, in a more responsive way) in typical desktop loads. I did compile kernels frequently at one time. The same for video transcoding. This doesn't change a bit that this is not quite common, even in most Arch users I know (although I admit I only know one or two; none of them have ever did either of those).

Another user actually pointed out something useful.

[Rallos Zek]

CFS is trying very hard to be a very smart scheduler but the cost is complexity. BFS is about 10K lines of code, CFS is possibly 10x this size. BFS is O(n) CFS is O(1).

CFS is not O(1) .

[lano1106]

CFS is not O(1) .

Ok. O(C) with whatever C value you want. If not please enligth us with your knowledge.

[wargames]

There we go again, Michael, it's not about speed, it's about responsiveness.

I'd love to try out BFS to see if it fixes this bug #1 on Linux which has been there for ages, there are even songs about it, not kidding.

So I don't give a flying fuck if BFS is a little slower, responsiveness is what kills the Linux desktop experience.

It seems you have never tried Windows 7... because AFAIK this affects all operating systems, and it's due to hard disk throughput. Just buy a SSD and see the difference for yourself. It probably could be improved but I guess the kernel devs don't really care since Linus uses a SSD