Radix root model not working with small branching factor

[marcelmaltry]

Hi, I recently tried to build a model with a radix layer and noticed that radix models do not work with small branching factors (1, 2, 3), e.g.

cargo run --release -- uniform_dense_200M_uint64 sosd_rmi radix,linear 1

I always get an error similar to this:

thread '<unnamed>' panicked at 'Top model gave an index of 2954937499648 which is out of bounds of 2. Subset range: 1 to 200000000', /private/tmp/rust-20200803-28615-1977jkb/rustc-1.45.2-src/src/libstd/macros.rs:16:9

I suspect that the issue stems from models::utils::num_bits. I guess you are computing the amount of bits that are needed to represent the largest index (while loop) and then substract 1 to ensure that the radix model always predicts an index smaller than the branching_factor. However, your implementation appears to be off by 1, i.e. the additional nbits -= 1 is not needed.

[ImmanuelHaffner]

I suppose a simpler (and faster) solution to computing the number of bits required can be found here. While this gives you floor(log2(x)), we can use it to implement ceil(log2(x)) as floor(log2(x - 1)) + 1. The code for your case of 64 bit integers would then be

64 - (largest_target - 1).leading_zeros()

[RyanMarcus]

Hm, that's a strange one. I have no idea what I was thinking when I wrote that code!

Any two-layer RMI with only a single leaf node is the same as a one-layer RMI, so the code should catch that and warn the user as well.