Cache Oblivious Algorithms
jiahai-feng.github.io
Cache Oblivious Algorithms
1–10 of 21 posts
Re: Cache Oblivious Algorithms
#2I implemented a bunch of cache oblivious search trees and benchmarked them against their classical counterparts. The results showed that while the cache oblivious ones were more cache efficient, they were slower overall.
The implementations and benchmarks can be found here if anyone is curious: https://gitlab.com/VladLazar/cache-oblivious-data-structures
Re: Cache Oblivious Algorithms
#3I implemented a bunch of cache oblivious search trees and benchmarked them against their classical counterparts. The results showed that while the cache oblivious ones were more cache efficient, they were slower overall. The implementations and benchmarks can be found here if anyone is curious: https://gitlab.com/VladLazar/cache-oblivious-data-structures
Your readme lists the cache-oblivious data structures you tested. But, it would be nice to also list what baselines you tested them against. I’m curious if they were explicitly cache-aware.
Re: Cache Oblivious Algorithms
#4I tried cache-oblivious algorithms for some numerical code, but found them underwhelming. The cache-oblivious model does not consider the effects of prefetching and cache line associativity. Both can make a huge difference.
They are a great starting point and work well for the RAM/Swap level of the memory hierarchy, but for the L1/L2 caches manual tuning still pays off. This unfortunately makes the implementation non-oblivious and even depended on the specific CPU used.
Re: Cache Oblivious Algorithms
#5I'd not heard about van Emde Boas layout before, and it sounds super cool! I wish the author had included a simple example before focussing on the general case -- I find it hard to get an intuition for the general without a specific example! In particular, after some searching, I found the diagram at the top-left of page 4 of https://www.cs.au.dk/~gerth/papers/soda02.pdf to be immensely helpful in getting my head around the concept.
Re: Cache Oblivious Algorithms
#6I remember my professor Michael Bender teaching those M/B stuff and it was interesting (somehow related to origami). Sadly I pretty much forgot everything now.
Re: Cache Oblivious Algorithms
#7I think there might be a mistake in this article, or at least something requiring clarification.
> For convenience, suppose the binary tree is complete and has height H=2^K.
What is K? It's never stated. I'd usually assume H = log N, if N is the number of nodes in a balanced tree.
Re: Cache Oblivious Algorithms
#8I think there might be a mistake in this article, or at least something requiring clarification. > For convenience, suppose the binary tree is complete and has height H=2^K. What is K? It's never stated. I'd usually assume H = log N, if N is the number of nodes in a balanced tree.
I think K is just an arbitrary natural number. The author is assuming the height is a power of 2, and giving the name K to the log_2 of that height.
Re: Cache Oblivious Algorithms
#9[deleted]
Re: Cache Oblivious Algorithms
#10Don’t most CPUs have 64 byte cache lines anyway?