3 ms·

> 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

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

wrs 16y ago
You guys are totally talking past each other. Varnish makes the assumption that the OS cache replacement policy is awesome. You should let it do its thing and write your data structures accordingly. Considering that the author is intimately familiar with that policy, it's a valid approach. You could alternately say that you don't want to depend on the OS policy, which you don't control. You could say that using a differently-packed heap layout is more important than retaining 8MB more page content in the cache. (Maybe you have a nice fully-debugged heap library handy and you don't want to throw it away to get that 8MB back.) In that case, wiring that 8MB into physical memory is a valid approach. Databases (and, indeed, OS kernels) override generic cache replacement policies like this all the time. What is not a valid approach ("doing it wrong") is not thinking through issues like this at all, ignoring the dominating runtime cost of the memory hierarchy.
- jrockway 16y ago
  You guys are totally talking past each other. Not totally, it started with "the article is dumb", to which someone replied "nuh uh! you're dumb", to which the OP replied, "oh no i'm not", to which another reply said "oh yes you are". Very focused. (The rest of the posts were good reading, but getting the emotion involved just makes everyone mad. Neither of the commenters cared anymore about their argument, they only cared about winning.) At least on 4chan we get pictures of cats with this stuff ;)
  - jemfinch 16y ago
    > The rest of the posts were good reading, but getting the emotion involved just makes everyone mad. For my part, there was no emotion involved. That's why I didn't bother replying to the emotional aspects of timr's second post. > Neither of the commenters cared anymore about their argument, they only cared about winning. I care a lot about the argument; I think Poul's article was interesting and relevant, and should not be dismissed by people who (it seems clearly to be the case) did not understand it, but think they did.
- jemfinch 16y ago
  > You guys are totally talking past each other. That doesn't change the fact that, as best I can discern, the OP has made some factual errors which demand (<http://xkcd.com/386/> http://xkcd.com/386/>) response.
  - ErrantX 16y ago
    You realize that the XKCD example is a warning for those in your position not timr's :) (I have it hung on the wall in my office for this very reason)
- timr 16y ago
  I'm not talking past anyone -- I'm just choosing to ignore the silly aspersions to my intelligence. It's possible to make an argument without calling the other guy stupid. What you're seeing here is really just the usual battle between ideology and reason that seems to pop up on HN on the weekends. We've got a fundamentally silly article that wants to take all of computer science to task, based on a corner-case analysis of worst-case performance of a single algorithm, in a single, exaggerated context. You're right that the author wants to rely entirely upon the OS cache replacement policy for Varnish and that's fine, as far as it goes. But this ideology leads directly to the problem observed (namely: some rarely used things that really should stay in memory are evicted, because the OS has no ability to discern the semantics of memory use by the application). Rather than acknowledging this limitation, the author has decided instead that the algorithms are all wrong, and that the Stoopid Computer Scientists are all a bunch of short-sighted eggheads. Again, it's not a question of who's right, and who's wrong -- it's a matter of philosophy. You can assume that the OS memory manager is the all-knowing, all-powerful Wizard of RAM, or you can give it some guidance. In this case, locking an 8MB heap into RAM is hardly a trade-off, when you're talking about a system that is actively managing several orders of magnitude more memory on a regular basis. Spending days of coding time optimizing a basic data structures for worst-case memory access patterns is short-sighted, when the alternative is an mlock() call.
timr 16y ago
"Your math that follows seems to indicate otherwise....I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with MB?" No. There are 1M records, 512 per page. This is directly from the article. From this, we can deduce that each record is 4096 / 512 = 8 bytes. Eight bytes multiplied by 1M records: 8MB. Don't believe my math? OK. The article explicitly said that there were 1954 pages in the heap. If we have a 4k page size, that's (4096 * 1954) bytes == 7.63 MB. Even better.
- jemfinch 16y ago
  Why are you still arguing about this? Your original claim was, "if you build a binary heap...and make that heap big enough to require multiple pages (about 8 MB". It does not take 8 MB to make a heap "big enough to require multiple pages." It takes 4 KB. PHK's example was a middling-sized heap, not the minimum heap necessary to require multiple pages, as you implied with your original statement.
  - sesqu 16y ago
    The original was make that heap big enough to require multiple pages (about 8 MB, in this case You are arguing that it has to be 4 KB. timr is arguing it has to be big enough, and that it is 8 MB. The implication is that it is big enough to qualify, without commenting on how big is big enough. The wording was misleading, and you made the mistake of focusing on what you saw to be an error in expression and taking it to be error in meaning, even after debate. Sadly, that's a very easy mistake to make, especially if you haven't argued with people very much, and it is only exacerbated by a textual medium with memory that can be referenced. If you ever find yourself in a similar situation again, try to read the whole offending paragraph for context. A lot of people make inaccurate statements that can only be correctly understood by identifying their frame of thought (which can be in error, muddled, or just presuming).

wrs 16y ago

You guys are totally talking past each other. Varnish makes the assumption that the OS cache replacement policy is awesome. You should let it do its thing and write your data structures accordingly. Considering that the author is intimately familiar with that policy, it's a valid approach. You could alternately say that you don't want to depend on the OS policy, which you don't control. You could say that using a differently-packed heap layout is more important than retaining 8MB more page content in the cache. (Maybe you have a nice fully-debugged heap library handy and you don't want to throw it away to get that 8MB back.) In that case, wiring that 8MB into physical memory is a valid approach. Databases (and, indeed, OS kernels) override generic cache replacement policies like this all the time. What is not a valid approach ("doing it wrong") is not thinking through issues like this at all, ignoring the dominating runtime cost of the memory hierarchy.

jrockway 16y ago
You guys are totally talking past each other. Not totally, it started with "the article is dumb", to which someone replied "nuh uh! you're dumb", to which the OP replied, "oh no i'm not", to which another reply said "oh yes you are". Very focused. (The rest of the posts were good reading, but getting the emotion involved just makes everyone mad. Neither of the commenters cared anymore about their argument, they only cared about winning.) At least on 4chan we get pictures of cats with this stuff ;)
- jemfinch 16y ago
  > The rest of the posts were good reading, but getting the emotion involved just makes everyone mad. For my part, there was no emotion involved. That's why I didn't bother replying to the emotional aspects of timr's second post. > Neither of the commenters cared anymore about their argument, they only cared about winning. I care a lot about the argument; I think Poul's article was interesting and relevant, and should not be dismissed by people who (it seems clearly to be the case) did not understand it, but think they did.
jemfinch 16y ago
> You guys are totally talking past each other. That doesn't change the fact that, as best I can discern, the OP has made some factual errors which demand (<http://xkcd.com/386/> http://xkcd.com/386/>) response.
- ErrantX 16y ago
  You realize that the XKCD example is a warning for those in your position not timr's :) (I have it hung on the wall in my office for this very reason)
timr 16y ago
I'm not talking past anyone -- I'm just choosing to ignore the silly aspersions to my intelligence. It's possible to make an argument without calling the other guy stupid. What you're seeing here is really just the usual battle between ideology and reason that seems to pop up on HN on the weekends. We've got a fundamentally silly article that wants to take all of computer science to task, based on a corner-case analysis of worst-case performance of a single algorithm, in a single, exaggerated context. You're right that the author wants to rely entirely upon the OS cache replacement policy for Varnish and that's fine, as far as it goes. But this ideology leads directly to the problem observed (namely: some rarely used things that really should stay in memory are evicted, because the OS has no ability to discern the semantics of memory use by the application). Rather than acknowledging this limitation, the author has decided instead that the algorithms are all wrong, and that the Stoopid Computer Scientists are all a bunch of short-sighted eggheads. Again, it's not a question of who's right, and who's wrong -- it's a matter of philosophy. You can assume that the OS memory manager is the all-knowing, all-powerful Wizard of RAM, or you can give it some guidance. In this case, locking an 8MB heap into RAM is hardly a trade-off, when you're talking about a system that is actively managing several orders of magnitude more memory on a regular basis. Spending days of coding time optimizing a basic data structures for worst-case memory access patterns is short-sighted, when the alternative is an mlock() call.

timr 16y ago

"Your math that follows seems to indicate otherwise....I demonstrated that a heap with only 2048 records requires multiple 4 KB pages. Are you perhaps confusing KB with MB?" No. There are 1M records, 512 per page. This is directly from the article. From this, we can deduce that each record is 4096 / 512 = 8 bytes. Eight bytes multiplied by 1M records: 8MB. Don't believe my math? OK. The article explicitly said that there were 1954 pages in the heap. If we have a 4k page size, that's (4096 * 1954) bytes == 7.63 MB. Even better.

jemfinch 16y ago
Why are you still arguing about this? Your original claim was, "if you build a binary heap...and make that heap big enough to require multiple pages (about 8 MB". It does not take 8 MB to make a heap "big enough to require multiple pages." It takes 4 KB. PHK's example was a middling-sized heap, not the minimum heap necessary to require multiple pages, as you implied with your original statement.
- sesqu 16y ago
  The original was make that heap big enough to require multiple pages (about 8 MB, in this case You are arguing that it has to be 4 KB. timr is arguing it has to be big enough, and that it is 8 MB. The implication is that it is big enough to qualify, without commenting on how big is big enough. The wording was misleading, and you made the mistake of focusing on what you saw to be an error in expression and taking it to be error in meaning, even after debate. Sadly, that's a very easy mistake to make, especially if you haven't argued with people very much, and it is only exacerbated by a textual medium with memory that can be referenced. If you ever find yourself in a similar situation again, try to read the whole offending paragraph for context. A lot of people make inaccurate statements that can only be correctly understood by identifying their frame of thought (which can be in error, muddled, or just presuming).