The cost of Linux's page fault handling
plus.google.com
plus.google.com
Since it's just after a git operation all the file state should be warm in the disk cache. It really shouldn't take that long. The Linux kernel (at least by looking at [1]) is about the same size in terms of file count as Chromium, and we got this operation down to about a second by using better tools (i.e. non-recursive make and then eventually a replacement).
I appreciate that the kernel has its own requirements (it sounds like his no-op builds are still running shell scripts, something you ought to avoid in your critical path) and also it's great that he's running it this way in part to help profile a "normal" workload... but I'm also a bit sad to see so much time spent waiting for something slower than necessary, as well as time spent optimizing what feels like the wrong thing.
[1]: http://larjona.wordpress.com/2011/06/15/numbers-about-the-li...
---
+Peter oh, it's absolutely true that 'make' is a pig, and does too much, and we don't exactly help the situation by using tons of GNU make features and complex variables and various random shell escapes etc etc.
So there's no question that some "makefile compiler" could optimize this all. But quite frankly, I've had my fill of random make replacements. imake, cmake, qmake, they all solve some problem, and they all have their own quirks and idiocies.
So while I'd love for 'make' to be super-efficient, at the same time I'd much rather optimize the kernel to do what make needs really well, and have CPU's that don't take too long either.
Because let's face it, even if the kernel build process was some super-efficient thing, real life isn't that anyway. I guarantee you that the "tons of small scripts etc" that the kernel build does is a real load somewhere totally unrelated. Optimizing page faults will help other loads.
Can you even imagine reading the man pages of all the different git-make commands? The syntax?
I hope Linus keeps contributing to humanity and doing what he's doing. He's obviously a great engineer, and if he works hard, he might undo the wrong of releasing git into the world.
If you are willing to learn what it is that it does, git is actually fairly frigg'n good.
Of course, mayhap I've just not used a better tool.
I've never seen a comment with which I more vehemently disagree.
I am willing to bet money (let's say 0.1 bitcoins) that there are plenty of people at your university who have trouble with Git. We can haggle on terms, but I'd bet that you'd see 10 people at least struggling with git in an intro course.
Once you learn to give it the right incantations, and learn never to deviate from the path you know, any tool can become usable. But it will never be a part of you and will never make you stronger.
This has crippled a generation of developers and I'm afraid it will be a massive barrier to entry, stunting humanity's growth probably by 10-20 years.
See http://homes.cs.washington.edu/~asampson/blog/git.html for a more in-depth treatment of Git's insanity.
It's the same reason so many new display technologies have failed: its not good enough to be better then an LCD eventually. You need to be better now, and better then the LCD which will come about as evolutionary improvements in manufacturing too. Being a little cheaper in the initial plant cost is meaningless if the plant has been built and we understand its processes.
Which of course is why the commentary on Git is absurd: people struggle with Git? People struggled with CVS. People struggle with the notion of "files" and programming in general. The alternative has to both exist, and be easier to use from the get-go. Not just a different set of traps.
At some level, command-line conventions are arbitrary. "ls" could just as easily be "dir" or "list." "revert" could just as easily be "checkout" in some contexts.
UNIX has never been a zero-learning-curve OS. That's OK. There are other operating systems that fill that role. git is a UNIX tool which is intuitive once you learn it.
The world doesn't owe you anything, and if you don't want to learn git, or any aspect of programming, nobody is forcing you to. There are lots of other things to do out there. Some of them even pay more.
The parent quote doesn't deserve to be downvoted but it seems to have been massively downvoted for the same reason a massive number of people use GIT who shouldn't - the bandwagon effect.
Git may well be a perfect tool for the Linux kernel but it's still an opaque nightmare for the many average non-kernel-developers who use it as "the new good version control system" (which it isn't, it's only a tool for a specific purpose made by a famous person).
The poster's point is valid - if Linus created a make replacement for his purposes, the effects of everyone else inappropriately adopting it would be horrific (even if it was indeed, a great make for the kernel and just for the kernel).
This is true as far as it goes, but a silly argument. Let's apply a reversal test (http://www.nickbostrom.com/ethics/statusquo.pdf).
Suppose the kernel build were as efficient as Chrome's is claimed to be on this page (<5s) and wasn't stressing his system. Would Linus then approve of anyone submitting patches to deliberately slow down the Linux kernel build just to show up slownesses in page fault and encourage kernel devs to spend time on optimizing that?
No, of course not! That would be idiocy and the person submitting the patches would probably be banned by Linus in his titanic rage. However, since the slow build & page faults is the status quo, Linus is making lemonade of it...
I don't get what you're arguing against. Even if the kernel were superfast, there's probably another "real load" out there somewhere that legitimately runs into lots of page faults.
Linus is actively arguing against a faster kernel build. It sounds like it makes sense, because it gives him leverage with CPU vendors.
But it doesn't, really. If kernel build were already fast, he would never in a million years slow it down just to get that leverage.
Now maybe he's perfectly aware of this status quo bias, and he's taking advantage of it to meliorate something he would otherwise have no power over. Sneaky.
Still, what's the priority? He's made his point now, hasn't he? He could work on making a faster build process, now.
Anyway he's not saying slowness is better in and of itself, just that there are better places to work on than replacing make.
I'm sure he'd be happy to take patches that make 'make' faster, but that's simply not what he's trying to address here.
"When a proposal to change a certain parameter is thought to have bad overall consequences, consider a change to the same parameter in the opposite direction. If this is also thought to have bad overall consequences..."
How is speeding up kernel build times a "bad overall consequence"? Thats exactly what Linus is trying to do.
However I'm not sure it is directly applicable here. There are two courses of action that could solve this problem:
A, an action that improves kernel builds
B, an action that improves several workloads
For A and B of similar cost, it makes sense to do action B in preference to action A.
Your argument speaks to A being of positive utility, but given a finite knapsack of effort smaller than the set of possible actions that fit in the knapsack, a greedy algorithm that places any positive item into the knapsack is not optimal.
Most people would consider A a more reasonable reaction, especially after hearing that Linus's best idea for doing B is apparently going all the way down to the hardware level in search of some improvement. We can see this by intuitively asking what people's reactions would be to a proposal to induce B if the equilibrium were already at A.
Personally, I don't care much about the speed of the Linux kernel build system, but I do care about the speed with which page faults are handled by the CPU. Even if the chances of success are lower, if he is able to succeed in speeding up every page fault on future Intel processors, I would consider that a much greater good.
The real problem (as I see it) is that I think he's trying to optimize the wrong thing. His worst-case test is based on trying to repeatedly fault in an uncacheable page: every lookup TLB lookup fails at every level of the cache. Likely, Intel has chosen to optimize the real situation where page translations are cached when they are repeatedly accessed.
Improve your dev cycle inefficiency that you don't really mind, or improve your product? What's unreasonable about the latter?
especially after hearing that Linus's best idea for doing B is apparently going all the way down to the hardware level
He's building a kernel, not a webapp. "All the way down" is a single layer.
(I believe the GPs reasoning is that "improve the build system" and "retard the build system" are not symmetrical, because both directions require positive effort to be expended).
B from linus' perspective just means "wait a year for things to automatically get better (after throwing some money at it)" which seems like the low-effort solution.
The suggestion in the comments to allow a Windows-style batched stat is a good idea. This means that more work is done per system call, reducing the number of calls and therefore the amount of time spent saving the CPU state to switch to kernel mode, and then restoring it again to switch back.
(A batched stat would be nice too, but it's not the most critical thing to optimize.)
But yes, the kernel build is doing all sorts of stuff other than stat, like starting shells and sub instances of make.
No they are not. Cutting context switches in system calls is one of the easiest ways of boosting throughput in your average unoptimized Linux app, in my experience. Exactly because so many developers go around ignoring the cost of system calls.
pymake: A mostly GNU-compatible python implementation of `make`.
But seriously mailing lists are pretty archaic, not saying that g+ is great but it's possible to have solid data redundancy and centralization without living in the past.
Basically, unthreaded messages for something like this is just obnoxious. And is pretty much the reason you move discussions to tables when you are at a public place and don't just sit having everyone try and shout at each other.
I imagine the end result is a bit like a performer having their own catchphrases sent to them, in that they're scroll-scroll-scrolled past without exception.
> It's interesting, because the kernel software overhead
>for looking up the page and putting it into the page
>tables is actually much lower. In my worst-case situation
>(admittedly a pretty made up case where we just end up
>mapping the fixed zero-page), those 1050 cycles is
>actually 80.7% of all the CPU time.Haswell: 1050 cycles / 80.7% CPU time on his microbenchmark
Core Duo: 940 cycles / 58% CPU time on his microbenchmark
Also he only used one compiler and would test with another compiler to confirm the results. Just to eliminate a possible compiler quirk in a quick way compared to checking the machine code.
As a side note NUMA autobalancing can be disabled by running:
echo 0 > /proc/sys/kernel /numa_balancing_scan_period_min_ms
echo 0 > /proc/sys/kernel/numa_balancing_scan_period_max_ms
echo 0 > /proc/sys/kernel/numa_balancing_scan_size_mb
echo 1000000 > /proc/sys/kernel/numa_balancing_scan_period_min_ms
numa_balancing=disableThere are some better build systems which will fulfill this requirement, but fail others.
This is why I am implementing buildsome [1], that gives far better guarantees [2] about the build's correctness while making it easier to specify.
Empty builds only check "mtimes" of all files, and no more than that.
[1] https://github.com/ElastiLotem/buildsome
[2] https://github.com/ElastiLotem/buildsome/raw/master/doc/Pres...
If absolutely nothing changed, you wouldn't need to build in the first place.
He's talking about the case of "nothing changed that needs to be built". Configuration files, sources that aren't built on that platform, etc. Which means the build system still needs to traverse directories and figure dependencies out, etc.
Empty build would be same time as git status.
#ifdef win32
...some changes we don't care about on linux
#else
...no changes
#endif
The hard case is changing defined macros in a way that doesn't matter but does pass extra -D flags to the compilation units. You can detect this by ad hoc preprocessor aware logic, or you can have a separate build step for preprocessing and do content aware rebuilds that avoid rebuilding if the preprocessed text is identical.
A) If the headers are supposed to be auto-generated, it will uninformatively fail
B) If everything is successful, it will not tell you about all the paths it depends on not existing.
gcc -M -Ia -Ib foo.c
Will tell you about b/x.h being a dependency, but will not tell you about a/x.h not-existing being a dependency.
B) This makes sense, though I don't necessarily see how that could happen. It won't help you not rerun the -M hit, but the flow is: "rerun -M" on files to get list of dependencies, restart with those dependency list loaded and see what needs to be rebuilt. Right?
B) If you rerun -M every time you try to build, your empty builds are going to be quite expensive. It makes sense to cache that, and only rescan files when they or their #included files changed. But then you need to be able to do the file-inexistence dependency thing or it's wrong.
I see what you are saying with B, but I don't have quite enough experience to know exactly how expensive that is. I also don't know enough about the kernel build to know what it is doing.
Also, I'm curious why the -M flag can't output the inexistance stuff. I guess it would be purely heuristic?
-M could in theory output the inexistence stuff, but then most build systems couldn't even express that dependency.
For that, I would assume you would still have to do that by hand for the header. There may be some autotools thing that covers it. Though.... even then, I'm not sure what the point is. If the header file itself is generated, then you already have the dependency on what it generates from.
The only scenario I think I see as not covered is when there is an include in an #if that flips from not taken to taken. Though, that does seem fairly edge case.
I think I really just need to see an example of the inexistance stuff. In particular, one that is expected to change between non-clean builds.
Problem A:
foo.c: #include "bar_auto.h"
when you have a rule "%_auto.h: %_auto.xml".
gcc -M on foo.c will not tell you about the dependence on "bar_auto.h", but will rather fail. With buildsome or a better #include scanner, you will know that foo.o depends on bar_auto.h, even though bar_auto.h does not yet exist.
Problem B:
x.c: #include "bla.h"
a/bla.h does not exist
b/bla.h does exist
gcc -Ia -Ib -o x.o -c x.c
gcc -M tells us that x.o depends on b/bla.h. We cache this information to avoid rerunning gcc -M every time. Then someone adds a/bla.h. A rebuild will change x.o, but "make" or whatever build system cached the result of "gcc -M" will not rebuild anything.
You might say "gcc -M" should be rerun each time, but this is extremely wasteful, as there's no reason to rescan all the .c/.h files every time, when they did not change.
The TLB is tiny these days, and 4kb pages are tiny.
I'm super hopeful that Linus is going to force through some big improvements to HugePages, because the current Linux HugePages support is super painful at the moment. 2MB pages alone could be a massive gain.
https://www.google.co.uk/search?q="pagesize"+"64k"+"bug"
https://www.google.co.uk/search?q="pagesize"+"64k"+"issue"
Another common one is actually in the kernel where filesystem block sizes are limited to page sizes, so from this point of view large page sizes are better:
4k for a page is ridiculous. I'd say it was ridiculous for something like 5 years ago already
4M may be too big (I'm thinking 512k could be a sweet spot)
(or it could just work in chunks - I believe it does something like that already, and get multiple pages at once)
IIRC Linus was quite dismissive about having larger-than-4k page sizes as the default.
It's probably easier to make something special for small files than making the current system go faster
Probably it's more that iret simply has always been slow (hence why the various syscall/sysenter extensions were created).
https://github.com/jw2013/getvminfo
I use that to see the page fault pattern of both sequential and random memory access pattern. In case anyone is interested, just check it out.
Coming up with a better architecture is easy compared to the challenge of getting people to actually use it.
Another interesting aspect of the Mill architecture is that protection and translation are separate. The cache uses virtual addresses, and the TLB sits between cache and main RAM. The TLB is much bigger and slightly slower, so simply doesn't fault nearly so often.
The next talk will be about configuration, which is another cool topic, and that'll be in a couple of weeks. Get on the mailing list to get details as they become available: http://millcomputing.com/mailing-list/
(I of course welcome any arguments that demonstrate that I overlooked something when claiming all this.)
Caching is supposed to speed things up, so it is kinda silly that the caching system has somehow gone backwards in overall performance.
Pagefaults are a critical path for performance concerns in almost any software system that needs high-performance. If they are 10% slower, then its like the worst case performance of the computer is 10% slower.
Anyone who needs to write high performance code (say, simulations, or game design: http://gameprogrammingpatterns.com/data-locality.html ), is concerned with avoiding pagefaults and cache misses, but the average code (general case?) doesn't concern itself with this as much, so the average program may end up experiencing this more than a linux compile.
It's probably something like hundreds of thousands per second at most, giving you something like a less than 0.5% slowdown. Versus the speedup of 300% for some other code (it's an extreme value actually, but still). Your newer Intel CPU certainly didn't get slower on average code compared to the Core Duo, for the same clock speed.
Nothing to raise the eyebrows here. I believe it's not "in Linus case" but "in every case" that the overall time is shorter.
4th ed: http://amzn.com/0123744938
5th ed: http://amzn.com/0124077269
perf stat <executable>
Shared libraries are also mmap'ed and faulted in, and doing it this way saves memory for things that aren't used. But if paying the penalty for faulting the pages when used outweighs the memory savings, it might be better to use MAP_POPULATE here too. It might worth trying to add an LD_LIBRARY_XXX option to tell the loader to use MAP_POPULATE. Statically linking the executable will also reduce the number of faults (sections are combined, etc.)
The interesting part is that this is used for both invalid memory areas (which cause segfaults) and for virtual memory. The kernel can take memory your process hasn't used in a while, write its contents to disk, and then mark that area "not present." Then it can give that memory to someone else, and load your data back in when you try to access it.
This trick is also used to load in binaries and other files. Instead of reading a program in all at once, the kernel just updates some internal bookkeeping to say "these pages should be from this file" and then lets the page fault handler load them in on demand.
The problem here is that the actual kernel page fault handler is plenty fast, but the hardware mechanisms that set it off and finish it are slow, because of how the CPU is built.
Edit: sorry, I'm totally wrong. Now I am wondering what the case I described is called. It is the event when the page table walker is invoked.
I'd say your original statement is correct, and that the term "page fault" is overloaded. It can be used for both the TLB miss handler and also for loading swapped out data from disk. It's up to context to make it clear.
More fun reading here: https://www.kernel.org/doc/Documentation/x86/exception-table...
Some systems, mainly older RISC designs, trap into the OS when a page translation is not found in the TLB
-- Wikipedia
A software-managed TLB involves switching contexts and executing instructions in a TLB miss handler (the fetching of which could cause cache misses too), then switching back to the instruction that was interrupted. Compare that to just internally dispatching a memory read or two more, and you'll probably see why soft TLBs seem to have fallen out of favour; even if context switches could be done with no overhead, that extra cost of fetching, decoding, and executing instructions can't be recovered. (As that old saying goes, "The fastest way to do something is to not do it at all.")
Looking a bit more into it, MIPS is the most widely-used CPU that still has a "soft TLB". The other popular RISC, ARM, is automatic like x86.
If you measure workforce engagement by the amount of time their knees spend under the desk, you are measuring input, not output.
So if you measure how long it takes for engineers/developers to get feedback, you're really measuring how good their tools are, which is a half-decent proxy for engineer performance.
(Note that it's the same when testing takes a long time, coincidentally, the same company had a long running product and 80 minute test cycle, so everybody was paid to take coffee)
The worst part is that some applications are really hard to make faster, for example, going from "slow now" to "faster tomorrow" might necessitate quite a few changes that will be validated at "slow now" speed, for months. So the whole road to a faster tomorrow will be at pilgrimage pace.
$ perf stat make
...
116,222 page-faults # 0.046 M/sec
...
Just for the sake of thinking YC is not about posing, does anybody understand that actually each of your 4 Ghz core is actually taking 80% of its time at the HW level having page fault because the architecture is this way. It means, less that only 800Mega cycles are actually executed per seconds (or idling). Actual computer do perform as well as a 800MHz computer that would never page fault and are sucking more than 300W/h.
Doesn't this figures seem enormous?
EDIT: it should at least raise some incredulity, and if confirmed some serious questions on how we measure computer performance vs power efficiency.