I implemented what you describe using the BSR (BitScanReverse) instruction as base of an indirect addressing of an exponentially growing data size.

Essentially, instead of a direct addressing like V[i], you can do VV[log2(i)][i]. Where log2() is implemented with a single BSR instruction.

The addressing table for the first level is very small in size, and it can be assumed always in cache.

Here the .h/.c source: https://github.com/amadvance/tommyds/blob/master/tommyds/tom...

https://github.com/amadvance/tommyds/blob/master/tommyds/tom...

Did you used something different ?