frond 0.1.1

use std::time::Instant;

use frond::{Interface, Naive};

mod alloc {
    use std::alloc::{Layout, System};
    use std::sync::atomic::{AtomicUsize, Ordering};

    #[global_allocator]
    static ALLOCATOR: Alloc = Alloc;

    static ALLOCATED: AtomicUsize = AtomicUsize::new(0);
    static FREED: AtomicUsize = AtomicUsize::new(0);
    static RESIDENT: AtomicUsize = AtomicUsize::new(0);

    pub fn allocated() -> usize {
        ALLOCATED.swap(0, Ordering::Relaxed) / 1_000_000
    }

    pub fn freed() -> usize {
        FREED.swap(0, Ordering::Relaxed) / 1_000_000
    }

    pub fn resident() -> usize {
        RESIDENT.load(Ordering::Relaxed) / 1_000_000
    }

    #[derive(Default, Debug, Clone, Copy)]
    struct Alloc;

    unsafe impl std::alloc::GlobalAlloc for Alloc {
        unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
            let ret = System.alloc(layout);
            assert_ne!(ret, std::ptr::null_mut());
            ALLOCATED.fetch_add(layout.size(), Ordering::Relaxed);
            RESIDENT.fetch_add(layout.size(), Ordering::Relaxed);
            std::ptr::write_bytes(ret, 0xa1, layout.size());
            ret
        }

        unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
            std::ptr::write_bytes(ptr, 0xde, layout.size());
            FREED.fetch_add(layout.size(), Ordering::Relaxed);
            RESIDENT.fetch_sub(layout.size(), Ordering::Relaxed);
            System.dealloc(ptr, layout)
        }
    }
}

fn naive_bulk_load_throughput(items: u64, split_threshold: usize, endpoint_splits: bool) {
    let before = Instant::now();

    let mut naive = Naive::new();
    let mut splits = 0;
    let mut previous_shards = Vec::with_capacity(items as usize / split_threshold);

    for i in 0..items {
        let k: Vec<u8> = i.to_be_bytes().to_vec();
        let (_last, new) = naive.insert(&k, &k);
        naive = new;

        if naive.len() >= split_threshold {
            // midpoint
            let split_key = if endpoint_splits {
                k
            } else {
                (i - (split_threshold as u64 / 2)).to_be_bytes().to_vec()
            };

            let (_lhs, mut rhs) = naive.split(&split_key);
            std::mem::swap(&mut naive, &mut rhs);
            previous_shards.push(rhs);
            splits += 1;
        }
    }

    println!(
        "{:.2} million wps {} mb allocated {} mb freed {} mb resident to insert {} items with a split threshold of {}, using endpoint split optimization: {}, split {} times",
        items as f64 / (before.elapsed().as_micros().max(1)) as f64,
        alloc::allocated(),
        alloc::freed(),
        alloc::resident(),
        items, split_threshold, endpoint_splits, splits
    );
}

fn main() {
    let items = 100_000;

    println!("naive with COW for each insert:");
    for split_threshold in [128, 1024, 4096] {
        for endpoint_splits in [false, true] {
            naive_bulk_load_throughput(items, split_threshold, endpoint_splits);
        }
    }
}