4 ms·

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.

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.