You're Doing It Wrong: CS in the real world
queue.acm.org
You're Doing It Wrong: CS in the real world
1–10 of 60 posts
Re: You're Doing It Wrong: CS in the real world
#2It's a good article, although certainly not new, even to academics. There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy.
For example, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5...
And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious algorithms (although, as you can tell by the name, they have somewhat opposing ideological beliefs).
Nevertheless, this is a good example as to why performance on real machines often needs to be implemented, rather than speculated, as the the architectural complexity can lead to some interesting peformance characteristics (of course, some good ground in complexity and experience will help prioritize which algorithms are even in the ballpark).
Re: You're Doing It Wrong: CS in the real world
#3It's a good article, although certainly not new, even to academics. There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy. For example, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5... And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious alg…
Does the 'B-heap' PHK describes already have a name in the literature?
Re: You're Doing It Wrong: CS in the real world
#4this article is ridiculous. He makes blanket claims based on the performance of a very specialized application. For many / most applications, memory is so cheap that you CAN effectively ignore VM. Where some thought about the relative latency of memory is useful though is in parallel applications on NUMA hardware.
Re: You're Doing It Wrong: CS in the real world
#5It's a good article, although certainly not new, even to academics. There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy. For example, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5... And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious alg…
Does the 'B-heap' PHK describes already have a name in the literature?
Not that I know of, but there are a LOT of heap variants in the literature, and I'm not clear on the details of the OPs algorithm (it gave an overview, but not as detailed as most in the literature)
The work by Arge, et al is probably the foundational work in priority queues for modern memory hierarchies. If I recall correctly, they use a cache oblivious approach: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106....
That's a good start if you're looking at the literature.
Re: You're Doing It Wrong: CS in the real world
#6this article is ridiculous. He makes blanket claims based on the performance of a very specialized application. For many / most applications, memory is so cheap that you CAN effectively ignore VM. Where some thought about the relative latency of memory is useful though is in parallel applications on NUMA hardware.
That depends whether, when you're talking about 'most applications', you mean most by sheer number, or most by processing time used. Because yes, there are a zillion tiny applications that don't care about VM space. But the ones that do are used far more often (running nonstop on servers, etc) than that random iBoobs app on your iPhone.
Re: You're Doing It Wrong: CS in the real world
#7this article is ridiculous. He makes blanket claims based on the performance of a very specialized application. For many / most applications, memory is so cheap that you CAN effectively ignore VM. Where some thought about the relative latency of memory is useful though is in parallel applications on NUMA hardware.
this article is great. He gives a specific example based on real-world performance, showing that you can't always rely on theory assuming a general case. For many intensive applications, memory is so precious, you CAN'T effectively ignore VM. Some thought about the relative latency of memory is useful in more than just parallel applications on NUMA hardware.
(Git and Mercurial are designed with an eye towards optimizations based on disk latencies. Python is optimized with regard to CPU cache. We're back to "Abstractions Leak.")
Re: You're Doing It Wrong: CS in the real world
#8I'm having a hard time reconciling this statement from the beginning of the article (where he establishes his premise):
"One particular task, inside Varnish, is expiring objects from the cache when their virtual lifetimers run out of sand. This calls for a data structure that can efficiently deliver the smallest keyed object from the total set."
with this statement, where he defends his claims that the Stoopid Computer Scientists have it all wrong:
"Did you just decide that my order of magnitude claim was bogus, because it is based on only an extreme corner case? If so, you are doing it wrong, because this is pretty much the real-world behavior seen....Creating and expiring objects in Varnish are relatively infrequent actions. Once created, objects are often cached for weeks if not months, and therefore the binary heap may not be updated even once per minute; on some sites not even once per hour."
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. The only justification for this is left as an exercise in critical thinking for the reader:
"At this point, is it wrong to think, 'If it runs only once per minute, who cares, even if it takes a full second?' We do, in fact, care because the 10 extra pages needed once per minute loiter in RAM for a while, doing nothing for their keep—until the kernel pages them back out again, at which point they get to pile on top of the already frantic disk activity, typically seen on a system under this heavy VM pressure."
(that sound you hear is the frantic waving of hands)
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), then do absolutely nothing to ensure that it stays in memory, 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.
I think I speak for dopey CS professors everywhere, when I say: Duh.
Don't misunderstand my point: it's not that the article is wrong...it's just that it's so arrogantly written that it's hard to forgive the fact that the situation described is contrived. 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.
Re: You're Doing It Wrong: CS in the real world
#9It's a good article, although certainly not new, even to academics. There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy. For example, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5... And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious alg…
Does the 'B-heap' PHK describes already have a name in the literature?
It's the van Emde Boas layout. For example, see here http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli....
Re: You're Doing It Wrong: CS in the real world
#10It's a good article, although certainly not new, even to academics. There is a whole branch of CS that is dedicated to understanding complexity with respect to the memory hierarchy. For example, see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5... And there are different frameworks for building algorithms that perform well in the memory hierarchy, such as Architecture Cognizant and Cache Oblivious alg…
Nevertheless, this is a good example as to why performance on real machines often needs to be implemented, rather than speculated, as the the architectural complexity can lead to some interesting peformance characteristics
I don't really agree with this. In the old days, to really get an idea of how fast something would run, you had to count cycles and think about pipeline hazards and whatnot. Today, you can simply estimate the number of misses at the various memory levels -- this is often not that difficult to do -- and get a good idea of the program's performance.
So architectural differences used to be much more important back when I/O didn't dominate as much as it does today.