4 ms·

> 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 an

> 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).

tialaramex 1y ago
> 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 1y ago
  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.
  - tialaramex 1y ago
    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 1y ago
      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 1y ago
        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 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.
        uecker 1y ago
        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...
        swinglock 1y ago
        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?
  - im3w1l 1y ago
    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 1y ago
      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 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.
ethan_smith 1y ago
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 1y ago

> 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 1y ago
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.
- tialaramex 1y ago
  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 1y ago
    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 1y ago
      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 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.
      - uecker 1y ago
        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...
        swinglock 1y ago
        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?
- im3w1l 1y ago
  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 1y ago
    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 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.

ethan_smith 1y ago

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.