3 ms·
The most surprising part of this to me was the speedup from replacing std::vector. They write, "We don’t need resize or push_back in our code, all arrays are i
by thestoicattack 8y ago
The most surprising part of this to me was the speedup from replacing std::vector.
They write, "We don’t need resize or push_back in our code, all arrays are initialized with the right size." But if you're not doing any resizing or anything, and you're reserving the right amount, std::vector basically is a thin wrapper over a dynamically-allocated raw array -- which is what they tout as their replacement.
I guess I'm surprised that the overhead from default initialization was so large.
With vector, it seems there are always tradeoffs: resize and you have some initialization overhead, but only reserve and you will have a bounds-check-maybe-realloc every time you need to push_back. Of course, since you reserved, the realloc never happens, but you still have to check each time.
I wonder if something like generate_n or copy_n into a back_inserter can avoid the bounds checks?
- jhasse 8y ago> std::vector basically is a thin wrapper over a dynamically-allocated raw array Not exactly. A dynamically-allocated array doesn't necessarily save its own size (the system allocator can do optimizations), but std::vector does (you could call size() on it). So std::vector has to save this size somewhere, which takes space and time.
- thestoicattack 8y agoFor me, the overhead of keeping track of size and capacity is still pretty thin. It's not like it's a linked list or something. The overhead is thin but non-zero.
- FartyMcFarter 8y agoThat overhead can be thin or heavy, depending on the operation. Doing "push_back" requires checking if "size < capacity", so this operation has a lot of overhead even for std::vector instances that never reallocate storage.
- MauranKilom 8y agoHere it would be great to see if the optimizer (which was only on O2 for unfathomable reasons) understands the reserve() beforehand to the point that it can eliminate those checks. You'd have to look at assembly for that.
- thestoicattack 8y agoI think Compiler Explorer shows that it usually doesn't, unfortunately.
- kccqzy 8y agoBranch prediction should eliminate that.
- FartyMcFarter 8y agoNot completely. I can still imagine a few overheads: - code size is bigger, taking up space in the cache and memory; - instructions need to be decoded (whether this affects performance depends on surrounding code); - this branch will take a slot in the branch predictor state (same here).
- je42 8y agoif you know the vector's size in advance then you would use just the operator[] + resize and not push_back + reserve. you would use push_back and reserve if you have a pretty good idea about the size but you can't depend on it.
- FartyMcFarter 8y agoThat has the overhead of initializing the entries (which may or may not be necessary). Apparently you can prevent this by using custom allocators, which might be a fine solution but makes the code look less idiomatic.