Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Exactly! Why would I want to add my own memory management logic on top of the memory management logic that already exist.

One valid reason might be that I can't rely on realloc not be poor, but then I would rather use my own special allocation function. Other valid reasons would be to have very precise control or certain guarantees, but then I would prefer a different interface. In any case, I do not think that this logic belongs into my vector. But it is also possible that I change my mind on this...



As you said in the article, the reason is performance and that stands even if a realloc implementation is not poor.

It can't preallocate, so when adding many items it will make many expensive realloc calls that could have been avoided. Though you could have an interface that allows pushing or popping many items at once to make up for it, but this is less convenient.

You can currently forgo shrinking on pop but you can't if mixing popping and pushing. You need to know the capacity for that, otherwise it may actually shrink on a consequent push. This could incur many expensive reallocs if used similarly to a stack.

Even the cheap realloc calls will cost more than checking an int in code that's likely small, inlined, and with its data in one cache line (number of items and capacity next to each other in one struct, which are also next to the first item). The realloc function is probably dynamically linked, more complex, and has to access additional data.

If you don't want to add more memory overhead to the vector, consider just using two ints and it won't be any larger, that's enough unless a vector should be many gigabytes. Otherwise if you think that's not enough and feel like leaning into the complexity instead, use bit fields or bit twiddling to split up one 64 bit int into say, 56+8 bit ints. Let the smaller int track additional capacity rather than total capacity and also use that to solve your hysteresis problem. Well, or just use two 64 bit ints, but what's the fun in that?


When I implemented this, I did some minimal benchmarking. Realloc was easily fast enough to cover all my use cases. I am not Facebook who need to optimize the single last byte of their string type. For the fast case, there is the alternative API which allows one to keep track of the capacity, without having the cost of storing it in the type.

But realloc also does overallocate a little bit, and for large blocks it would remap the pages. The inlining argument makes sense though. (Edit: Pushing and then popping a billion integers takes about 2 seconds with std::vector<int>, 10 with vec(int) and realloc each time, and 4.3 seconds with a simple preallocation logic that does not require a capacity on my laptop. Having a call to "rand" in it already adds more overhead.).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: