Code for benchmarking all the implementations of the cardinality extimations of hyperloglog

bench.rs

#![feature(test)]
extern crate test;

use test::{black_box, Bencher};
// Optionally include some setup
const NUMBER_OF_ELEMENTS: usize = 10_000;
const BITS: usize = 5;

fn gen_data() -> Vec<u8> {
    let mut res = Vec::with_capacity(NUMBER_OF_ELEMENTS);
    let mut x = 0x4e3bdb5ddde78274_u64;
    for _ in 0..NUMBER_OF_ELEMENTS {
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;

        res.push(
            (x & ((1 << BITS) - 1)) as u8
        );
    }
    res
}

#[bench]
fn bench_v1(b: &mut Bencher) {
    let values = gen_data();
    b.iter(|| {
        // Inner closure, the actual test
        v1(black_box(&values))
    });
}
#[bench]
fn bench_v2(b: &mut Bencher) {
    let values = gen_data();
    b.iter(|| {
        // Inner closure, the actual test
        v2(black_box(&values))
    });
}
#[bench]
fn bench_v3(b: &mut Bencher) {
    let values = gen_data();
    b.iter(|| {
        // Inner closure, the actual test
        v3(black_box(&values))
    });
}
#[bench]
fn bench_v4(b: &mut Bencher) {
    let values = gen_data();
    b.iter(|| {
        // Inner closure, the actual test
        v4(black_box(&values))
    });
}
#[bench]
fn bench_v5(b: &mut Bencher) {
    let values = gen_data();
    b.iter(|| {
        // Inner closure, the actual test
        v5(black_box(&values))
    });
}

pub fn v1(values: &[u8]) -> f32 {
    let mut total: f32 = 0.0;
    for value in values {
        total += 1.0 / 2.0_f32.powf(*value as f32);
    }
    total
}


pub fn v2(values: &[u8]) -> f32 {
    let mut total: f32 = 0.0;
    for value in values {
        total += 1.0 / ((1 << *value) as f32);
    }
    total
}

pub fn v3(values: &[u8]) -> f32 {
    let mut total: f32 = 0.0;
    for value in values {
        total += RECIPROCALS_TABLE[*value as usize];
    }
    total
}

pub fn v4(values: &[u8]) -> f32 {
    let mut total: f32 = 0.0;
    for value in values {
        let hack = (127 + *value as u32) << 23;
        total += f32::from_ne_bytes(hack.to_ne_bytes());
    }
    total
}

pub fn v5(values: &[u8]) -> f32 {
    let mut counter: u64 = 0;
    for value in values {
        counter += (1_u64 << 32) >> *value;
    }
    let exp = counter.leading_zeros() + 1;
    counter <<= exp;
    counter >>= 64 - 23;
    let res = (((127 + 32 - exp) as u32) << 23) | (counter as u32);
    f32::from_ne_bytes(res.to_ne_bytes())
}

const RECIPROCALS_TABLE: &[f32] = &[
    1.0,
    0.5,
    0.25,
    0.125,
    0.0625,
    0.03125,
    0.015625,
    0.0078125,
    0.00390625,
    0.001953125,
    0.0009765625,
    0.00048828125,
    0.000244140625,
    0.0001220703125,
    6.103515625e-05,
    3.0517578125e-05,
    1.52587890625e-05,
    7.62939453125e-06,
    3.814697265625e-06,
    1.9073486328125e-06,
    9.5367431640625e-07,
    4.76837158203125e-07,
    2.384185791015625e-07,
    1.1920928955078125e-07,
    5.960464477539063e-08,
    2.9802322387695312e-08,
    1.4901161193847656e-08,
    7.450580596923828e-09,
    3.725290298461914e-09,
    1.862645149230957e-09,
    9.313225746154785e-10,
    4.656612873077393e-10,
    2.3283064365386963e-10,
    1.1641532182693481e-10,
    5.820766091346741e-11,
    2.9103830456733704e-11,
    1.4551915228366852e-11,
    7.275957614183426e-12,
    3.637978807091713e-12,
    1.8189894035458565e-12,
    9.094947017729282e-13,
    4.547473508864641e-13,
    2.2737367544323206e-13,
    1.1368683772161603e-13,
    5.684341886080802e-14,
    2.842170943040401e-14,
    1.4210854715202004e-14,
    7.105427357601002e-15,
    3.552713678800501e-15,
    1.7763568394002505e-15,
    8.881784197001252e-16,
    4.440892098500626e-16,
    2.220446049250313e-16,
    1.1102230246251565e-16,
    5.551115123125783e-17,
    2.7755575615628914e-17,
    1.3877787807814457e-17,
    6.938893903907228e-18,
    3.469446951953614e-18,
    1.734723475976807e-18,
    8.673617379884035e-19,
    4.336808689942018e-19,
    2.168404344971009e-19,
    1.0842021724855044e-19,
];