Bounds Check Elimination with Fast-Range

[John Rose]

On Nov 18, 2019, at 8:43 PM, August Nagro <augustnagro at gmail.com> wrote:
> 
> And here’s a tangent to thing to think about: is growing HashMap’s backing array by powers of 2 actually a good thing, when the HashMap gets large? What if you instead wanted to grow by powers of 1.5, or even grow probabilistically, based on the collision rate, allocation pressure, or other data? With fast-range you can do this if you want. And without the performance hit of %!

It's an interesting tangent; let me follow you along it for a bit.

I think there may be interesting compromises between a size menu having only
powers of two and a size-to-order policy, or a menu of powers of bases not
related to 2, such as 1.5.  In particular, if you can manage a ratio near to 1.414
you can cut your fragmentation costs roughly in half by putting all powers of
2 on the menu, plus those values times 1.414.  (Or likewise a pair of multipliers
near to 1.260 and 1.587.)  If there were a clever ALU operation (or table lookup)
cheaper than a full multiply or remainder that would get the effect of a
fast range reduction just for the items on the menu, then it would be a
good trade-off to stick to the menu, where the discounts apply, rather
than pay for full-custom sizes.  Both 1.4 (7/5) and 1.5 (3/2) look attractively
simple, requiring some wrangling of approximate moduli of 3 or 5 or 7.
Or for 2^(1/3), 1.25 (5/4) and 1.66… (5/3)) are also simple ratios.  Or maybe
there is a non-obvious number (not a simple ratio) which has a surprisingly
simple modulus approximation—though I’m not holding my breath on that
one. Since I’m hoping to stay under the cost of a multiply, I admit it’s a
tight ceiling, but I think there might be something there between the
two extremes (2^n only and arbitrary sizes).

— John