|
General articles: - Behdad Esfahbod MSc thesis about Preload project
- Wikipedia article about Windows prefetcher
- Presentation about boot prefetching from pagecache project by Fengguang Wu
- Stefan Strauss-Haslinglehner master's thesis about prefetching solution for Linux (in German) Automatic translation from German to English
- "On faster application startup times: Cache stuffing, seek profiling, adaptive preloading", Bert Hubert in Proceedings of Linux Symposium 2005, page 245. Important quotes:
- While highly elegant, this leads to unpredictable seek behaviour, with occasional hits going backward on disk. The author has discovered that if there is one thing that disks don’t do well, it is reading backwards.
- The reads which cannot be explained are in all likelihood part of either directory information or filesystem internals. These are of such quantity that directory traversal appears to be a major part of startup disk accesses.
- The really dangerous bit is that we need to be very sure our sequential slab is still up to date. It also does not address the dentry cache, which appears to be a dominant factor in bootup.
- It is natural to assume that seeking to locations close to the current location of the head is faster, which in fact is true. For example, current Fujitsu MASxxxx technology drives specify the ‘full stroke’ seek as 8ms and track-to-track latency as 0.3ms. However, for many systems the actual seeking is dwarfed by the rotational latency. On average, the head will have to wait half a rotation for the desired data to pass by. A quick calculation shows that for a 5400RPM disk, as commonly found in laptops, this wait will on average be 5.6ms. This means that even seeking a small amount will at least take 5.6ms. The news gets worse—the laptop this article is authored on has a Toshiba MK8025GAS disk, which at 4200RPM claims to have an average seek time of 12ms. Real life measurements show this to be in excess of 20ms.
Tools: Disk access characteristics: Google Summer of Code applications and projects: This prefetcher links: Other links:
|
Sign in to add a comment
This kind of prefetching goes back farther than the references you have up there. The earliest I'm aware of was in the 1996 timeframe, in a product for Windows 95 called SuperFassst?!. A patent was issued on that (but you don't have to worry about that patent, #5,933,630, for reasons I'll explain momentarily). Here's a link to the patent: http://www.google.com/patents?vid=USPAT5933630
Microsoft was aware of SuperFassst?!, and there has been an allegation that the Windows prefetch system in XP was essentially the same thing, just implemented at a different level. There was a lawsuit over that, which went to trail at the end of 2007, with much of the argument revolving around whether it mattered as far as the patent goes whether you log file accesses at the file system level, or in the memory manager by logging page faults. The jury (9 people, 6 of which do not use computers at all) decided that the whole thing was obvious, and invalidated the patent, which is why you don't have to worry about it--but if you are going to give a reasonably thorough bibliography, it should probably be cited.
Also, if anyone is really curious about what Microsoft does, the transcript from the aforementioned trial would provide fascinating reading. Quite a lot of internal design documents from Microsoft were presented in open court, and an expert on plaintiff's side who had access to Windows source code presented detailed diagrams and flow charts showing exactly how their prefetching works (and listing errors about this in Mark Russinovich's book on Windows internals). I have no idea how one goes about ordering a transcript, but the case was Computer Acceleration Corporation vs. Microsoft, and it was case number 9:2006cv00140 in the Eastern District of Texas. I also don't know if the slides from the trial are available, or just the text transcript--without the slides it would be not nearly as good, but there would still be a lot of interesting info in just the text. (I was at the trial, which is why I know all this. I'm one of the people who developed SuperFassst?! back in 1996).