Still waiting for swap prefetch

It is an unfortunate thing when a talented and well-meaning developer runs afoul of the kernel development process and walks away. We cannot afford to lose such people. So it is worth the trouble to try to understand what went wrong.

Problem #1 is that Con chose to work in some of the trickiest parts of the kernel. Swap prefetch is a memory management patch, and those patches always have a long and difficult path into the kernel. It's not just Con who has run into this: Nick Piggin's lockless pagecache patches have been knocking on the door for just as long. The LWN article on Wu Fengguang's adaptive readahead patches appeared at about the same time as the swap prefetch article - and that was after your editor had stared at them for weeks trying to work up the courage to write something. Those patches were only merged earlier this month, and, even then, only after many of the features were stripped out. Memory management is not an area for programmers looking for instant gratification.

There is a reason for this. Device drivers either work or they do not, but the virtual memory subsystem behaves a little differently for every workload which is put to it. Tweaking the heuristics which drive memory management is a difficult process; a change which makes one workload run better can, unpredictably, destroy performance somewhere else. And that "somewhere else" might not surface until some large financial institution somewhere tries to deploy a new kernel release. The core kernel maintainers have seen this sort of thing happen often enough to become quite conservative with memory management changes. Without convincing evidence that the change makes things better (or at least does no harm) in all situations, it will be hard to get a significant change merged.

Ina recent interview Con stated:

The problem is that, as any developer knows, "no bug reports" is not the same as "no bugs." What is needed in a situation like this is not just testimonials from happy desktop users; there also needs to be some sort of sense that the patch has been tried out in a wide variety of situations. The relatively self-selecting nature of Con's testing community (more on this shortly) makes that wider testing harder to achieve.

A patch like swap prefetch will require a certain amount of support from the other developers working in memory management before it can be merged. These developers have, as a whole, not quite been ready to jump onto the prefetch bandwagon. A concern which has been raised a few times is that the morning swap-in problem may well be a sign of a larger issue within the virtual memory subsystem, and that prefetch mostly serves as a way of papering over that problem. And it fails to even paper things completely, since it brings back some pages from swap, but doesn't (and really can't) address file-backed pages which will also have been pushed out. The conclusion that this reasoning leads to is that it would be better to find and fix the real problem rather than hiding it behind prefetch.

The way to address this concern is to try to get a better handle on what workloads are having problems so that the root cause can be addressed. That's why Andrew Morton says:

and why Nick Piggin complains:

There have been a few attempts to characterize workloads which are improved by swap prefetch, but the descriptions tend toward the vague and hard to reproduce. This is not an easy situation to write a simple benchmark for (though Con has tried), so demonstrating the problem is a hard thing to do. Still, if the prefetch proponents are serious about wanting this code in the mainline, they will need to find ways to better communicate information about the problems solved by prefetch to the development community.

Communications with the community have been an occasional problem with Con's patches. Almost uniquely among kernel developers, Con chose to do most of his work on his own mailing list. That has resulted in a self-selected community of users which is nearly uniformly supportive of Con's work, but which, in general, is not participating much in the development of that work. It is rare to see patches posted to the ck-list which were not written by Con himself. The result was the formation of a sort of cheerleading squad which would occasionally spill over onto linux-kernel demanding the merging of Con's patches. This sort of one-way communication was not particularly helpful for anybody involved. It failed to convince developers outside of ck-list, and it failed to make the patches better.

This dynamic became actively harmful when ck-list members (and Con) continued to push for inclusion of patches in the face of real problems. This behavior came to the fore after Con posted the RSDL scheduler. RSDL restarted the whole CPU scheduling discussion and ended up leading to some good work. But some users were reporting real regressions with RSDL and were being told that those regressions were to be expected and would not be fixed. This behavior soured Linus on RSDL and set the stage for Ingo Molnar's CFS scheduler. Some (not all) people are convinced that Con's scheduler was the better design, but refusal to engage with negative feedback doomed the whole exercise. Some of Con's ideas made it into the mainline, but his code did not.

The swap prefetch patches appear to lack any obvious problems; nobody is reporting that prefetch makes things worse. But the ck-list members pushing for its inclusion (often with Con's encouragement) have not been providing the sort of information that the kernel developers want to see. Even so, while a consensus in favor of merging this patch has not formed, there are some important developers who support its inclusion. They include Ingo Molnar and David Miller, who says:

So swap prefetch may yet make it into the mainline - that discussion is not, yet, done. If we are especially lucky, Con will find a way to get back into kernel development, where his talents and user focus are very much in need. But this sort of situation will certainly come up again. Getting major changes into the core kernel is not an easy thing to do, and, arguably, that is how it should be. If the process must make mistakes, they should probably happen on the side of being conservative, even if the occasional result is the exclusion of patches that end up being helpful.

Now I've been programming since magnetic drums were hip so I may be a bit confused here but it seems to me that I can remember a time less than a decade ago when a system didn't need a couple of gigs to run Linux well.

It seems that Linux may still be a little more efficient than Vista on most loads (but not Firefox) but back in the nifty nineties Linux was a _lot_ more efficient than Windows. In short, Linux has been getting worse faster than Windows.

Turn off swap then if you feel that way. I've got no problem with my system swapping out the getty copies which will never be used and instead using the RAM to cache my mail files.

I have a bunch of stuff that includes running programs, program data and files that the CPU has to deal with. I want everything to go as fast a possible so whenever possible if the CPU wants some of that data it should be able to get it as quickly as possible which means it should be in RAM if at all possible. The better the kernel does this, the faster everything will run.

When you get 2GB (I have them), just start Eclipse on a larger project, while Firefox and Thunderbird are running; and watch your memory getting used. And you didn't even start any VM (Xen or VMware)...

Sure, you can write bad code in any language, but in my experience Python is not particularly slower than other script languages. Here is a benchmark that appears to validate that experience: http://www.timestretch.com/FractalBenchmark.html Another one is here: http://acker3.ath.cx/wordpress/archives/7

Lua might be something to look at.

Of course you will always be able to write faster code in C, but this will take you some more time.

Ya had me until you said this. Why stop at C, when it could be written in ASM? And heck, how do you know the assembler will generate fast code, better do it in hex instead.

I would have thought that after all these years that people would learn more about computer science and programming than to troll the "C is always faster than everything else" line.

(Hey, ghc does it, it must be good! :) )

Why stop at C, when it could be written in ASM?

That's not a natural progression. Code compiled from C is often faster than that compiled from assembly language, for the same reason that a computer can land an airplane more smoothly than a human. Even code compiled from C by a naive compiler (e.g. gcc -O0) is unlikely to be slower than code compiled from assembly language. C is that low-level a language.

how do you know the assembler will generate fast code, better do it in hex instead

Wedo know that. The assembler will generate code that is not only the same speed as that generated by the hex editor, but is actually the same code. That's the definition of assembly language.

I would have thought that after all these years that people would learn more about computer science and programming than to troll the "C is always faster than everything else" line.

The only line I saw was, "C is always faster than Python." And it is, isn't it?

Could you elaborate on that? I'm not much of a coder, but it would be interesting to hear what the problem with python is since I have considered playing with it.

In regards to Ubuntu and Redhat, well I bet they are open for improvements to their code though you don't say what apps it is. Your comment lacks facts.

So to be successful, Ocaml would need 2 things:
1) replace the current default syntax with a better one.
There is already an alternative syntax for Ocaml (so apparently I'm not the only one who don't like the default syntax), it's quite better and F# (an Ocaml clone for .Net) 's syntax looks even better.
2) improve tutorials book to teach both imperative style and functional style, without having such blatant bias towards functional style, it has its place but not for everything.

Somehow I doubt that will happen, so Ocaml is bound to stay in the limelight..

... except that even a simple "hello world" seems to take 40 megabytes of memory. It's not about a few cpu cycles that kills you in performance, it's the enormous overhead that even simple programs get....

$ cat hello.py
import time
print "hello, world"
time.sleep(30)

% python hello.py &
[1] 25243
hello, world
$ ps l -C python
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
0  1000 25446  2688  17   0   3844  2256 -      S    pts/0      0:00 python hello.py

% ps ax -o cmd:50,vsz,rss,stime | egrep '[p]ython'
/usr/bin/python -E /usr/sbin/setroubleshootd       808024 12104 Jul06
python /usr/share/system-config-printer/applet.py  232764  6436 Jul06
/usr/bin/python -E /usr/bin/sealert -s             411728 18524 Jul06
python /usr/libexec/revelation-applet --oaf-activa 458328 55056 Jul06
python /usr/lib64/gdesklets/gdesklets-daemon       453980 65768 Jul23
python ./hpssd.py                                  171220  1176 Jul11

...that's 2_536_044 KB VSZ and 159_064 KB RSS, and as you can see I've rebooted gdesklets recently (it was roughly double that, I think).

Plus I'm not running pupplet/yum-updatesd atm. And for instance "revelation-applet" is just a text entry box 95% of the time.

I appreciate that the huge VSZ numbers are (hopefully) mostly unused shared libs. etc. but half a GB is still a lot for the OS to manage for a text box, and 40+MB of RSS for a simple GUI is far from "so much crap".

For comparison my webserver uses two processes with a VSZ of about 12MB each and RSS of about 1MB each, and I'd prefer that to be smaller.

Check the size of a Linux kernel, and you will see that the is a bigger increment (in percent) in 5 years than the memory used by mozilla. We have more memory, so we can afford to use it more inefficiently.

It seems that Linux may still be a little more efficient than Vista on most loads (but not Firefox) but back in the nifty nineties Linux was a _lot_ more efficient than Windows. In short, Linux has been getting worse faster than Windows.

I am not sure if I agree with that. I am writing this on a Dell laptop with a 1GHz CPU and 512MB of memory. It is a pain to use on Windows XP, and I wouldn't dare try to put Vista on it. But latest version of Ubuntu trundles along quite nicely. There are a few applications that struggles; like eclipse; but they struggled 3 years ago too. Tom

And just throwing hardware at the problem doesn't make it go away. Having 2GB of RAM will make it livable but hard drives aren't getting all that much faster. Paging in enough of OO.o and all the libraries it needs to get to mapping the initial window means looking at a throbber almost as long on a hot new monster PC as it does on an older one. Same for all the disc thrashing involved in logon as multi-megabyte blobs of libraries and executables are mapped in to provide what should be small crap like battery indicators and CPU speed monitor widgets in menu bar.

Having more resources is no excuse for sloppy and wasteful practices. And if we want our stuff to be an option for the coming world of smart phones, flash based laptops (without swap) and the embedded world we need to be thinking about getting our act together now.

Your conclusion simply does not follow from Nick Piggin's quite reasonable postulate.

Now I've been programming since magnetic drums were hip so I may be a bit confused here but it seems to me that I can remember a time less than a decade ago when a system didn't need a couple of gigs to run Linux well.

I would say it still does. I'm writing this as we speak from a PIII 700 MHz with 256 MB of RAM and honest Linux runs great. I even use Firefox which tends to eat up 50% of my RAM according to top, but still no complaints. In fact even with Firefox using half my RAM I'm still not even touching swap.

Interestingly enough when I read some of the posts on lkml claiming that they had 1GB of RAM and swap prefetch drastically improved their workload, all I could think is "what on earth are these people running?" Until a couple of months ago my dev-machine at work only had 512 MB of RAM and had all kinds of nasty things like Firefox, beagle, and Lotus Notes running but my swap was rarely used. Conversely on days when I was forced to boot it into Windows XP for one reason or another I couldn't leave an application minimized for more than 10 minutes before Windows decided to swap it out. Waiting 1 minute every time I switch apps on Windows is enough to make me go crazy and be thankful that Linux has a sane swapping algorithm.

That would seem a bit silly

When people complain that "Firefox eats up 2 GB" in a 4 GB machine, it gives the wrong impression. Firefox runs fine on my 128 MB laptop, and memory seldom goes above 80 MB.

But caching in a lossless format such as PNG isn't such a good idea either. An important aspect of caches is that you should store an artifact which you already have, not one you have to generate. If you have to compress a bitmap to PNG before caching it, you are wasting a lot of CPU time just to generate a cache which you might as well never use again.

An example: you download a JPEG image, then uncompress it to show it, and then you compress it to PNG before caching it in memory. Messy.

Geez, what are you doing to the poor thing??

No idea where it is going - admittedly I tend to have about 200 tabs open, but that alone shouldn't be the problem.

OK, that might do it... I have two FF windows containing a total of 9 tabs, and it's been running since early March. Total memory usage (per ps(1)): 197M allocated, 157M resident. (Of course, there's also X11 pixmaps, as was noted in another LWN article a while back. I've forgotten how to check that, but even if FF were the sole X client--which it's not, by far--that's only another 194M allocated and 46M resident.)

Greg

Danke, sir! That's the command I couldn't recall.

Greg

Don't worry, it's still fine, running 2.6.22.1 kernel on old hardware, with a light desktop, xfce4, running lots of little server things, nfs, vnc, streaming, etc, the system using... 90 mB ram, out of 192 mB total. I originally had 512 in it but it never got remotely close to using it so I pulled it out and put back in small sticks I had lying around. Once in a while it uses swap, a tiny bit, but not often.

For full desktop like kde or gnome, 256 is what you need to avoid swapping.

And more for dev work, vmware, heavy graphics, and so on. Just because you put in 2 gig doesn't mean you use it, this box has 2 and it's using 3/4 gig with 50 or so apps open on 8 virtual desktops. But fire up a vmware or vbox install or two and you're getting closer to 2 gigs.

For example, couldn't one create a virtual file called /proc/<pid>/swapin that when written to, fetches all the swapped data for that process back into ram?

The advantage, of course, would be that no existing users would be affected, and the optimal swap prefetch policy could be adjusted according to the application.

The disadvantages are, of course, that (1) few programs will use that interface, since it is too system dependent, (2) few programs will use that interface at the time it matters, since developers usually cannot exactly know when their program will need a lot of memory (who knows that a crazy user create ten thousand bookmarks in his browser and call expand all...), and (3) large program with VM even larger than the available RAM will fail (or cause the whole system to run very slowly) the moment it calls that interface, and most unluckily, it happens only on some small systems that the developer doesn't have access to.

But some users were reporting real regressions with RSDL and were being told that those regressions were to be expected and would not be fixed. This behavior soured Linus on RSDL and set the stage for Ingo Molnar's CFS scheduler. Some (not all) people are convinced that Con's scheduler was the better design, but refusal to engage with negative feedback doomed the whole exercise.

I was following most of that on LKML as it happened, and the way that I saw it was that a guy testing RSDL was reporting the fact that his X server now got 25% CPU instead of 75% as a regression.

Con did respond. He said the scheduler was fair, that was the design, and that he (the tester) could renice X to -10 or -15 if he wished.

I don't see how else Con could respond to that. RSDL was supposed to be fair. Giving X 75% isn't fair. There's just no way to resolve those two things.

That's just the sort of approach which created trouble for SD/RSDL. If people see regressions with their workloads, stamping a "100% certified fair!" label on it will not make them feel better about it. You have to address these problems; if you are unwilling to do so, your code will not make it into the kernel.

CFS is also a "fair" scheduler, but it has not drawn the same sort of complaints - though it will be interesting to see what happens as the testing community gets larger. As I understand it, the CFS brand of "fairness" takes a longer-term view, allowing tasks to get their "fair" share even if they sleep from time to time. That helps to prevent the sort of regressions seen with SD.

The real key, though, is what happens when things go wrong. There will certainly be people reporting scheduler issues over the 2.6.23 cycle. Ingo and the other CFS hackers could certainly dismiss them as "entirely silly," seeing as the scheduler is "completely fair," after all. But they won't do that. Instead, they will do their best to understand and solve the problems. That is why CFS is in the kernel, and SD is not.

Of course it is not unbiased reporting - we pay good money for Jon's opinion. That's what an editorial is. Jon explained quite clearly, and even-handedly in my opinion, why he came to the conclusion he did. Agree with him or not (and I certainly don't always), but criticising his reporting because you don't agree with his conclusions is not helping anyone.

CFS will cause regressions, because it doesn't do unfair scheduling -
which is what users have come to expect. There is no way around it.

Besides, CFS does worse on 3D gaming compared to SD and mainline, and ppl
will complain about that as well.

Note that I'm happy CFS got in mainline, as far as I can tell, it has a
superior design. It's just that the mentioned reasoning for the choice
doesn't work for me...

Maybe this is worth reading, if you didn't already.
http://osnews.com/story.php/18350/Linus-On-CFS-vs.-SD
(don't forget the OTHER SIDE of the story ;-) )

As I understand it, the CFS brand of "fairness" takes a longer-term view, allowing tasks to get their "fair" share even if they sleep from time to time.

Correct, and i call this concept "sleeper fairness".

The simplest way to describe it is via an specific example: on my box if i run glxgears, it uses exactly 50% of CPU time. If i boot into the SD scheduler, and start a CPU hog in parallel to the glxgears task, the two tasks share the CPU: the CPU hog will get ~60% of CPU time, glxgears will get ~40% of CPU time. If i boot CFS, both tasks will get exactly 50% of CPU time.

I've described this mechanism and other internal details in another thread already, but i think it makes sense to paste that reply here too:

wait_runtime is a scheduler-internal metric that shows how much out-of-balance this task's execution history is compared to what execution time it could get on a "perfect, ideal multi-tasking CPU". So if wait_runtime gets negative that means it has spent more time on the CPU than it should have. If wait_runtime gets positive that means it has spent less time than it "should have". CFS sorts tasks in an rbtree with this value as a key and uses this value to choose the next task to run. (with lots of additional details - but this is the raw scheme.) It will pick the task with the largest wait_runtime value. (i.e. the task that is most in need of CPU time.)

This mechanism and implementation is basically not comparable to SD in any way, the two schedulers are so different. Basically the only common thing between them is that both aim to schedule tasks "fairly" - but even the definition of "fairness" is different: SD strictly considers time spent on the CPU and on the runqueue, CFS takes time spent sleeping into account as well. (and hence the approach of "sleep average" and the act of "rewarding" sleepy tasks, which was the main interactivity mechanism of the old scheduler, survives in CFS. Con was fundamentally against sleep-average methods. CFS tried to be a no-tradeoffs replacement for the existing scheduler and the sleeper-fairness method was key to that.)

This (and other) design differences and approaches - not surprisingly - produced two completely different scheduler implementations. Anyone who has tried both schedulers will attest to the fact that they "feel" differently and behave differently as well.

Due to these fundamental design differences the data structures and algorithms are necessarily very different, so there was basically no opportunity to share code (besides the scheduler glue code that was already in sched.c), and there's only 1 line of code in common between CFS and SD (out of thousands of lines of code):

  * This idea comes from the SD scheduler of Con Kolivas:
  */
 static inline void sched_init_granularity(void)
 {
         unsigned int factor = 1 + ilog2(num_online_cpus());

This boot-time "ilog2()" tuning based on the number of CPUs available is a tuning approach i saw in SD and i asked Con whether i could use it in CFS. (to which Con kindly agreed.)

The practical difference is noticeable for something like the X server - Xorg is often a "sleepy" process but it's important that when it runs it gets its own maximum share of CPU time. With a "runners only" fairness model it will receive less CPU time than with a "sleepers considered too" (CFS) fairness model.

The article mentions that Linus and some others feel that SwPr is just papering over a more fundamental problem. So, why not spend time trying to fix the fundamental problem before hacking around it?

That's a rhetorical question... there could be a number of reasons: the root cause is too complex to be understood, or the proper fix is worse than SwPr, etc. I just think that Linus & crew would like to see someone attempt to fix the real problem before resorting to a SwPr hack. If a proper fix is attempted and proves unweildy, then I bet SwPr will jump a lot higher on a number of kernel devs' priority queues.

> ...entirely silly. Complaining about the fairness of a fair scheduler?

They weren't complaining about the fairness, they were complaining about the quality. Is a 100% fair scheduler actually the best scheduler? Probably not.

It's quite difficult to solve.. The only way would be to have some way to transfer the 'CPU token' that APP have to the server it's asking to do some work on its behalf, if it is a multi-threaded server which use a different thread for each client, then maybe the kernel could understand what's happening and boost the corresponding server's thread priority accordingly, but in a non-threaded server, I don't see how it could be solved even if the APP says gives my 'CPU token' to server X, how could the server X would be able to report/understand that currently he is supposed to be working for client APP and not for another client?

My interpretation: there are 3 classes of systems:

1. Those that have loads of memory and very few programs requiring big memory that ever run, and as such never write anything to the swap. Swap prefetch is of course a no-op in such systems.
2. Those that have loads of memory and very few programs requiring big memory that ever run, but still the swap is being written. Swap prefetch improves the performance of such system, but developers would ask, "why the hell did it happen in the first place?"
3. Those that have not such much memory to run all the programs requiring big memory that ever run, and naturally swap prefetch does help, as expected.

So because of the unclear reason that (2) happens, and perhaps because those systems in class (1) might see regressions and need to manually turn off prefetching via a kernel option (never mind that none is currently known after 18 months of testing), those (typically) systems among (3) have to suffer? After all, prefetch is not something that is done only to the swap. A block I/O system without prefetch also have horrible performance, and we have prefetch there for ages. So why swap has to be treated differently? Should we perfectly expect that an application being swapped (for whatever reason) should perform much worse than an application being loaded the first time if prefetching happens when the application is first being loaded and does not happen when the application is pushed to the swap due to uncontrollable memory pressure? Is it such a surprise that swap prefetch is something needed anyway?

And what is the consequence to (2) if swap can be prefetched? It means there is no way to detect such a problem exists? Of course not, the kernel keeps page fault counters, if developers care to write a script and collect the stats of each of the running processes. The only thing that will happen is that people will no longer be so unhappy about the problem, because that doesn't hit their bottom line: enjoying hot coffee while working in the morning. And the end result is, unsurprisingly, less attention to the problem. But... is it really such a bad thing after all, that some hard problem can be put aside because the problem no longer cause serious user dismay?

Perhaps I'm understanding something really wrong.