45 ms·
The cost of Linux's page fault handling
- halayli 13y ago"Computer Organization and Design, Fourth Edition: The Hardware/Software Interface" is an excellent read that complements this article.
- prlin 13y agoQuick google search brings up that it's available here: https://www.u-cursos.cl/usuario/9553d43f5ccbf1cca06cc02562b4005e/mi_blog/r/MK.Computer.Organization.and.Design.4th.Edition.Oct.2011.pdf https://www.u-cursos.cl/usuario/9553d43f5ccbf1cca06cc02562b4...
- rbanffy 13y agoI'd really prefer not to see things like this on HN. Even an old edition is still under copyright.
- gknoy 13y agoAgreed. Anyone who prefers to buy it can do it via e.g. Amazon: 4th ed: http://amzn.com/0123744938 http://amzn.com/0123744938 5th ed: http://amzn.com/0124077269 http://amzn.com/0124077269
- biehl 13y agoI wonder how many NH readers would benefit from reading in that book (a lot I guess) and also how many have no immediate access or consider the asked price unreasonable (probably fewer, but still many).
- zokier 13y agoI would benefit from many things for which I consider the asked price to be unreasonable. I still do not expect to get them for free.
- biehl 12y agoAnd yet, how many of those things have a fixed monopoly prices, disconnected from marginal costs, that has been set to fit a market with consumers with a completely different median income than yours? Are you in a third world country eg.?
- gue5t 13y agoWhat happened to the Hacker Ethic? "Access to computers--and anything which might teach you something about the way the world works--should be unlimited and total." and "All information should be free."
- zokier 13y agoNothing "happened". Using "hacker ethic" as an excuse for piratism has always been stupid. That is why Stallman began writing GNU instead distributing illegitimate copies of UNIX.
- prlin 13y agoYou make a good point. I was just hoping to lower the boundary between people thinking about reading more, and actually going to read more.
- nraynaud 13y agoI coined the term "applications that you use at the coffee machine" a while ago for long-running stuff (simulations, compilations, NP-complete stuff like routing or model checking). It's basically paying engineers to do nothing.
- rbanffy 13y agoI always assumed we were paid to think, not to type. If you measure workforce engagement by the amount of time their knees spend under the desk, you are measuring input, not output.
- klodolph 13y agoWell, yes, that's a bad way to measure performance. But when I compile something, it's because I want feedback from the compiler and static analyzer about the program I just wrote. I have a half-dozen parts of the program in short-term memory which I want to consider when seeing the output or the program behavior. If it takes five minutes to compile code, then my short-term memory will be filled with something else by then, like the weather, chores I'm putting off at home, or whatever. 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.
- nraynaud 13y agoIt's more like reading reddit, when you're waiting for a heavy computation, you're not exploring results, tuning the algorithm or anything. You're just stuck on your tracks by a stupid machine. If anything, you'll be conservative in your use of the slow algorithm, because you don't want to lose another half day. You can't fiddle. Even if you try to be productive reading something smart in the mean time, you'll be interrupted by the end of the computation, and you'll be completely out of context when analyzing the results. (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)
- bryanlarsen 13y agoor to sword fight: http://xkcd.com/303/ http://xkcd.com/303/
- dmethvin 13y agoThis is one of the reasons why continuous performance testing is important. Even when your own code doesn't regress, the platform beneath you may do so. In this case it sounds like a case of the platform making most stuff faster but not page faults, so it looks proportionally worse.
- jw2013 13y agoI once wrote a kernel loadable module for getting page fault handling info (time cost, etc.): https://github.com/jw2013/getvminfo 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.
- evmar 13y agoLinus wrote: 'Even a fully built kernel ("allmodconfig", so a pretty full build) takes about half a minute on my normal desktop to say "I'm done, that pull changed nothing I could compile".' 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-linux-kernel-2-6-38-2/ http://larjona.wordpress.com/2011/06/15/numbers-about-the-li...
- josephg 13y agoFrom further down in the comment thread, Linus says that speeding this up should help other workloads too, and he's sick of using make replacements: --- +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.
- danudey 13y agoMaybe he'll get so fed up with make that he'll write his own that everyone can just switch to instead of all the crud we have.
- Rusky 13y agoOne reason the Mill architecture looks so interesting is that all of the state that needs to be saved is done asynchronously, in parallel with program execution. In fact, the same mechanism is used for function calls, system calls, and interrupts, which all just look like atomic ops. That should make interrupts and irets much faster.
- rbanffy 13y agoIIRC SPARC register windows do something like this - a call and a return do not need to save or restore anything but a pointer to what is the first register available to your function.
- agwa 13y agoItanium too. Coming up with a better architecture is easy compared to the challenge of getting people to actually use it.
- Rusky 13y agoI think it's at least partially a problem of not being better enough than "good enough". Not to mention Itanium (and maybe Sparc, I don't know enough about it to say) had plenty of its own problems, including with interrupt handling.
- willvarfar 13y ago(Mill team) 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.
- mwcampbell 13y agoCan you guys say anything yet about how the Unix fork syscall is implemented on that architecture? The requirement for copy-on-write pages seems to conflict with a single virtual address space.
- epistasis 13y agoThis sounds like it's just the cost to traverse the page table, right? ~300 cycles per raw memory lookup, and 3 of them because you'll typically need to go three levels deep? 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.
- justincormack 13y agoSwitch to PowerPC and get 64k pages by default in most distros!
- deleted 13y ago[deleted]
- rwmj 13y ago.. and exposing lots of buggy userspace code into the bargain!
- dmm 13y agoWhat kind of bugs appear with bigger default page sizes?
- rwmj 13y agoLots of userspace makes assumptions about page size being 4k and breaks when it changes. Try looking for: https://www.google.co.uk/search?q="pagesize"+"64k"+"bug" https://www.google.co.uk/search?q="pagesize"+"64k"+"bug" https://www.google.co.uk/search?q="pagesize"+"64k"+"issue" 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: https://lwn.net/Articles/591690/ https://lwn.net/Articles/591690/
- codys 12y agoAnd an even slower page fault mechanism. PPC generally ends up relying on hugepages to try to match pagefault speeds on x86
- dchichkov 13y agoInterestingly, a soft page fault can be caused not only by a real page fault event, but also by NUMA autobalancing. Which actually could be a major source of kernel interference to purely user space processes. I sometimes see these NUMA-originated soft page faults very high up in a (CPU/cache) profiler for sensitive real-time processes that should avoid contexts switches and L1/L2 cache pollution at all costs. 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 Or booting the box with the kernel command line that includes: numa_balancing=disable
- fooyc 13y agoTurns out the kernel is very well optimised for kernel compiling workloads.
- thrownaway2424 13y agoLinux is highly tuned for exactly two things: building itself, and distributing itself.
- Peaker 13y agoIf "git status" is empty, and takes milliseconds to know that -- "make" should take roughly the same amount of time to know the same. There 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 https://github.com/ElastiLotem/buildsome [2] https://github.com/ElastiLotem/buildsome/raw/master/doc/Presentation.pdf https://github.com/ElastiLotem/buildsome/raw/master/doc/Pres...
- reubenmorais 13y ago> If "git status" is empty, and takes milliseconds to know that -- "make" should take roughly the same amount of time to know the same. 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.
- Peaker 13y agoIf nothing needs to be built, my statement still stands. The build system needs to cache its dependency computations. Empty build would be same time as git status.
- dangerlibrary 13y ago#ifdef win32 ...some changes we don't care about on linux #else ...no changes #endif so you'd still need to traverse all the headers, at a minimum.
- reubenmorais 13y agoThough in this case, things do need to be rebuilt. No C build system is this clever, as far as I know :)
- abus 13y agoWhat in the world could have convinced Linus to use Google+?
- lern_too_spel 13y agoHe needs asymmetric follows for his rants to get reach, and his rants don't fit in 140 characters. That leaves blogs and Google+, which is a tradeoff between better formatting controls and monetization (blogs) and realtime engagement (Google+). His choice makes perfect sense to me.
- shawnz 13y agoWhy not Facebook?
- lern_too_spel 13y agoFacebook requires log in to see public posts. It is not a suitable platform for public ranting or any other public communication.
- protopete 13y agoTo count the number of page faults during execution, use: perf stat <executable> Page faults occur after anonymous pages are mmap'ed for the heap, either mapping a common zero page, then faulted again for a memory write. Prefaulting the page with MAP_POPULATE flag to mmap can help reduce the number of page faults. 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.)
- michaelf 13y agoCan anyone hazard a guess as to how Linus was able to measure the cost of a page fault and an iret so precisely? What tools and techniques might he have used?
- zerohp 13y agoI don't know what he used, but its probably based on the model specific registers for performance counters. See Chapter 18 of the Intel 64 and IA-32 Architectures Software Developer's Manual.
- apw 12y agoIt's quite likely that he was using `perf': $ perf stat make ... 116,222 page-faults # 0.046 M/sec ... https://perf.wiki.kernel.org/index.php/Tutorial https://perf.wiki.kernel.org/index.php/Tutorial
- weinzierl 13y agoThe title is a bit misleading. If I understood Linus correctly he is saying that a page fault on modern processors is costly. There is nothing the OS can do to make a page fault itself (or iret) faster. > 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.
- sounds 13y agoI think it's interesting how he compares Haswell to his 32-bit Core Duo. Haswell: 1050 cycles / 80.7% CPU time on his microbenchmark Core Duo: 940 cycles / 58% CPU time on his microbenchmark
- Zenst 13y agoAgreed, given one is 32 bit memory addressing and the other 64 bit. You would expect the 64 bit to be upto twice as long and adding optimisations in the middle, but not equal. After all a 32 bit memory address is twice as much as a 64 bit one to handle behind the scene. 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.
- dllthomas 13y agoPage faults that don't happen are free. If the OS can find ways of reducing the number of them, that's a way of speeding up the average "time there would have been a page fault"... you're right that the title is misleading, though.
- saurik 13y agoIs anyone else horribly sad that this kind of content and discussion is ending up on Google+? I often find myself combing the mailing lists of key projects like the Linux kernel to figure out why things happened the way they did, and Google+ comments are not searchable in the same way; and even if they were, I am having a difficult time believing that the content will not just end up gone entirely after another ten or twenty years. I know some people point out that using "modern" communication channels decreased friction, latency, etc. but for some use cases the value of records and centralization is high enough to warrant moving slower or more painfully.
- Igglyboo 13y agoIs anyone else horribly sad that this kind of content and discussion is ending up on the internet instead of written down in books? 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.
- mwcampbell 13y agoWhy do you equate discussions on mailing lists with living in the past? Sure, Google+ is newer, but that doesn't make it better. On the contrary, mailing lists are better in at least two ways: they're decentralized, and they don't require proprietary software.
- taeric 13y agoThat said, the level of "discussion" in that thread is kind of sad. No guarantee it would be better elsewhere, but I at least have tools that help me wade through mailing list traffic. 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.
- lomnakkus 13y agoIf mailing lists have survived to this day they must be doing something right. (We'll see if G+ survives into 2020, but that's not really my point.)
- Torgo 13y agoI consume Mr. Torvalds's G+ posts like I suppose a sports fan consumes sports news. I can't play at that level so I live vicariously through others.
- dalek2point3 13y agoI'm a complete noob when it comes to kernel development -- but this seems super interesting. Anyone care to explain what's going on?
- Rusky 13y agoEach process has a set of page tables, which describe how physical memory is mapped to their view of memory. The entries in those tables can be marked "not present", so that when they're accessed by the process the kernel is signaled via what's called a page fault. 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.
- dalek2point3 13y agothanks! this is a great explanation.
- julie1 13y agoSo on 82 comments only one notices that the title is awfully wrong, and the 81 others spread their culture like jam on bread; the less you have the more you spread. 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.
- userbinator 13y agoI'm not intimately familiar with the Linux kernel, but doesn't a page fault usually involve reading something from disk? In that case even the fastest SSD is going to take a few orders of magnitude more time than those 1K cycles to get the desired data back into memory.
- sliverstorm 13y agoA page fault is when the TLB misses and the CPU doesn't know where in physical memory to find the requested virtual address. 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.
- nkurz 13y agoIntel's documentation calls it a "Page-Fault Exception". See Section 4.7 here: http://www.intel.com/Assets/en_US/PDF/manual/253668.pdf http://www.intel.com/Assets/en_US/PDF/manual/253668.pdf 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-tables.txt https://www.kernel.org/doc/Documentation/x86/exception-table...
- userbinator 13y agoWhat you described, a TLB miss, is just called a TLB miss. The CPU will automatically find and read the appropriate PTE and load it into the TLB, just like it does on a cache miss.
- sliverstorm 13y agoI learned slightly differently, that the CPU does not always find the mapping by itself, but this explains it: Some systems, mainly older RISC designs, trap into the OS when a page translation is not found in the TLB -- Wikipedia
- acqq 13y agoSo Linus noticed that the page fault on the Intel CPU became slower on the newer CPUs something like 10%. Before and after, it took roughly 1000 ticks to perform the fault. Which just means that if the clock is the same, let's say 3 GHz, instead of 3 millions page faults per second on Core Duo you can now "just" do 2.7 millions of page faults per second. Doesn't sound like something to be much worried about. The code which spends most of its time in page faults is just something that I can't imagine to be an example of the code anybody even attempted to make faster. Linus admits that too: changing the build process would certainly eliminate significant number of page faults in his case. So, my conclusion this time is... Meh. The pig did't fly before and now it won't 10% more so. Intel guys, if you sacrificed this in order to make the instructions that matter faster, I welcome this: Linus also observes that the rest of his code practically got faster around... more than 3 times!? Before, it was around 900 ticks page fault code, the rest of the code around 50 percent of total, that is also 900 ticks. Now it's 1000 ticks PF, the rest around 20% of total (see: Linus claims 80% spent in PF), that is, around 250 ticks for his code. I say, Intel, you did a perfect job speeding up some code that matters to take just 250 instead of 900 ticks between Core Duo and new CPUs. This sounds amazing. (I of course welcome any arguments that demonstrate that I overlooked something when claiming all this.)
- ultimape 13y agoYes, in Linus's case, it is a faster overall runtime, but such a stark difference in cycle times is a bit of an eyebrow raiser. 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 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.
- acqq 13y ago