Hacker Neue

Preferences
petters parent
> Many vector types include a capacity field, so that resizing on every push can be avoided. I do not include one, because simplicity is more important to me and realloc often does this already internally. In most scenarios, the performance is already good enough.

I think this is the wrong decision (for a generic array library).

ethan_smith
Without a capacity field, each push operation potentially triggers a realloc, causing O(n) copying and possible memory fragmentation - especially problematic for large vectors or performance-critical code.
tialaramex
> realloc often does this already internally

Is Martin claiming that realloc is "often" maintaining a O(1) growable array for us?

That's what the analogous types in C++ or Rust, or indeed Java, Go, C# etc. provide.

uecker
No, I claim that the performance of realloc is good enough for most use cases because it also does not move the memory in case there is already enough space left.

I then mention that for other use cases, you can maintain a capacity field only in the part of the code where you need this.

Whether this is the right design for everybody, I do not know, but so far it is what I prefer for myself.

im3w1l
I think it's a very interesting design choice. I haven't read the code, so maybe you already thought of this, but one idea that comes to mind is that instead of reallocing new_size, you realloc f(new_size) where f is some function that rounds up to discrete steps. This should ensure good asymptotics as realloc can then realize that the requested allocation size is identical to the current one and nothing needs to be done.

However one possible issue is if someone pushes and pops repeated just at the boundary where f increases in value. To address that you would have to use more advanced techniques, and I think "cheat" by inspecting internal structures of the allocator.

Edit: malloc_usable_size could be used for this purpose I think.

uecker
Yes!

I try do this here (this code is not tested and may not be up-to-date): https://github.com/uecker/noplate/blob/main/src/vec.h#L30

The issue with the boundary is what I meant with hysteresis in the article.

tialaramex
I think the claim that it's good enough for "most use cases" to have an O(n) growable array container needs some serious backing data.
uecker
If I have some time, I will do some benchmarking.

In all my current code where I tried it makes no noticeable difference, and I am not a fan of premature optimization. But then, I could always switch to the alternative API.

swinglock
Popular allocators will indeed grow your allocation in-place without moving when possible. This is essentially the same as if you'd tracked it yourself in your vector and grown it once in a while, though it will work with bytes instead of number of items. See for instance the size classes in jemalloc at https://jemalloc.net/jemalloc.3.html. If you ask for 1 byte, you actually have 8 bytes, so realloc within the same size class will be cheap compared to actually moving.
3 More Comments →

This item has no comments currently.

Keyboard Shortcuts

Story Lists

j
Next story
k
Previous story
Shift+j
Last story
Shift+k
First story
o Enter
Go to story URL
c
Go to comments
u
Go to author

Navigation

Shift+t
Go to top stories
Shift+n
Go to new stories
Shift+b
Go to best stories
Shift+a
Go to Ask HN
Shift+s
Go to Show HN

Miscellaneous

?
Show this modal