7 ms·
Memory allocation by STL has been broken for as long as I remember, which is at least twelve years or so. It's been a while but if I remember correctly it doubl
by BurnGpuBurn 8y ago
Memory allocation by STL has been broken for as long as I remember, which is at least twelve years or so. It's been a while but if I remember correctly it doubled its allocation every time it ran out or space.
- NullPrefix 8y agothis is implementation specific. Care to tell which compiler are you talking about?
- jcelerier 8y ago> It's been a while but if I remember correctly it doubled its allocation every time it ran out or space. why would you call this "broken" ? That's one of the most optimal solutions for reallocations if you append values continuously, since it will reallocate only logarithmically.
- gmadsen 8y agowhat? ha, that is the text book approach to reallocating an array for additional values to get log complexity
- vardump 8y agoI'm not so sure I'd want a 2GB vector to grow to 4GB, etc.
- jhasse 8y agoWhy not?
- dbaupp 8y agoO(n^2) time for n push_back calls would be worse, so some sort of multiplication/exponential growth is required for the "fits all" default vector and its default growth strategy.
- BeeOnRope 8y agoOld versions of MSVC used a 3/2 growth factor which led to less extreme jumps for large vectors, although also a lot more copies when filling a small vector. I'm not sure if that's still true.
- ChrisSD 8y agoIn such extreme cases you can (and should) use your own allocation strategy.
- vardump 8y agoYeah, but I'm not entirely clear how I'd for example get std::vector to use a mmap'ed range, that I could zero-copy grow. Also in that case I might want to grow it by a fixed amount, once it grows past a certain threshold. It's a shame one needs to write another vector implementation just for that.
- ChrisSD 8y agoWhy wouldn't writing an allocator class be enough for mmap?
- BeeOnRope 8y agoProbably not, because the allocators don't expose the "extend" or "realloc" concept, so all you'll see from within your allocator is a request for an entire new region that vector wants in order to copy the new stuff into. To implement a growing allocation , you'll have to create a custom vector, pretty much.
- Timmah 8y agoHow would you ensure nothing was used in the region after the original allocation?
- mortehu 8y agoI think you mean amortized constant complexity, or O(1).
- EpicEng 8y agoWhich libs _don't_ use that allocation strategy? The fact that you think it's broken only means you don't really know what you're talking about.
- deleted 8y ago[deleted]