Hacker News Reader

Comment by rswier | Hacker News Reader

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

View on HN

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

If the multiplier is less than the golden ratio, then the new allocation fits into the memory released from the previous two allocations.

But most allocators will not actually take advantage of that, so it’s a pretty dubious argument.

Good point, I haven't actually checked if any realloc implementations do that.

I 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!

Reply on news.ycombinator.com