4 ms·

Could you elaborate on the "nearby areas of RAM" part? From what I've been learning, cache lines are only 64 bytes, so if you can't fit things in the same 64 by

Could you elaborate on the "nearby areas of RAM" part? From what I've been learning, cache lines are only 64 bytes, so if you can't fit things in the same 64 bytes then it's not worth thinking about. What am I missing?

Const-me 8y ago
1. If these structures take 100 bytes, they will span 2-3 cache lines. You access an item, CPU caches these 2-3 lines. If shortly after that you access the neighbor one because your algorithm walked the tree/graph pointers and come to a neighbor item, you save some RAM latency. If these items are 1MB/each the win will be very small, but for small structures the performance difference can be huge. 2. MMUs in modern CPUs have prefetcher silicon in it. If the CPU detects you’re doing something resembling sequential access, it will prefetch more cache lines after that. 3. Modern CPUs also have TLBs https://en.wikipedia.org/wiki/Translation_lookaside_buffer https://en.wikipedia.org/wiki/Translation_lookaside_buffer Accessing data within the same page (platform-specific, on Windows often 4kb) is faster that accessing random locations because the virtual address->physical address mapping for that page will be in the cache. 4. Last but not least, with small arenas per tree/graph memory allocations and deallocations will be faster than even jemalloc, from the point of view of C runtime you’ll only call malloc/free once per graph, not once per item. Look at the data in my repository: https://github.com/Const-me/CollectionMicrobench https://github.com/Const-me/CollectionMicrobench As you see, adding my custom allocator to these standard C++ collections improved performance substantially. Update: also, with 1 arena per tree, it becomes orders of magnitude faster to copy the tree. You just memcpy and then sequentially walk through the arena adjusting the pointers. Or combine both in a single step.

Const-me 8y ago

1. If these structures take 100 bytes, they will span 2-3 cache lines. You access an item, CPU caches these 2-3 lines. If shortly after that you access the neighbor one because your algorithm walked the tree/graph pointers and come to a neighbor item, you save some RAM latency. If these items are 1MB/each the win will be very small, but for small structures the performance difference can be huge. 2. MMUs in modern CPUs have prefetcher silicon in it. If the CPU detects you’re doing something resembling sequential access, it will prefetch more cache lines after that. 3. Modern CPUs also have TLBs https://en.wikipedia.org/wiki/Translation_lookaside_buffer https://en.wikipedia.org/wiki/Translation_lookaside_buffer Accessing data within the same page (platform-specific, on Windows often 4kb) is faster that accessing random locations because the virtual address->physical address mapping for that page will be in the cache. 4. Last but not least, with small arenas per tree/graph memory allocations and deallocations will be faster than even jemalloc, from the point of view of C runtime you’ll only call malloc/free once per graph, not once per item. Look at the data in my repository: https://github.com/Const-me/CollectionMicrobench https://github.com/Const-me/CollectionMicrobench As you see, adding my custom allocator to these standard C++ collections improved performance substantially. Update: also, with 1 arena per tree, it becomes orders of magnitude faster to copy the tree. You just memcpy and then sequentially walk through the arena adjusting the pointers. Or combine both in a single step.