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

17 bookmarks. First posted by absfac 16 days ago.

storage engines for several major databases with significantly improved performance. Personally, I find theory working out in practice especially satisfying.
algorithm  cache  performance 
10 days ago 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 
16 days ago 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.
16 days ago by phutwo
need to grok this more fully, also some refs at the end
data-structures  to-read 
16 days ago by absfac