4 ms·
Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy. If you've ever wondered why the CS literature seems full of
by kmavm 16y ago
Knuth was writing for MIX. This machine, like all its contemporaries, had a flat memory hierarchy.
If you've ever wondered why the CS literature seems full of trees, but in 2010 practice, sets, associative memories, etc., are often implemented with hashing, consider that a cache miss on much modern hardware is 300 cycles. The equivalent of
for (register int i = 0; i < 299; i++) ;
can pay for itself by saving a cache miss. The log N cache misses to find something in a tree (the pointers all point somewhere random, and you should expect them to miss) is much more expensive than hashing reasonable-length keys and taking a single cache miss in a hash table, for almost any value of N > 1.
The author has made a nice contribution; as Colivas probably was trying to hint to him, there is a long history of converting linked data structures to block-friendly form by an analogous transformation. A straight write-up of his work, without all the chest-pounding over his rediscovery of the fact that block devices operate on blocks, would have been a pleasure to read. Pity.
- nostrademons 16y agoThis is a big problem for functional languages, and there've been a bunch of efforts to solve it. For example, Clojure's default dictionary type uses a hash array-mapped trie, with each level sized so that a typical block can fit in a single cache line. It's very common for the youngest generation in a generational garbage collector to be sized to fit entirely into L2 cache, so that you know that every write or read of a recently-allocated value will at least be an L2 cache hit. (Unfortunately, it's usually not practical to make it a L1 hit, lest you be stuck thrashing in the GC, so you're still looking at ~12 cycles.) Deforestation optimizes out allocation entirely, instead performing the next computation immediately on values that are already in registers. Many GCs will also try to copy nearby pointers next to their parents, so that the pointers aren't quite random.
- haberman 16y agoNote that the article's "improved" data structure is 30% slower than the naive binary heap when there's no VM pressure. And his heap is small compared to the cache itself. In other words, if he had just used mlock() to make sure his heap wasn't getting swapped out, he would have gotten better performance and avoided the need to invent a "new" data structure. He chose a really bad example to get on a soapbox about.
- deleted 16y ago[deleted]
- davidcuddeback 16y agoFTA: A 300-GB backing store, memory mapped on a machine with no more than 16 GB of RAM, is quite typical. The user paid for 64 bits of address space, and I am not afraid to use it. He's writing a data structure that's not intended to fit within physical memory. mlock() doesn't do you any good in that scenario.
- rlpb 16y agoI think your quote is about the entire cache, not just the heap.