4 ms·

Thanks for the article and the comments, I had never heard of Cache Oblivious algorithms and this article seems to indicate that others have not either: http://

Thanks for the article and the comments, I had never heard of Cache Oblivious algorithms and this article seems to indicate that others have not either: 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... I wonder if current popular libraries like the STL or the Java Collections library have started to take advantage of this work yet or not...

gwern 14y ago
Cache-oblivious algorithms can be pretty wacky when you're used to not thinking about locality at all. A mergesort can be understood by even a beginner after an hour or less in a language like Haskell. A funnelsort...? Well, I'll put it this way: even after reading the papers, I'm not sure how I would go about implementing it.
- mtdewcmu 14y ago
  I glanced at the code files from the inventor. It doesn't look like the kind of algorithm you implement yourself.
deleted 14y ago
[deleted]
gsg 14y ago
Most of the STL data structures guarantee stable element addresses, completely precluding any kind of cache-friendly rearrangement. They also require fast stable iterators that are cheap to pass by value, constraining the implementation further. For this reason I am fairly confident that every std::map/set ever written will be a balanced tree with parent pointers. There's just no latitude to do anything else.