3 ms·
Sure, the penality is only usually paid for the access to the vector, unless the compiler need to spill the heap pointer. The branch predicated on the test is
by gpderetta 8y ago
Sure, the penality is only usually paid for the access to the vector, unless the compiler need to spill the heap pointer.
The branch predicated on the test is executed speculatively, so the next load does not actually depended on the discriminant load and test so the dependency chain is actually shorter (1 load instead of two). If the code is bottlenecked by something other than the dependency chain length (for example number of outstanding loads) of course it doesn't matter, but dependency chains are usually the first bottleneck.
- jstimpfle 8y agoThis is insightful. Thanks.
- gpderetta 8y agoThanks. Mind you, that's the theory, I haven't actually benchmarked the use case. But in general reducing the length of pointer chains to traverse is an often low hanging fruits of performance optimizations.
- jstimpfle 8y agoI've just noticed that while the thing you mentioned about branch prediction might well often work out, nevertheless the compiler needs to emit additional object code for the discrimation test whenever it cannot infer whether an access is "small" or "large". It might mean a significant increase in code size. Of course I didn't measure anything, either.
- BeeOnRope 8y agoIt depends on the implementation. Using a discriminant plus branch is one way to do it, but another implementation is to just always use a data pointer, which points into the embedded array in the small vector case. Now there is no branch and in fact the element access code is identical to std::vector case. Only a few, less frequently called paths need to be aware of the small vs large cases, such as the resize code (which needs to not free the embedded buffer). The main downsides are that you have added back the indirection in the small vector case (indirection is unconditional), and that you "waste" the 8 bytes for the data pointer in the small case, as the discriminant version can reuse that for vector data. IMO the observed performance improvements are basically 100% due to the avoidance of malloc and in the real world (but not this benchmark) due to better cache friendliness of on-stack data, but not because any vector functions such as element access are substantially sped up. That explains why the benefits disappear (in a relative sense) pretty quickly as the element size increases, even for the large-embedded-buffer case where all of the elements are still on the stack: the malloc benefit is (roughly) a one-time benefit per vector, not a "per access" or "per element" benefit so as the vector grows, the relative benefit diminishes and the non-malloc operation costs come to dominate.