3 ms·

The thing is that a cache line is 64 bytes, and loading from main memory to cache is orders of magnitude slower than from cache to register. In the std::vector

The thing is that a cache line is 64 bytes, and loading from main memory to cache is orders of magnitude slower than from cache to register. In the std::vector case, it's loading 64 bytes into cache just to get the heap pointer. Then the heap pointer tells it which other 64 bytes to load. In the SmallVector case, the 64 bytes that contain the heap pointer are likely to include the entire vector, entirely eliminating the second load.

jstimpfle 8y ago
Since it's stack memory, in both cases you can assume that the struct (whether or not including a small-array) is already loaded in the cache. The question is can't you achieve that the heap memory of the vector version is also in the cache if you just care a tiny little bit about data organization.
- BeeOnRope 8y ago
  Sure, it can be the case that both the data and the vector struct are in cache (in different lines). Analyses like "stack is in cache, but heap is in main memory" are too simple to capture the subtleties of real programs. In general, for a benchmark, you can expect everything to be in cache, unless the data is large enough that it doesn't fit, which usually means that it won't fit regardless of small-vector optimization or not. That said, purely from a memory access and cache use point of view, it is more or less strictly better to pack all the vector data (data and metadata) together as the small vector does: you'll always only bring in the one cache line containing everything. In the split stack + heap case [1], sure both lines might be cache, so the access time might be the same, but you still need to have both of those lines in the cache, so the footprint is bigger. So at beast it can be "tied", but at some point you'll suffer misses with this strategy that you wouldn't suffer if everything were co-located. It follows directly from the general rule that you want to pack data accessed together close together. --- [1] Of course it might be heap + heap since the std::vector itself might be allocated on the heap but it doesn't really change the analysis.

jstimpfle 8y ago

Since it's stack memory, in both cases you can assume that the struct (whether or not including a small-array) is already loaded in the cache. The question is can't you achieve that the heap memory of the vector version is also in the cache if you just care a tiny little bit about data organization.

BeeOnRope 8y ago
Sure, it can be the case that both the data and the vector struct are in cache (in different lines). Analyses like "stack is in cache, but heap is in main memory" are too simple to capture the subtleties of real programs. In general, for a benchmark, you can expect everything to be in cache, unless the data is large enough that it doesn't fit, which usually means that it won't fit regardless of small-vector optimization or not. That said, purely from a memory access and cache use point of view, it is more or less strictly better to pack all the vector data (data and metadata) together as the small vector does: you'll always only bring in the one cache line containing everything. In the split stack + heap case [1], sure both lines might be cache, so the access time might be the same, but you still need to have both of those lines in the cache, so the footprint is bigger. So at beast it can be "tied", but at some point you'll suffer misses with this strategy that you wouldn't suffer if everything were co-located. It follows directly from the general rule that you want to pack data accessed together close together. --- [1] Of course it might be heap + heap since the std::vector itself might be allocated on the heap but it doesn't really change the analysis.