28 ms·

I use doubling because it’s simple to reason about and hard to screw up the math. What kind of growth factors heuristics worked for you the best ? VPP: rather

by ay 4y ago

I use doubling because it’s simple to reason about and hard to screw up the math. What kind of growth factors heuristics worked for you the best ? VPP: rather fast user mode dataplane. https://fd.io/ https://fd.io/ is the “marketing” site. https://wiki.fd.io/view/VPP https://wiki.fd.io/view/VPP is the “less flashy” dev wiki.

Kranar 4y ago
The optimal growth factor is the golden ratio (1.6), in practice many vectors use a growth factor of 1.5. The reason for not going above the golden ratio is that it prevents any previously allocated memory from ever being reused. If you are always doubling the size of your vector, then it is never possible to reclaim/reuse any previously allocated memory (for that vector) which means every time your vector grows you are causing more and more memory fragmentation, as opposed to using a growth factor of 1.5 which results in memory compaction.
- llbeansandrice 4y ago
  Why does that happen when doubling size? I don’t understand
  - Kranar 4y ago
    Sure we can go over both cases: Case 1: Growth factor of 2 and an initial size of 10 bytes. Start with an initial allocation of 10 bytes of memory. On growth allocate 20 bytes and release the 10 bytes, leaving a hole 10 bytes. On growth allocate 40 bytes and release the 20 bytes, the hole in memory is now 30 bytes large (the initial 10 byte hole + the new 20 byte hole). On growth allocate 80 bytes and release the 40 bytes, the hole is now 60 bytes. On growth allocate 160 bytes and release the 80 bytes, the hole is now 140 bytes. So on so forth... using this strategy it is never possible for the dynamic array to reclaim the hole it left behind in memory. Case 2: Growth factor of 1.5 and an initial size of 10 bytes. Start with an initial allocation of 10 bytes of memory. On growth allocate 15 bytes and release the 10 bytes, leaving a hole 10 bytes. On growth allocate 22 bytes and release the 15 bytes, the hole in memory is now 25 bytes large (the initial 10 byte hole + the new 15 byte hole). On growth allocate 33 bytes and release the 22 bytes, the hole is now 47 bytes. On growth allocate 50 bytes and release the 33 bytes, the hole is now 80 bytes. On growth reuse 75 bytes from the hole in memory left over from previous growths, the hole is now 5 bytes. With a growth factor of 1.5 (or anything less than the golden ratio), the hole grows up to a point and then shrinks, grows and shrinks, allowing the dynamic array to reuse memory from past allocations. With a growth factor of 2, the hole in memory continues to grow and grow and grow.
    - sfink 4y ago
      This appears to assume that there will be no intervening allocations that are allowed to use the same region of memory, since otherwise your "hole" will be very discontiguous. But if that is the case, then why are you releasing memory? That's just costing you time moving the data. With a doubling mechanism: Start with an initial allocation of 10 bytes of memory. On growth allocate another 10, and don't copy anything, leaving no hole at all. On growth allocate another 20, and don't copy anything, leaving no hole at all. etc. In what scenario would the growth factor of 1.5 actually help? If you're restricting the allocation API to only malloc then you can't grow the size of your allocation and what you said might make sense as something the allocator could take advantage of internally. But realloc exists, and will hopefully try to extend an existing allocation if possible. (If your earlier allocation was fairly small, then the allocator might have put it in an arena for fixed-size allocations so it won't be possible to merge two of them, but once things get big they generally get their own VMA area. Obviously totally dependent on the allocator implementation, and there are many.)
    - Dylan16807 4y ago
      99.9% of the time, each allocation leaves a separate hole. Your goal is to enable other allocations to use those holes without further splitting them, not to get your ever-growing vector to reuse memory.
sfink 4y ago
I usually use doubling, but I just recently landed a patch to expand by a factor of 8 instead, which sped up a microbenchmark (of constructing a JSON string, fwiw) by 50%. Someone saw in a profile that we were spending a lot of time in realloc in a task that involved building a string in contiguous memory. But the final string was realloc'd down to its actual size, so it was safe to get a lot more aggressive with the growth to avoid copying. The overhead was only temporary. It turns out that powers of 8 get big fast, so there are now many fewer copies and the few that happen are copying a small portion of the overall data, before a final octupling that provided mostly unused space that didn't cost much. Know your problem, I guess?
- ay 4y ago
  Very interesting. And indeed, especially being adjacent with the very interesting “golden ratio” comment, this shows that there is more than one definition of “best” dependent on the task, and that one always needs to verify their hunch by actual profiling.

by ay 4y ago

Kranar 4y ago

The optimal growth factor is the golden ratio (1.6), in practice many vectors use a growth factor of 1.5. The reason for not going above the golden ratio is that it prevents any previously allocated memory from ever being reused. If you are always doubling the size of your vector, then it is never possible to reclaim/reuse any previously allocated memory (for that vector) which means every time your vector grows you are causing more and more memory fragmentation, as opposed to using a growth factor of 1.5 which results in memory compaction.

llbeansandrice 4y ago
Why does that happen when doubling size? I don’t understand
- Kranar 4y ago
  Sure we can go over both cases: Case 1: Growth factor of 2 and an initial size of 10 bytes. Start with an initial allocation of 10 bytes of memory. On growth allocate 20 bytes and release the 10 bytes, leaving a hole 10 bytes. On growth allocate 40 bytes and release the 20 bytes, the hole in memory is now 30 bytes large (the initial 10 byte hole + the new 20 byte hole). On growth allocate 80 bytes and release the 40 bytes, the hole is now 60 bytes. On growth allocate 160 bytes and release the 80 bytes, the hole is now 140 bytes. So on so forth... using this strategy it is never possible for the dynamic array to reclaim the hole it left behind in memory. Case 2: Growth factor of 1.5 and an initial size of 10 bytes. Start with an initial allocation of 10 bytes of memory. On growth allocate 15 bytes and release the 10 bytes, leaving a hole 10 bytes. On growth allocate 22 bytes and release the 15 bytes, the hole in memory is now 25 bytes large (the initial 10 byte hole + the new 15 byte hole). On growth allocate 33 bytes and release the 22 bytes, the hole is now 47 bytes. On growth allocate 50 bytes and release the 33 bytes, the hole is now 80 bytes. On growth reuse 75 bytes from the hole in memory left over from previous growths, the hole is now 5 bytes. With a growth factor of 1.5 (or anything less than the golden ratio), the hole grows up to a point and then shrinks, grows and shrinks, allowing the dynamic array to reuse memory from past allocations. With a growth factor of 2, the hole in memory continues to grow and grow and grow.
  - sfink 4y ago
    This appears to assume that there will be no intervening allocations that are allowed to use the same region of memory, since otherwise your "hole" will be very discontiguous. But if that is the case, then why are you releasing memory? That's just costing you time moving the data. With a doubling mechanism: Start with an initial allocation of 10 bytes of memory. On growth allocate another 10, and don't copy anything, leaving no hole at all. On growth allocate another 20, and don't copy anything, leaving no hole at all. etc. In what scenario would the growth factor of 1.5 actually help? If you're restricting the allocation API to only malloc then you can't grow the size of your allocation and what you said might make sense as something the allocator could take advantage of internally. But realloc exists, and will hopefully try to extend an existing allocation if possible. (If your earlier allocation was fairly small, then the allocator might have put it in an arena for fixed-size allocations so it won't be possible to merge two of them, but once things get big they generally get their own VMA area. Obviously totally dependent on the allocator implementation, and there are many.)
  - Dylan16807 4y ago
    99.9% of the time, each allocation leaves a separate hole. Your goal is to enable other allocations to use those holes without further splitting them, not to get your ever-growing vector to reuse memory.

sfink 4y ago

I usually use doubling, but I just recently landed a patch to expand by a factor of 8 instead, which sped up a microbenchmark (of constructing a JSON string, fwiw) by 50%. Someone saw in a profile that we were spending a lot of time in realloc in a task that involved building a string in contiguous memory. But the final string was realloc'd down to its actual size, so it was safe to get a lot more aggressive with the growth to avoid copying. The overhead was only temporary. It turns out that powers of 8 get big fast, so there are now many fewer copies and the few that happen are copying a small portion of the overall data, before a final octupling that provided mostly unused space that didn't cost much. Know your problem, I guess?

ay 4y ago
Very interesting. And indeed, especially being adjacent with the very interesting “golden ratio” comment, this shows that there is more than one definition of “best” dependent on the task, and that one always needs to verify their hunch by actual profiling.