4 ms·

> Instead of "traverse" the author means you have to follow the pointer out to main memory to read the data. Another term they might have used is "fetch". No,

> Instead of "traverse" the author means you have to follow the pointer out to main memory to read the data. Another term they might have used is "fetch". No, I got that. But stack memory is main memory as well, and it is accessed through a pointer (in this case the stack pointer) just like heap memory. That is, unless the stack memory is not really stack memory, but optimized by the compiler to be register-only. Which is mostly not possible for stack-allocated arrays (when they are indexed with runtime indices, or when they are simply too large). It's true that stack memory is (almost) always in the cache, which is why stack memory is considered fast. But couldn't that be mostly true for temporary heap storage as well?

forrestthewoods 8y ago
When I said main memory I meant failing to get a cache hit. If you’re hitting the allocator (slow!) then odds are pretty good those bytes aren’t fresh in the cache. They could be if you just read them and then freed them and then the allocator handed them right back. But that’s probably not a good pattern either. Another form of this pattern is the small string optimization. It’s exceptionally common. https://blogs.msmvps.com/gdicanio/2016/11/17/the-small-string-optimization/ https://blogs.msmvps.com/gdicanio/2016/11/17/the-small-strin...
- chrisseaton 8y ago
  > If you’re hitting the allocator (slow!) then odds are pretty good those bytes aren’t fresh in the cache. Incidentally, this is a great reason why GCs are useful even if you don't need the automatic memory management - a GC can allocate from memory that is always in cache, and they can do it in a couple of cycles.
  - deleted 8y ago
    [deleted]
gpderetta 8y ago
Aside from cachability, there is still an extra indirection. If you have a std vector on the stack, to access the first element you need to dereference the stack poiner, at an offset, to fetch the heap pointer and then dereference it. The two loads are in a dependency chain. This is true for the first load at least. For subsequent loads the heap pointer might already be in a register. For a small vector you still need to dereference the stack pointer to load the heap pointer/discriminant, the perform a conditional jump on it, then, if the vector is stack allocated perform a further load at an offset from the stack pointer. Thanks to jump prediction, the second load does not depend on the first, so the dependency chain is shorter which might make a difference in some scenarios.
- jstimpfle 8y ago
  Honestly the SmallVector case sounds more complicated. As to the dependency chain in the standard vector version, the heap pointer should be easily put in a register. And the SmallVector has such a dependency just as well: The discrimant must be loaded and tested first. In both cases it shouldn't matter much since it's expected to be optimized to a one-time cost.
  - slavik81 8y ago
    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.

forrestthewoods 8y ago

When I said main memory I meant failing to get a cache hit. If you’re hitting the allocator (slow!) then odds are pretty good those bytes aren’t fresh in the cache. They could be if you just read them and then freed them and then the allocator handed them right back. But that’s probably not a good pattern either. Another form of this pattern is the small string optimization. It’s exceptionally common. https://blogs.msmvps.com/gdicanio/2016/11/17/the-small-string-optimization/ https://blogs.msmvps.com/gdicanio/2016/11/17/the-small-strin...

chrisseaton 8y ago
> If you’re hitting the allocator (slow!) then odds are pretty good those bytes aren’t fresh in the cache. Incidentally, this is a great reason why GCs are useful even if you don't need the automatic memory management - a GC can allocate from memory that is always in cache, and they can do it in a couple of cycles.
- deleted 8y ago
  [deleted]

gpderetta 8y ago

Aside from cachability, there is still an extra indirection. If you have a std vector on the stack, to access the first element you need to dereference the stack poiner, at an offset, to fetch the heap pointer and then dereference it. The two loads are in a dependency chain. This is true for the first load at least. For subsequent loads the heap pointer might already be in a register. For a small vector you still need to dereference the stack pointer to load the heap pointer/discriminant, the perform a conditional jump on it, then, if the vector is stack allocated perform a further load at an offset from the stack pointer. Thanks to jump prediction, the second load does not depend on the first, so the dependency chain is shorter which might make a difference in some scenarios.

jstimpfle 8y ago
Honestly the SmallVector case sounds more complicated. As to the dependency chain in the standard vector version, the heap pointer should be easily put in a register. And the SmallVector has such a dependency just as well: The discrimant must be loaded and tested first. In both cases it shouldn't matter much since it's expected to be optimized to a one-time cost.
- slavik81 8y ago
  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.