Compare memory usage in different ID maps

branch_bitmap.diff

129c129
<         for i in 0..32 as usize {
---
>         for i in 0..8 as usize {

main.rs

use std::num::NonZeroUsize;
use std::collections::HashMap;
use deepsize::DeepSizeOf;
use itertools::Itertools;
use rudy::rudymap::RudyMap;

#[derive(DeepSizeOf)]
pub struct HashIdMap {
    real_to_virt: HashMap<usize, usize>,
    virt_to_real: Vec<usize>,
}

impl HashIdMap {
    fn new(nodes: impl Iterator<Item = usize>) -> Self {
        let virt_to_real = nodes.collect_vec();
        let real_to_virt = virt_to_real
            .iter()
            .copied()
            .enumerate()
            .map(|(index, node)| (node, index))
            .collect();

        Self {
            real_to_virt,
            virt_to_real,
        }
    }
}

#[derive(DeepSizeOf)]
pub struct VecIdMap {
    real_to_virt: Vec<Option<usize>>,
    virt_to_real: Vec<usize>,
}

impl VecIdMap {
    fn new(nodes: impl Iterator<Item = usize>) -> Self {
        let virt_to_real = nodes.collect_vec();
        let max_id = virt_to_real
            .iter()
            .max()
            .copied()
            .unwrap_or(0);
        let mut real_to_virt = vec![None; max_id + 1];
        virt_to_real
            .iter()
            .enumerate()
            .for_each(|(index, node)| real_to_virt[*node] = Some(index));

        Self {
            real_to_virt,
            virt_to_real,
        }
    }
}

#[derive(DeepSizeOf)]
pub struct VecNonZeroIdMap {
    real_to_virt: Vec<Option<NonZeroUsize>>,
    virt_to_real: Vec<usize>,
}

impl VecNonZeroIdMap {
    fn new(nodes: impl Iterator<Item = usize>) -> Self {
        let virt_to_real = nodes.collect_vec();
        let max_id = virt_to_real
            .iter()
            .max()
            .copied()
            .unwrap_or(0);
        let mut real_to_virt = vec![None; max_id + 1];
        virt_to_real
            .iter()
            .enumerate()
            .for_each(|(index, node)| real_to_virt[*node] = NonZeroUsize::new(index + 1));

        Self {
            real_to_virt,
            virt_to_real,
        }
    }
}

pub struct RudyIdMap {
    real_to_virt: RudyMap<usize, usize>,
    virt_to_real: Vec<usize>,
}

impl RudyIdMap {
    fn new(nodes: impl Iterator<Item = usize>) -> Self {
        let virt_to_real = nodes.collect_vec();
        let mut real_to_virt = RudyMap::new();
        let success = virt_to_real
            .iter()
            .enumerate()
            .map(|(index, node)| real_to_virt.insert(*node, index))
            .all(|duplicated| duplicated.is_none());
        assert!(success);

        Self {
            real_to_virt,
            virt_to_real,
        }
    }

    fn deep_size_of(self) -> usize {
        self.real_to_virt.memory_usage() + self.virt_to_real.deep_size_of()
    }
}


fn main() {
    let range = 500..1000;

    let map = HashIdMap::new(range.clone());
    println!("{:?}", map.deep_size_of());

    let map = VecIdMap::new(range.clone());
    println!("{:?}", map.deep_size_of());

    let map = VecNonZeroIdMap::new(range.clone());
    println!("{:?}", map.deep_size_of());

    let map = RudyIdMap::new(range.clone());
    println!("{:?}", map.deep_size_of());
}