For #148 @leerho discussed with me that computing the inverse powers of 2 is a very simple integer subtract and shift operation that is performed in one or two CPU clocks. It is extremely fast, can be inlined, and faster than any table lookup. No need to store a table. The Java code looks like this:
public static double invPow2(final int exp) {
if ((exp | (1024 - exp - 1)) < 0) {
throw new SketchesArgumentException("exp cannot be negative or greater than 1023: " + exp);
}
return Double.longBitsToDouble((1023L - exp) << 52);
}As in Rust, we define the exp as u8, it can be as simple as:
/// Compute 1 / 2^value (inverse power of 2)
#[inline]
fn inv_pow2(value: u8) -> f64 {
let value = (1023u64 - value as u64) << 52;
f64::from_bits(value)
}I think we can try to replace INVERSE_POWERS_OF_2[old_value as usize] with inv_pow2(old_value). But we'd better have a benchmark first to check if the inv_pow2 approach is significantly faster in Rust.
For #148 @leerho discussed with me that computing the inverse powers of 2 is a very simple integer subtract and shift operation that is performed in one or two CPU clocks. It is extremely fast, can be inlined, and faster than any table lookup. No need to store a table. The Java code looks like this:
As in Rust, we define the exp as
u8, it can be as simple as:I think we can try to replace
INVERSE_POWERS_OF_2[old_value as usize]withinv_pow2(old_value). But we'd better have a benchmark first to check if theinv_pow2approach is significantly faster in Rust.