hibit_tree 0.1.1-beta.1

//! get 50% existent, ~50% non-existent

use std::collections::BTreeMap;
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use rand::{Rng, SeedableRng};
use rand::seq::SliceRandom;
use hibit_tree::{HierarchyIndex, ReqDefault};
use hibit_tree::config::_64bit;
//use hi_sparse_array::level_block::{Block, ClusterBlock, SmallBlock};
//use hi_sparse_array::Iter;
//use hi_sparse_array::level::{IntrusiveListLevel, SingleBlockLevel};
use hibit_tree::HibitTree;
use hibit_tree::Tree;

const RANGE: usize = 260_000;
const COUNT: usize = 4000;

#[derive(Default, Clone)]
struct DataBlock(u64);
/*impl Empty for DataBlock{
    fn empty() -> Self {
        Self(0)
    }

    fn is_empty(&self) -> bool {
        todo!()
    }
}*/

type Map = nohash_hasher::IntMap<u32, DataBlock>;
//type Map = ahash::AHashMap<u32, DataBlock>;
type BTree = BTreeMap<u32, DataBlock>;

//type BlockArray = SparseArray<(SingleBlockLevel<Lvl0Block>, IntrusiveListLevel<Lvl1Block>, IntrusiveListLevel<Lvl2Block>), DataBlock>;
// type BlockArray = SparseTree<config::width_64::depth_3, DataBlock>;
type BlockArrayNew = Tree<DataBlock, _64bit<4>, ReqDefault>;

//type SmallBlockArray = SparseArray<(SingleBlockLevel<Lvl0Block>, IntrusiveListLevel<CompactLvl1Block>, IntrusiveListLevel<CompactLvl2Block>), DataBlock>;
//type SmallBlockArray = SparseArray<config::sbo::width_64::depth_6, DataBlock>;
/*type ClusterBlockArray = SparseArray<(SingleBlockLevel<Lvl0Block>, IntrusiveListLevel<ClusterLvl1Block>), IntrusiveListLevel<DataBlock>>;*/

/*fn cluster_array_get(array: &ClusterBlockArray) -> u64 {
    let mut s = 0;
    for (_, i) in CachingBlockIter::new(array){
        s += i.0;
    }
    s
}*/

/*fn small_array_get(array: &SmallBlockArray, indices: &[usize]) -> u64 {
    let mut s = 0;
    for &i in indices{
        s += array.get(i).0;
    }
    s
}*/

/*fn array_get(array: &BlockArray, indices: &[usize]) -> u64 {
    let mut s = 0;
    for &i in indices{
        unsafe{
        s += array.get(Index::new_unchecked(i))
            //.unwrap_unchecked().0;
            .unwrap_or(&DataBlock(0)).0;
        }
    }
    s
}*/

fn array_new_get(array: &BlockArrayNew, indices: &[usize]) -> u64 {
    let mut s = 0;
    for &i in indices{
        unsafe{
        s += array.get(HierarchyIndex::new_unchecked(i))
            .unwrap_or(&DataBlock(0)).0;
         //s += array.get_or_default(Index::new_unchecked(i)).0;            
        }
    }
    s
}

fn array_new_get_or_default(array: &BlockArrayNew, indices: &[usize]) -> u64 {
    let mut s = 0;
    for &i in indices{
        unsafe{
        /*s += array.get(HierarchyIndex::new_unchecked(i))
            .unwrap_or(&DataBlock(0)).0;*/
        s += array.get_or_default(HierarchyIndex::new_unchecked(i)).0;            
        }
    }
    s
}

fn hashmap_get(array: &Map, indices: &[usize]) -> u64 {
    let mut s = 0;
    for i in indices{
        s += array.get(&(*i as _)).unwrap_or(&DataBlock(0)).0;
    }
    s
}

fn btree_get(array: &BTree, indices: &[usize]) -> u64 {
    let mut s = 0;
    for i in indices{
        s += array.get(&(*i as _)).unwrap_or(&DataBlock(0)).0;
    }
    s
}


pub fn bench_iter(c: &mut Criterion) {
    let mut new_array = BlockArrayNew::new();
    let mut new_array2 = BlockArrayNew::new();
    // let mut block_array = BlockArray::default();
    //let mut small_block_array = SmallBlockArray::default();
    /*let mut cluster_block_array = ClusterBlockArray::default();*/
    let mut hashmap = Map::default();
    let mut btree = BTree::default();
    
    let mut rng = rand::rngs::StdRng::seed_from_u64(0xe15bb9db3dee3a0f);
    let mut random_indices = Vec::new();
    
    for _ in 0..COUNT {
        let v = rng.gen_range(0..RANGE);
        random_indices.push(v);
        
        // block_array.insert(v, DataBlock(v as _));
        new_array.insert(v, DataBlock(v as _));
        new_array2.insert(v, DataBlock(v as _));
        //*small_block_array.get_mut(v) = DataBlock(v as u64);
        /* *cluster_block_array.get_or_insert(v) = DataBlock(v as u64);*/
        hashmap.insert(v as _, DataBlock(v as u64));
        btree.insert(v as _, DataBlock(v as u64));
    }
    
    // add 100% random as well
    /*for _ in 0..COUNT {
        let v = rng.gen_range(0..RANGE);
        random_indices.push(v);
    }*/
    random_indices.shuffle(&mut rng);

    c.bench_function("new array2", |b| b.iter(|| array_new_get_or_default(black_box(&new_array2), black_box(&random_indices))));
    c.bench_function("new array", |b| b.iter(|| array_new_get(black_box(&new_array), black_box(&random_indices))));
    // c.bench_function("level_block array", |b| b.iter(|| array_get(black_box(&block_array), black_box(&random_indices))));
    //c.bench_function("small level_block array", |b| b.iter(|| small_array_get(black_box(&small_block_array), black_box(&random_indices))));
    /*c.bench_function("cluster level_block array", |b| b.iter(|| cluster_array_get(black_box(&cluster_block_array))));*/
    c.bench_function("hashmap", |b| b.iter(|| hashmap_get(black_box(&hashmap), black_box(&random_indices))));
    c.bench_function("btree", |b| b.iter(|| btree_get(black_box(&btree), black_box(&random_indices))));
}

criterion_group!(benches_iter, bench_iter);
criterion_main!(benches_iter);