Russell Cohen | Maximize Cache Performance with this One Weird Trick: An Introduction to Cache-Oblivious Data Structures


24 bookmarks. First posted by absfac february 2018.


"Can we design data structures and algorithms that perform optimally regardless of underlying cache sizes?"

"A clearer name might be cache-size oblivious."

via https://news.ycombinator.com/item?id=16317613
algorithms  performance  cache 
february 2018 by pronoiac
If you read my recent post about Postgres you may have noted that Postgres operates primarily with fixed-size blocks of memory called “pages.” By default, Postgres pages are 8KB. This number is tuned to match operating system page sizes which are tuned to match hardware cache sizes.
getpocket 
february 2018 by linkt
storage engines for several major databases with significantly improved performance. Personally, I find theory working out in practice especially satisfying.
algorithm  cache  performance 
february 2018 by tebeka
Along these lines, today’s post explores the question:

Can we design data structures and algorithms that perform optimally regardless of underlying cache sizes?

If we could do this, our code would optimally utilize all cache layers without tuning. In academia, algorithms and data structures that have these properties are referred to as cache-oblivious. (This is a pretty confusing name. A clearer name might be cache-size oblivious.) I find cache-oblivious data structures very satisfying because they can yield huge performance gains in practice.
programming  algorithm  data-structures  optimization 
february 2018 by mayoff
If you read my recent post about Postgres you may have noted that Postgres operates primarily with fixed-size blocks of memory called “pages.” By default, Postgres pages are 8KB. This number is tuned to match operating system page sizes which are tuned to match hardware cache sizes. If you were to run Postgres on hardware with different cache sizes than Postgres was tuned for, you may be able to pick a better page size.
february 2018 by phutwo
Can we design data structures and algorithms that perform optimally regardless of underlying cache sizes?
postgres  performance  cache 
february 2018 by georgebashi
need to grok this more fully, also some refs at the end
data-structures  to-read 
february 2018 by absfac