4 ms·
> I suspect there is some clever base between 1 and 2 which is trivial to compute Something like this perhaps (although this might be too much granularity):
by rswier 5y ago
> I suspect there is some clever base between 1 and 2 which is trivial to compute
Something like this perhaps (although this might be too much granularity):
(8 + (cap & 7)) << ((cap >> 3) + 1)
16 18 20 ... 30
32 36 40 ... 60
64 72 80 ... 120
128 ... etc.
- twic 5y agoI thought, oh, you only need two bits for the multiplier, that gives you four multiples of each tier size, that should be enough. But that means the largest buffer (with a slightly less sophisticated formula than yours) is ((2 << 2) * 2 << (2 <<(8 - 2) - 1)) = 32 exabytes. Meanwhile, yours has a maximum of 60 GB. So i don't think you have too much granularity!
- zgs 5y agoI remember seeing a paper that concluded the expansion should not be more than the golden ratio (ϕ = 1.618033988749). Given how widespread the golden ratio, I'd hypothesise that it's probably optimal. The first three fractions approximating ϕ are: 3/2, 8/5 and 21/13. The first two are quick and easy to compute.
- newaccount74 5y agoIf the multiplier is less than the golden ratio, then the new allocation fits into the memory released from the previous two allocations.
- stephencanon 5y agoBut most allocators will not actually take advantage of that, so it’s a pretty dubious argument.
- newaccount74 5y agoGood point, I haven't actually checked if any realloc implementations do that.