[rswier]

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

[zgs]

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.

[newaccount74]

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

[stephencanon]

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

[newaccount74]

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

[twic]

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!