8 ms·
Cache-Line Aware Data Structures
- faragon 8y agoCached: https://web.archive.org/web/20180813200145/http://accu.org/index.php/journals/2535 https://web.archive.org/web/20180813200145/http://accu.org/i... Additional material for data-oriented design: https://github.com/dbartolini/data-oriented-design https://github.com/dbartolini/data-oriented-design
- senatorobama 8y ago
- shafte 8y agoThis 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.
- kev009 8y agoOTOH 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 https://www.akkadia.org/drepper/cpumemory.pdf
- parhamn 8y agoAlso 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 https://queue.acm.org/detail.cfm?id=1814327