LWN: Comments on "Still waiting for swap prefetch"

Regressions and progress

Blaisorblade — 2007-10-09T21:57:08+00:00

This Linus quote is also from a couple of years ago, about drivers (when somebody fixed ACPI and broke suspend for most stuff). And he's a maintainer, and he must have this opinion (or the community should replace him).

What matters is "how deep do you need to stack DM" (is it a real problem) and "4k is a default (other choices are kept, so *you* will make the 8k choice, which is mostly worse)".

That is a known problem since years, and Device Mapper can be changed to be non-recursive; see the LWN articles about changes in link-resolution from recursive to iterative to understand what I mean - that's the same stuff. Technically, this is a tail-call optimization to reduce stack depth.

After reading the discussion over Con's community management, and thinking to Reiser4, I think that Linux is not about politics, but about communities, or rather Social Networks of developers and their influence on community filtering they do (that's a lot of academic buzzwords).

That said, it's known that many problem (including VM and I think scheduling) are computationally hard, so whichever solution you choose it has weak points (it's a theorem in some cases - you can prove that for each compressor there is a file the compressor expands). The point is how hard is the regression.

Distributions had to be fixed not to renice X to -10 (as usual for 2.4) when 2.6 came out. A stable kernel cannot require such a big change. I can fix my X startup script (well, working my way through X startup is not fun, even for an experienced Linux developer like me), but the Ubuntu average user cannot (I know tens of such users, switching from Windows because Vista sucks and Linux had Beryl - they are good Physics students).

Bitmap cache

Blaisorblade — 2007-10-09T18:49:43+00:00

I've read time ago a comment from a OLPC developer on exactly this issue. I'm writing a summary of his comments I recall.
Basically, an application can store an uncompressed bitmap in the X server. And Firefox caches all images this way! That's the problem. Probably avoiding the caching would be even faster (due to no swapping).

IMHO (and this is my opinion, I don't recall his one) a reasonable solution would be to extend the X protocol to allow caching compressed images in most reasonable formats (including especially JPEG). Then the X server can keep a cache of most shown decoded images.

Since the JPEG compression ratio is huge, there would be a huge gain from this.

CFS and SD internals, design

mingo — 2007-09-18T09:25:03+00:00

How does this work, and effect fairness? I mean, can you tell a bit more on the difference between SD and CFS in this area? (I'm pretty interested, that's all)

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.

Bloat

jmorris42 — 2007-08-09T02:28:35+00:00

I really hate this notion that a three year old computer should be tossed in the trash as so obsolete there is no use it can be put to. Linux used to be a good way to get good use out of older hardware. Not anymore. Now you need hardware equal to, and prior to Vista shipping greater than, the minimum Windows baseline.

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.

Off by an order of magnitude?

lysse — 2007-08-09T01:51:23+00:00

Quite right. Sorry. Oops.

Still waiting for swap prefetch

xorbe — 2007-08-07T02:33:24+00:00

Even with swap off, kernel can drop the program text, and swap it in from the backing binary on disk -- all without a swap file.

Bloat

happycube — 2007-08-06T20:49:00+00:00

The real problem is with older hardware - it's impossible to get more than 512MB in an i815-based P3, for instance.

Still waiting for swap prefetch

roelofs — 2007-08-03T23:45:39+00:00

xrestop will show you the X memory usage, such as pixmaps.

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

Greg

Still waiting for swap prefetch

bersl2 — 2007-08-03T04:04:56+00:00

"We have more memory, so we can afford to use it more inefficiently."

That's badly worded. It would be more correct to say that memory efficiency has been sacrificed for time efficiency.

RDSL and ignoring feedback

renox — 2007-08-02T08:00:40+00:00

The thing that this complaint show is that a 'fair scheduler' in itself is not good enough for enduser desktop..
If you have an application APP that is important to you, you renice it so it has lots of CPU, fine, but then say that this application sends a lot of work to do for the X server (could be any server really), then there is a kind of 'priority inversion' which happens where APP is slowed down because the X server doesn't have a big enough CPU share..

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?

Still waiting for swap prefetch

renox — 2007-08-02T07:40:26+00:00

My problem with Ocaml is its syntax and its functional mindset: I tried once to learn Ocaml and I disliked the syntax plus the PDF book I used insisted on using functional way to solve everything which is strange as Ocaml is said to support both imperative and functional style, why the book insisted so much on the functional style is beyond me, bleach.

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..

Still waiting for swap prefetch

zlynx — 2007-08-01T16:43:30+00:00

One of these days someone needs to add the amount of CPU X spent per client to xrestop.

Still waiting for swap prefetch

set — 2007-08-01T02:23:31+00:00

xrestop will show you the X memory usage, such as pixmaps.

program speed vs programming language

liljencrantz — 2007-07-31T12:08:25+00:00

Depends on how you define your scope. I've seen situations where people solve the same problem in different languages, and because they have to spend so much time to do _anything_ in a low-level language, they are forced to chose a dumb algorithm, whereas people coding in a high level language can spend more time on the high level logic and can therefore chose a fast algorithm.

Still waiting for swap prefetch

gouyou — 2007-07-30T08:35:02+00:00

We have more memory
Not really take a look at the OLPC or at the new development on the embeded device scene (Nokia N770/N800, OpenMoko) ...

Still waiting for swap prefetch

dlang — 2007-07-29T23:27:50+00:00

but if the system is pulling the pages off of disk while the system is idle, and puts those pages at the end of the LRU list so that they are the first thing thrown away if you need more memory, what does it hurt you to pull them in and never use them?

Bloat

njs — 2007-07-29T21:35:29+00:00

>Perhaps the key developers should be given a $1,500 budget to buy their workstation with

Err... you can get 2GB of memory for < $100 these days. From a glance at dell.com, right now $550 low-end desktops come with 1GB of memory default, and $750 ones with 2GB. There are still real cases where memory is limited (embedded devices, OLPC, people living in non first-world countries, ...), but your scale seems a bit miscalibrated.

RDSL and ignoring feedback

bronson — 2007-07-28T20:41:30+00:00

Sorry, I don't quite understand... are you saying that a 100% fair scheduler actually *is* the best scheduler? If so, then would you have any evidence/research to back this up? I'm genuinely interested.

My uneducated view: in schedulers, as with government and parenting, 100% fairness is unattainable and probably paradoxical. The best policy may or may not be the most fair policy. They're simply disconnected.

Bitmap cache

Los__D — 2007-07-28T14:00:13+00:00

It really depends on the cost of CPU vs. the cost of memory.

For most usage patterns, I agree, but for those that likes to have 30+ tabs open (for some reason), caching the uncompressed bitmap is a _big_ waste.

The question is if the best approach wouldn't be to just forget or limit those caches for that kind of usage. At least the bitmap approach is asking for disk trashing.

Bitmap cache

man_ls — 2007-07-28T13:51:51+00:00

I would never (never EVER) suggest using JPEG for computer graphics

I wouldn't either. My little experiment with JPEG images involved decompressing a JPEG image vs. caching an uncompressed bitmap. Caching images in a lossy format would be ludicrous.

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.

Bitmap cache

Los__D — 2007-07-28T13:38:05+00:00

I would never (never EVER) suggest using JPEG for computer graphics, but caching in PNG would seem smarter than a bitmap, and not really that much slower. Of course, when you only have 3-4 tabs, it wouldn't really matter, but as the count goes up, you can much better afford the CPU than the memory. Plus, the CPU is only when you change, the memory usage is constant.

I'm not completely sure how uncompressed PNG would handle the JPEG's on the page, but I couldn't imagine it getting worse (memory wise) than bitmap, just equal. (I've been known to be naive in my expectations from formats though).

The browser (toolkit?) could of course also do some kind of checking of available memory, and change algorithm from that, but maybe that is an unneeded complexity.

I don't know, maybe it's easiest/simplest and mostly correct to just keep the rendered pages as is in memory, but for some usage patterns, it does become a huge waste of memory.

RDSL and ignoring feedback

jospoortvliet — 2007-07-28T12:35:15+00:00

No, but a 100% fair scheduler is the only way to ensure you won't have
stalls and other problems brought by unfairness. You can't have your cake
and eat it too.

Great article, thanks!

jospoortvliet — 2007-07-28T12:33:17+00:00

Imho this one isn't entirely fair either, but Corbet & me & others are
still fighting this one out, so don't take my word for it.

CFS and SD internals, design

jospoortvliet — 2007-07-28T12:30:59+00:00

Thanx, Ingo, an excellent explanation. I wonder if you could elaborate on
the following you wrote:

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.)

How does this work, and effect fairness? I mean, can you tell a bit more
on the difference between SD and CFS in this area? (I'm pretty
interested, that's all)

RDSL and ignoring feedback

jospoortvliet — 2007-07-28T12:08:36+00:00

I find that hard to believe if we're talking about the same person
complaining. His problem can never be fixed by CFS, unless CFS
automatically would renice his X, or would introduce unfairness some
other way.

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 ;-) )

Still waiting for swap prefetch

roelofs — 2007-07-28T03:43:19+00:00

Really, FF crashes on me about once a week, because although I have 2GB RAM and 6GB of swap, firefox manages to malloc() 4 GB!

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

Great article, thanks!

wruppert — 2007-07-28T02:54:15+00:00

Thanks for explaining both sides of this issue so clearly. I have not been following this and then read the interview about Con leaving kernel dev. I was wondering what the other side of the story was. Great job!

Regressions and progress

zlynx — 2007-07-27T23:37:32+00:00

Linus' statement says regressions are much more important. But that doesn't specify how much more important. And when the benefits of the change build up, they override how important a regression is.

Ingo's scheduler does not work as well as Con's on many 3D applications, like games. That's a regression from Con's work. Ingo's doesn't always schedule games as well as mainline either (Transgaming went to some work to make Cedega share work between processes and sleep enough to fake out the 2.6 scheduler).

If I decide to complain about the regression (which I won't) should Linus hold up merging CFS until Ingo can meet my demand that the new thing work just like the old thing? (Renicing Cedega is just *too* hard! Poor me!)

Another example: I've complained that 4K stacks aren't ready to be the default (stacking enough device mappers crash), but I strongly suspect that the kernel is going to change the default to 4K no matter what I think.

program speed vs programming language

giraffedata — 2007-07-27T23:06:50+00:00

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

We do 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?

Regressions and progress

corbet — 2007-07-27T22:41:16+00:00

Here's a message from Linus from a couple of weeks ago; I had considered it for the quote of the week:

So we don't fix bugs by introducing new problems. That way lies madness, and nobody ever knows if you actually make any real progress at all. Is it two steps forwards, one step back, or one step forward and two steps back? Different people will give different answers.
That's why regressions are _so_ much more important than new bugfixes. Because it's much more important to make slow but _steady_ progress, and have people know things improve (or at least not "deprove"). We don't want any kind of "brownian motion development".

RDSL and ignoring feedback

zlynx — 2007-07-27T22:21:54+00:00

It may technically be a regression for that user, but if a change improves things for more other users than it hurts, I call that progress.

It may be a case of two steps forward, one step back, but still progress and a good thing, not bad news.

explicit pagein

giraffedata — 2007-07-27T22:12:23+00:00

To avoid the manual step (either good morning or good night), I run this in a cron job every hour all day. It doesn't matter that the interactive programs get paged in uselessly several times during the night; even if done right in the middle of updatedb, they just get paged right out again and the cost is insignificant.

I also send messages through some response-time-critical daemons regularly, to "loosen them up." I.e. page in executables, anonymous pages, etc.

Bitmap cache

man_ls — 2007-07-27T21:57:49+00:00

Yeah we do, but does it really cache a bitmap of the page?

I don't know exactly, but I would say it does. Loading a couple of big JPEG files takes quite longer than changing tabs between them.

That would seem a bit silly

Why, exactly? If you have the RAM to spare, it seems to be as good as any other use. I seem to remember some discussion on LWN about Firefox caching even pages in the history.

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.

RDSL and ignoring feedback

corbet — 2007-07-27T21:51:11+00:00

If somebody's workload works on 2.6.N, but fails on 2.6.N+1, it's a regression. It doesn't matter if life is better for a lot of other folks, or whether you call it "fair," it's still a regression. Regressions are bad news. And yes, CFS does do a better job with that sort of workload.

RDSL and ignoring feedback

jospoortvliet — 2007-07-27T21:41:13+00:00

Indeed. Top be honest, I don't get it why he re-stated that. I mean, it's
lovely to try and fix things if they come up, but this was and is
impossible to fix. And I'm sure Ingo won't try to fix it either. If
someone complains X gets not enough CPU (because it gets 1/10th if 10
heavy processes are running), he will tell the person to renice X. Just
like Con did. After all, it's what a fair scheduler does.

Someone complaining about it simply doesn't understand it - a fair
scheduler WILL lead to regressions. No way around it, period. It's unfair
to attack Con on this one, imho, and again - I really don't see how
Corbet can say these things.

BTW not to say Corbet is stupid or anything negatively, I just think he's
wrong here. Or there is something I utterly do NOT understand (and if
that's the case, I hope he can explain).

Off by an order of magnitude?

Los__D — 2007-07-27T14:36:16+00:00

Yeah we do, but does it really cache a bitmap of the page? That would seem a bit silly

Still waiting for swap prefetch

IkeTo — 2007-07-27T12:52:41+00:00

> 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.

Still waiting for swap prefetch

IkeTo — 2007-07-27T12:32:41+00:00

> 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.

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.

Still waiting for swap prefetch

IkeTo — 2007-07-27T11:56:55+00:00

> C and Python are not the only programming
> languages in the world!! You won't believe it, but other
> programming languages have been invented.

> My personal fave at the moment is OCaml. About as fast as C,
> statically typed, no buffer overflows, small memory footprint,
> access to Perl & Python libraries, and loads of native libs.

Two suggestions. Suggestion 1: start lobbying people all around to start using OCaml: universities, companies, etc. If you are successful you have a bunch of people who *know* what it is (currently the people with that characteristics are so few that it doesn't matter). Or choose suggestion 2: start implementing some *real cool* thing in OCaml, making sure that developing the equivalent thing (e.g., with same performance, flexibility, etc) is so expensive that nobody can do *because of a choice of different language*. Then you serve as an example showing others the real benefit of the language.

Before you do so, accept that languages behaving the same way as in C or Python are those who know by those who work on creating applications. Problem is, money talks. If the industry do need C and Python, that's what's university courses teach, that's what's people know, and that's what applications will be written in.

Off by three orders of magnitude!

man_ls — 2007-07-27T06:06:06+00:00

That should read 20672 KB, sorry.