Cache-Line Aware Data Structures | Hacker News Reader

Cache-Line Aware Data Structures

accu.org

123 pointsingve4 comments

This is cool. I especially appreciate the disclaimer at the end:

>> We can’t stress enough how important it is to measure your applications and the tools used to measure those applications.

In general, hardware-oriented data-structure design is really appropriate for organizations with:

1. Large server workloads that exercise the data structure frequently.

2. Fine-grained control of what hardware they're using.

3. Very very good continuous profiling and monitoring of the production workload.

I often see #3 missing when people propose writing their own hash table or whatever, but it's an essential prerequisite. These days, serious wins tend to come from making large assumptions (X instructions will get vectorized, Y access pattern dominates) and specializing your implementation to them.

OTOH you can make pretty sweeping generalizations. For example, FreeBSD recently shuffled the members of the TCP structures around to line up assuming 64B boundaries and mitigate some of the false sharing associated with locks and memory barriers (locking implementations usually cause a complete cacheline Read-Modify-Write that has to be communicated over the cache coherence protocol potentially xxx ns away). For large structures, putting things in the first or second part (64 to 128B) will generally get you cache hits due to prefetching so it can behave somewhat ganged in practice as well. If you have something designed for 64B lines that doesn't work in a linear fashion, the prefetcher may be wasting a lot of bandwidth. https://www.akkadia.org/drepper/cpumemory.pdf

Cached:

https://web.archive.org/web/20180813200145/http://accu.org/i...

Additional material for data-oriented design:

https://github.com/dbartolini/data-oriented-design

Also liked this similar post a while back about optimizing varnish's binary heap for better page/cache use: https://queue.acm.org/detail.cfm?id=1814327

Reply on news.ycombinator.com