3 ms·
I could be wrong, but it sounds to me like you may not have the base of knowledge necessary to accurately evaluate Poul's writing. > So, maybe I'm reading this
by jemfinch 16y ago
I could be wrong, but it sounds to me like you may not have the base of knowledge necessary to accurately evaluate Poul's writing.
> So, maybe I'm reading this wrong, but it sure sounds like he's going out of his way to find a scenario that results in an "order of magnitude" difference, simply so that he can write an article with a big claim.
What he's saying is that this order of magnitude difference is where his software, Varnish, spends most of its time in reality. Systems that run Varnish are almost always at the end of his graph where VM pressure is the greatest, largely because Varnish is specifically written to allow the VM to manage disk-to-memory and memory-to-disk movement, rather than implementing it (poorly) in-process like Squid does.
> (that sound you hear is the frantic waving of hands)
I don't see how his statement is a hand wave at all.
> Basically, the claim is that if you build a binary heap for an exceptionally infrequent operation, and make that heap big enough to require multiple pages (about 8 MB, in this case, on a machine that is presumably managing a multi-gigabyte resident web cache),
Pages are 4KB on most systems; I don't know where you're getting your 8MB number from.
> then do absolutely nothing to ensure that it stays in memory,
Why should you? It's only used infrequently.
> then pick the worst possible runtime scenario (touching every item in the heap in a pattern that results in repeated page faults) you can get pathological behavior.
You're not understanding. A heap's ordinary behavior causes excessive page faults on account of its poor locality. I assume you recall (or can remind yourself easily) the algorithm for using a heap as a priority queue: you remove the first element, substitute a leaf element, and sift the leaf element down, swapping it until it's greater than both its children). Because the children of element `k` are elements `2k` and `2k+1`, after the first 2,047 elements, every single comparison between levels potentially requires that the OS page in another 4KB page from disk. When you've got a million elements, that's 11 fast, in-memory comparisons for the first page, and 19 comparisons which require at least 1ms to read from disk the VM page where the children reside. This is not a worst case at all, but the common case. This doesn't require reading or writing all the elements in the queue, it just uses the heap normally.
> If I presented this problem to any of my own CS professors, I'm willing to wager that I'd be asked why I was being so stupid as to allow my index to page out of memory, when it represents such a trivial percentage of my heap.
If you kept the whole heap resident in memory, that'd just mean that other pages which you probably need more frequently than once per minute would be paged out to disk instead. At high VM pressure, you'll probably pay a higher paging cost if you keep an infrequently-used heap in memory, because pages you need more, that would stay in memory if you allowed the OS to page out your heap, end up being paged out instead.
- deleted 16y ago[deleted]
- timr 16y ago"I could be wrong, but it sounds to me like you may not have the base of knowledge necessary to accurately evaluate Poul's writing." Touché. I'm not Knuth or anything, but I try. "Pages are 4KB on most systems; I don't know where you're getting your 8MB number from." When I said "a heap big enough to require multiple pages", I actually meant it. Hence, I was referring to the size of the heap he used for his test: 8MB (1M records, 512 elements per page, 1954 pages allocated in memory). I may not be brilliant, but to compensate for my lack of intellectual horsepower, I tried to read the article closely. "If you kept the whole heap resident in memory, that'd just mean that other pages which you probably need more frequently than once per minute would be paged out to disk instead....pages you need more, that would stay in memory if you allowed the OS to page out your heap, end up being paged out instead." Indeed. If you fixed your 8MB heap in memory, you would lose that 8MB of pages for other uses. I guess it's a trade-off then...is it better to use 8MB of RAM on a system with gigabytes of main memory, or to re-write fundamental data structures for worst-case timing of operations that occur once per minute? It's certainly a conundrum....
- jemfinch 16y ago> When I said "a heap big enough to require multiple pages", I actually meant it. Did you? Your math that follows seems to indicate otherwise. > Hence, I was referring to the size of the heap he used for his test: 8MB (1M records, 512 elements per page, 1954 pages allocated in memory). I don't understand. I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with MB? > Indeed. If you fixed your 8MB heap in memory, you would lose that 8MB of pages for other uses. I guess it's a trade-off then...is it better to use 8MB of RAM on a system with gigabytes of main memory, or to re-write fundamental data structures for worst-case timing of operations that occur once per minute? The knowledge you seem especially to lack here is that Poul's software, Varnish, is designed to operate in conditions where swap is being used. It's irrelevant how many gigabytes of main memory are available: Varnish will use it all, and let the operating system decide which VM pages should be evicted to disk and which should remain resident in memory. His software lives at high VM pressure by design, so every page his index/heap requires in memory is a page of cached content that Varnish will not be able to deliver quickly. He doesn't just pay that cost when the heap runs once per minute, but also when the heap's pages are paged out again, and pages which would otherwise have remained resident in memory are brought back into memory.