4 ms·
I would recommend this book https://en.algorithmica.org/ https://en.algorithmica.org/. My opinion on things is that cache-oblivious programming is dead end an
by anonymoushn 3y ago
I would recommend this book https://en.algorithmica.org/ https://en.algorithmica.org/.
My opinion on things is that cache-oblivious programming is dead end and the constant factors by which cache-aware algorithms win are significant and worth taking.
- vlmutolo 3y agoCounterintuitively, “Cache-oblivious” algorithms typically refer to algorithms that are cache-friendly even for an unknown cache size, or for multiple levels of caches of varying (unknown) sizes. A good example is the memory hierarchy, from registers to L1–L3 processor cache to RAM to disk. Each have their own “block” size for memory transfers, and a cache-oblivious algorithm is designed to target all of those block sizes simultaneously. https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm
- anonymoushn 3y agoYes, that's correct, and specializing your code to the actual cache line and page sizes will generally yield significant speedups compared to this approach.