3 ms·
It'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
by kenjackson 16y ago
It'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.587 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).
- gojomo 16y agoDoes the 'B-heap' PHK describes already have a name in the literature?
- kenjackson 16y agoNot 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.3789 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.... That's a good start if you're looking at the literature.
- mad 16y agoIt's the van Emde Boas layout. For example, see here http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli....
- ssp 16y agoNo, it's not. The van Emde Boas layout splits the data set into sqrt(n) chunks of sqrt(n) items. Then it recursively splits each of those chunks similarly. This version simply divides the data set into page sized chunks. That has worse memory access complexity than the van Emde Boas layout, but is likely simpler to deal with in practice. It's not trivial to maintain the van Emde Boas layout under insertion and deletion for example. (The post you link is a good one btw.)
- ssp 16y agoNevertheless, 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.
- kenjackson 16y agoActually, even if your goal is to simply count jumps in the memory hierarchy, it can still be tough for several reasons. For example, the set associativity of a given level of the memory hierarchy can make analysis very tricky. Somethings that would ostensibly be efficient w/ respect to the memory hierarchy could actually have a whole bunch of conflict misses. Modeling this is possible, but not easy. Especially for non-trivial algorithms. Another example of a complicating issue is garbage collection. If the GC uses something like compaction you really don't have a great idea of where your data is. We used to do all these tricks in 'C' to map data and move it around to get the best locality. This isn't nearly as feasible in C# and Java. And there really are kind of two related questions: 1) How does this algorithm perform for a given memory hierarchy? 2) What is the best parameterization of this algorithm for the memory hierarchy? Question 1 is a fair bit easier than question 2. And you'd be surprised at how much faster you can make the same algorithm, by changing certain parameters (chunk size, etc...) for a given architecture. And these things are hard to answer by simple reasoning. And a local maxima, may in fact be far from the global maxima.
- wingo 16y ago> We used to do all these tricks in 'C' to map data and move it around to get the best locality. This isn't nearly as feasible in C# and Java. Did we really? With malloc things are just as unpredictable. If you resort to mmap-like memory-management, such schemes are almost as feasible in high-level languages (with appropriate FFIs) as in low-level languages, provided you are accessing data and not code.