alex/volcanic-mem

root / bench / src / main.rs

use ash::vk::{self, Handle};
use std::sync::Mutex;
use std::time::Instant;
use vk_mem::Alloc;

// ---- Workload -----------------------------------------------

struct Rng(u64);

impl Rng {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }

    fn below(&mut self, n: u64) -> u64 {
        self.next() % n
    }

    fn log_uniform(&mut self, min: u64, max: u64) -> u64 {
        let bits = self.below(64 - max.leading_zeros() as u64) + 1;
        (self.next() & ((1 << bits) - 1)).clamp(min, max)
    }
}

#[derive(Clone, Copy)]
enum Op {
    Alloc { slot: u32, size: u64, align: u64 },
    Free { slot: u32 },
}

/// Fills `live` allocations, then churns: each step frees a random live one and allocates a new one.
fn trace(
    seed: u64,
    live: usize,
    churn: usize,
    min: u64,
    max: u64,
    aligns: &[u64],
) -> (Vec<Op>, usize) {
    let mut rng = Rng(seed);
    let mut ops = Vec::with_capacity(live + churn * 2);
    let mut slots: Vec<u32> = Vec::new();
    let mut next = 0u32;
    let mut alloc = |rng: &mut Rng, slots: &mut Vec<u32>, ops: &mut Vec<Op>| {
        let slot = next;
        next += 1;
        let align = aligns[rng.below(aligns.len() as u64) as usize];
        ops.push(Op::Alloc {
            slot,
            size: rng.log_uniform(min, max),
            align,
        });
        slots.push(slot);
    };
    for _ in 0..live {
        alloc(&mut rng, &mut slots, &mut ops);
    }
    for _ in 0..churn {
        let slot = slots.swap_remove(rng.below(slots.len() as u64) as usize);
        ops.push(Op::Free { slot });
        alloc(&mut rng, &mut slots, &mut ops);
    }
    for slot in slots {
        ops.push(Op::Free { slot });
    }
    (ops, next as usize)
}

/// Runs each contender `rounds` times, interleaved so background load hits all of them alike.
/// Prints min and median nanoseconds per operation.
fn compare(title: &str, ops: usize, rounds: usize, contenders: &mut [(&str, &mut dyn FnMut())]) {
    let mut samples = vec![Vec::with_capacity(rounds); contenders.len()];
    for (_, run) in contenders.iter_mut() {
        run();
    }
    for _ in 0..rounds {
        for (i, (_, run)) in contenders.iter_mut().enumerate() {
            let start = Instant::now();
            run();
            samples[i].push(start.elapsed().as_nanos() as f64 / ops as f64);
        }
    }
    println!("\n{title}  ({ops} ops, {rounds} interleaved rounds)");
    println!("  {:<16} {:>10} {:>10}", "", "min ns/op", "median");
    for ((name, _), s) in contenders.iter().zip(&mut samples) {
        s.sort_by(f64::total_cmp);
        println!("  {:<16} {:>10.1} {:>10.1}", name, s[0], s[s.len() / 2]);
    }
}

// ---- A: virtual blocks --------------------------------------

fn replay_ours(
    block: &mut volcanic_mem::VirtualBlock,
    ops: &[Op],
    slots: &mut [Option<volcanic_mem::VirtualAllocation>],
) -> usize {
    let mut failed = 0;
    for op in ops {
        match *op {
            Op::Alloc { slot, size, align } => match block.allocate(size, align) {
                Ok(a) => slots[slot as usize] = Some(a),
                Err(_) => failed += 1,
            },
            Op::Free { slot } => {
                if let Some(a) = slots[slot as usize].take() {
                    block.free(a);
                }
            }
        }
    }
    failed
}

fn replay_vma(
    block: &mut vk_mem::VirtualBlock,
    ops: &[Op],
    slots: &mut [Option<vk_mem::VirtualAllocation>],
) -> usize {
    let mut failed = 0;
    for op in ops {
        match *op {
            Op::Alloc { slot, size, align } => {
                match unsafe { block.allocate(vma_info(size, align)) } {
                    Ok((a, _)) => slots[slot as usize] = Some(a),
                    Err(_) => failed += 1,
                }
            }
            Op::Free { slot } => {
                if let Some(mut a) = slots[slot as usize].take() {
                    unsafe { block.free(&mut a) };
                }
            }
        }
    }
    failed
}

fn vma_block(size: u64) -> vk_mem::VirtualBlock {
    vk_mem::VirtualBlock::new(vk_mem::VirtualBlockCreateInfo {
        size,
        ..Default::default()
    })
    .unwrap()
}

/// Allocates random sizes until the first failure and returns the used fraction of the block.
fn fill_ratio(alloc: impl FnMut(u64, u64) -> bool, size: u64, seed: u64) -> f64 {
    fill_bytes(alloc, 64, 1 << 20, seed) as f64 / size as f64
}

/// Allocates random sizes in `min..=max` until the first failure and returns the bytes placed.
fn fill_bytes(mut alloc: impl FnMut(u64, u64) -> bool, min: u64, max: u64, seed: u64) -> u64 {
    let mut rng = Rng(seed);
    let mut used = 0;
    loop {
        let (bytes, align) = (rng.log_uniform(min, max), 1 << (6 + rng.below(7)));
        if !alloc(bytes, align) {
            return used;
        }
        used += bytes;
    }
}

/// Largest size that still allocates at alignment 1, found by bisection. The probe must free
/// what it allocates.
fn largest_allocatable(mut fits: impl FnMut(u64) -> bool, max: u64) -> u64 {
    let (mut lo, mut hi) = (0, max);
    while lo < hi {
        let mid = lo + (hi - lo).div_ceil(2);
        if fits(mid) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    lo
}

/// Bytes of the trace's allocations whose slot is still live.
fn live_bytes(ops: &[Op], live: impl Fn(u32) -> bool) -> u64 {
    ops.iter()
        .filter_map(|op| match *op {
            Op::Alloc { slot, size, .. } if live(slot) => Some(size),
            _ => None,
        })
        .sum()
}

fn vma_info(size: u64, alignment: u64) -> vk_mem::VirtualAllocationCreateInfo {
    vk_mem::VirtualAllocationCreateInfo {
        size,
        alignment,
        user_data: 0,
        flags: vk_mem::VirtualAllocationCreateFlags::empty(),
    }
}

fn ours_probe(block: &mut volcanic_mem::VirtualBlock) -> impl FnMut(u64) -> bool {
    |s| block.allocate(s, 1).map(|a| block.free(a)).is_ok()
}

fn vma_probe(block: &mut vk_mem::VirtualBlock) -> impl FnMut(u64) -> bool {
    |s| {
        unsafe { block.allocate(vma_info(s, 1)) }
            .map(|(mut a, _)| unsafe { block.free(&mut a) })
            .is_ok()
    }
}

fn virtual_blocks() {
    let aligns = [16, 64, 256, 256, 256, 1024, 4096];
    let (ops, n) = trace(1, 20_000, 500_000, 16, 256 << 10, &aligns);
    let size = 4 << 30;
    let mut ours = volcanic_mem::VirtualBlock::new(size).unwrap();
    let mut vma = vma_block(size);
    let mut ours_slots: Vec<_> = (0..n).map(|_| None).collect();
    let mut vma_slots: Vec<_> = (0..n).map(|_| None).collect();
    compare(
        "A1  virtual block churn, 20k live, 16 B..256 KiB",
        ops.len(),
        25,
        &mut [
            ("volcanic-mem", &mut || {
                assert_eq!(replay_ours(&mut ours, &ops, &mut ours_slots), 0)
            }),
            ("VMA (TLSF)", &mut || {
                assert_eq!(replay_vma(&mut vma, &ops, &mut vma_slots), 0)
            }),
        ],
    );

    let (ops, n) = trace(
        5,
        6_000,
        300_000,
        64,
        1 << 20,
        &[64, 256, 1024, 4096, 65536],
    );
    let size = 1 << 30;
    let mut ours = volcanic_mem::VirtualBlock::new(size).unwrap();
    let mut vma = vma_block(size);
    let mut ours_slots: Vec<_> = (0..n).map(|_| None).collect();
    let mut vma_slots: Vec<_> = (0..n).map(|_| None).collect();
    compare(
        "A3  virtual block churn near capacity, 6k live in 1 GiB, 64 B..1 MiB, align up to 64 KiB",
        ops.len(),
        15,
        &mut [
            ("volcanic-mem", &mut || {
                assert_eq!(replay_ours(&mut ours, &ops, &mut ours_slots), 0)
            }),
            ("VMA (TLSF)", &mut || {
                assert_eq!(replay_vma(&mut vma, &ops, &mut vma_slots), 0)
            }),
        ],
    );
}

fn fragmentation() {
    // Fragmentation is deterministic: no timing noise involved. Averaged over seeds since a
    // single fill-until-failure run is chaotic.
    println!("\nA2  fragmentation under churn near capacity (deterministic, mean of 10 seeds)");
    println!(
        "  {:<16} {:>14} {:>16} {:>18}",
        "", "failed allocs", "fill after churn", "largest / free"
    );
    for live in [3_000usize, 6_000, 7_000] {
        let (mut ours_failed, mut ours_fill, mut vma_failed, mut vma_fill) = (0, 0.0, 0, 0.0);
        let (mut ours_largest, mut vma_largest) = (0.0, 0.0);
        for seed in 0..10u64 {
            let (ops, n) = trace(
                seed * 31 + 7,
                live,
                100_000,
                64,
                1 << 20,
                &[64, 256, 1024, 4096, 65536],
            );
            let without_frees = &ops[..ops.len() - live];
            let size = 1 << 30;

            let mut ours = volcanic_mem::VirtualBlock::new(size).unwrap();
            let mut slots: Vec<_> = (0..n).map(|_| None).collect();
            ours_failed += replay_ours(&mut ours, without_frees, &mut slots);
            let free = size - live_bytes(without_frees, |s| slots[s as usize].is_some());
            ours_largest += largest_allocatable(ours_probe(&mut ours), free) as f64 / free as f64;
            ours_fill += fill_ratio(
                |s, a| ours.allocate(s, a).map(std::mem::forget).is_ok(),
                size,
                seed,
            );

            let mut vma = vma_block(size);
            let mut slots: Vec<_> = (0..n).map(|_| None).collect();
            vma_failed += replay_vma(&mut vma, without_frees, &mut slots);
            let free = size - live_bytes(without_frees, |s| slots[s as usize].is_some());
            vma_largest += largest_allocatable(vma_probe(&mut vma), free) as f64 / free as f64;
            vma_fill += fill_ratio(
                |s, a| {
                    unsafe { vma.allocate(vma_info(s, a)) }
                        .map(std::mem::forget)
                        .is_ok()
                },
                size,
                seed,
            );
            unsafe { vma.clear() };
        }
        println!(
            "  {:<16} {:>14} {:>15.1}% {:>17.1}%   ({live} live)",
            "volcanic-mem",
            ours_failed,
            ours_fill * 10.0,
            ours_largest * 10.0
        );
        println!(
            "  {:<16} {:>14} {:>15.1}% {:>17.1}%   ({live} live)",
            "VMA (TLSF)",
            vma_failed,
            vma_fill * 10.0,
            vma_largest * 10.0
        );
    }

    // A4: churns small allocations, frees a random half of the survivors, then fills with large
    // allocations, like streaming in a new level after many small transient resources.
    const SIZE: u64 = 1 << 30;
    const LIVE: usize = 60_000;
    let aligns = [16, 64, 256, 1024];
    println!(
        "\nA4  size shift: churn {LIVE} live 64 B..64 KiB, free half, then fill with 256 KiB..16 MiB (deterministic, mean of 10 seeds)"
    );
    println!(
        "  {:<16} {:>8} {:>16} {:>18}",
        "", "free", "largest / free", "large fill / free"
    );
    let mut rows = [
        ("volcanic-mem", 0.0, 0.0, 0.0),
        ("VMA (TLSF)", 0.0, 0.0, 0.0),
    ];
    for seed in 0..10u64 {
        let (ops, n) = trace(seed * 17 + 3, LIVE, 200_000, 64, 64 << 10, &aligns);
        let churned = &ops[..ops.len() - LIVE];
        let mut rng = Rng(seed + 1);
        let survivors: Vec<u32> = ops[ops.len() - LIVE..]
            .iter()
            .filter_map(|op| match *op {
                Op::Free { slot } if rng.below(2) == 0 => Some(slot),
                _ => None,
            })
            .collect();
        let freed: Vec<Op> = survivors.iter().map(|&slot| Op::Free { slot }).collect();

        let mut ours = volcanic_mem::VirtualBlock::new(SIZE).unwrap();
        let mut slots: Vec<_> = (0..n).map(|_| None).collect();
        assert_eq!(replay_ours(&mut ours, churned, &mut slots), 0);
        replay_ours(&mut ours, &freed, &mut slots);
        let free = SIZE - live_bytes(churned, |s| slots[s as usize].is_some());
        let largest = largest_allocatable(ours_probe(&mut ours), free);
        let filled = fill_bytes(
            |s, a| ours.allocate(s, a).map(std::mem::forget).is_ok(),
            256 << 10,
            16 << 20,
            seed,
        );
        rows[0].1 += free as f64 / SIZE as f64;
        rows[0].2 += largest as f64 / free as f64;
        rows[0].3 += filled as f64 / free as f64;

        let mut vma = vma_block(SIZE);
        let mut slots: Vec<_> = (0..n).map(|_| None).collect();
        assert_eq!(replay_vma(&mut vma, churned, &mut slots), 0);
        replay_vma(&mut vma, &freed, &mut slots);
        let free = SIZE - live_bytes(churned, |s| slots[s as usize].is_some());
        let largest = largest_allocatable(vma_probe(&mut vma), free);
        let filled = fill_bytes(
            |s, a| {
                unsafe { vma.allocate(vma_info(s, a)) }
                    .map(std::mem::forget)
                    .is_ok()
            },
            256 << 10,
            16 << 20,
            seed,
        );
        unsafe { vma.clear() };
        rows[1].1 += free as f64 / SIZE as f64;
        rows[1].2 += largest as f64 / free as f64;
        rows[1].3 += filled as f64 / free as f64;
    }
    for (name, free, largest, filled) in rows {
        println!(
            "  {:<16} {:>7.1}% {:>15.1}% {:>17.1}%",
            name,
            free * 10.0,
            largest * 10.0,
            filled * 10.0
        );
    }
}

// ---- B: device allocators -----------------------------------

struct Vulkan {
    _entry: ash::Entry,
    instance: ash::Instance,
    physical_device: vk::PhysicalDevice,
    device: ash::Device,
    _loader: volcanic::loader::Loader,
    v_instance: volcanic::loader::InstanceCommands,
    v_device: volcanic::loader::DeviceCommands,
}

impl Vulkan {
    fn new() -> Self {
        unsafe {
            let entry = ash::Entry::load().unwrap();
            let app = vk::ApplicationInfo::default().api_version(vk::make_api_version(0, 1, 4, 0));
            let instance = entry
                .create_instance(
                    &vk::InstanceCreateInfo::default().application_info(&app),
                    None,
                )
                .unwrap();
            let physical_device = instance.enumerate_physical_devices().unwrap()[0];
            let priority = [1.0];
            let queue = vk::DeviceQueueCreateInfo::default()
                .queue_family_index(0)
                .queue_priorities(&priority);
            let mut features12 =
                vk::PhysicalDeviceVulkan12Features::default().buffer_device_address(true);
            let info = vk::DeviceCreateInfo::default()
                .queue_create_infos(std::slice::from_ref(&queue))
                .push_next(&mut features12);
            let device = instance
                .create_device(physical_device, &info, None)
                .unwrap();

            let loader = volcanic::loader::Loader::new().unwrap();
            let v_instance = loader
                .load_instance(instance.handle().as_raw() as usize as _)
                .unwrap();
            let v_device = v_instance
                .load_device(device.handle().as_raw() as usize as _)
                .unwrap();
            Self {
                _entry: entry,
                instance,
                physical_device,
                device,
                _loader: loader,
                v_instance,
                v_device,
            }
        }
    }

    fn ours(&self) -> volcanic_mem::Allocator {
        unsafe {
            volcanic_mem::Allocator::new(
                &self.v_instance,
                self.physical_device.as_raw() as usize as _,
                &self.v_device,
                self.device.handle().as_raw() as usize as _,
                &Default::default(),
            )
            .unwrap()
        }
    }

    fn vma(&self) -> vk_mem::Allocator {
        let mut info =
            vk_mem::AllocatorCreateInfo::new(&self.instance, &self.device, self.physical_device);
        info.vulkan_api_version = vk::make_api_version(0, 1, 3, 0);
        info.flags = vk_mem::AllocatorCreateFlags::BUFFER_DEVICE_ADDRESS;
        unsafe { vk_mem::Allocator::new(info).unwrap() }
    }

    fn gpu_allocator(&self) -> gpu_allocator::vulkan::Allocator {
        gpu_allocator::vulkan::Allocator::new(&gpu_allocator::vulkan::AllocatorCreateDesc {
            instance: self.instance.clone(),
            device: self.device.clone(),
            physical_device: self.physical_device,
            debug_settings: Default::default(),
            buffer_device_address: true,
            allocation_sizes: Default::default(),
        })
        .unwrap()
    }

    /// The memory type the driver uses for device-local storage buffers.
    fn device_local_type(&self) -> u32 {
        unsafe {
            let info = vk::BufferCreateInfo::default()
                .size(1 << 20)
                .usage(vk::BufferUsageFlags::STORAGE_BUFFER);
            let buffer = self.device.create_buffer(&info, None).unwrap();
            let bits = self
                .device
                .get_buffer_memory_requirements(buffer)
                .memory_type_bits;
            self.device.destroy_buffer(buffer, None);
            let props = self
                .instance
                .get_physical_device_memory_properties(self.physical_device);
            (0..props.memory_type_count)
                .find(|&i| {
                    bits & (1 << i) != 0
                        && props.memory_types[i as usize].property_flags
                            == vk::MemoryPropertyFlags::DEVICE_LOCAL
                })
                .unwrap()
        }
    }
}

impl Drop for Vulkan {
    fn drop(&mut self) {
        unsafe {
            self.device.destroy_device(None);
            self.instance.destroy_instance(None);
        }
    }
}

fn requirements(size: u64, align: u64, ty: u32) -> vk::MemoryRequirements {
    vk::MemoryRequirements {
        size,
        alignment: align,
        memory_type_bits: 1 << ty,
    }
}

fn run_ours(
    a: &volcanic_mem::Allocator,
    ops: &[Op],
    slots: &mut [Option<volcanic_mem::Allocation>],
    ty: u32,
) {
    for op in ops {
        match *op {
            Op::Alloc { slot, size, align } => {
                let r = requirements(size, align, ty);
                let desc = volcanic_mem::AllocationDesc {
                    requirements: volcanic::VkMemoryRequirements {
                        size: r.size,
                        alignment: r.alignment,
                        memoryTypeBits: r.memory_type_bits,
                    },
                    location: volcanic_mem::MemoryLocation::GpuOnly,
                    kind: volcanic_mem::ResourceKind::Linear,
                    dedicated: false,
                };
                slots[slot as usize] = Some(a.allocate(&desc).unwrap());
            }
            Op::Free { slot } => a.free(slots[slot as usize].take().unwrap()),
        }
    }
}

fn run_vma(a: &vk_mem::Allocator, ops: &[Op], slots: &mut [Option<vk_mem::Allocation>], ty: u32) {
    let info = vk_mem::AllocationCreateInfo {
        usage: vk_mem::MemoryUsage::Unknown,
        ..Default::default()
    };
    for op in ops {
        match *op {
            Op::Alloc { slot, size, align } => {
                slots[slot as usize] = Some(
                    unsafe { a.allocate_memory(&requirements(size, align, ty), &info) }.unwrap(),
                );
            }
            Op::Free { slot } => unsafe {
                a.free_memory(&mut slots[slot as usize].take().unwrap())
            },
        }
    }
}

fn run_gpu_allocator(
    a: &Mutex<gpu_allocator::vulkan::Allocator>,
    ops: &[Op],
    slots: &mut [Option<gpu_allocator::vulkan::Allocation>],
    ty: u32,
) {
    for op in ops {
        match *op {
            Op::Alloc { slot, size, align } => {
                let desc = gpu_allocator::vulkan::AllocationCreateDesc {
                    name: "",
                    requirements: requirements(size, align, ty),
                    location: gpu_allocator::MemoryLocation::GpuOnly,
                    linear: true,
                    allocation_scheme: gpu_allocator::vulkan::AllocationScheme::GpuAllocatorManaged,
                };
                slots[slot as usize] = Some(a.lock().unwrap().allocate(&desc).unwrap());
            }
            Op::Free { slot } => a
                .lock()
                .unwrap()
                .free(slots[slot as usize].take().unwrap())
                .unwrap(),
        }
    }
}

/// Peak and final reserved `VkDeviceMemory` over full traces on fresh allocators (deterministic).
fn reserved_memory(vk: &Vulkan, ty: u32) {
    const SEEDS: u64 = 5;
    let aligns = [1024, 1024, 1024, 4096, 65536];
    let mut rows = [
        ("volcanic-mem", 0u64, 0u64),
        ("VMA", 0, 0),
        ("gpu-allocator", 0, 0),
    ];
    let mut live_total = 0u64;
    for seed in 0..SEEDS {
        let (ops, n) = trace(100 + seed, 4_000, 100_000, 256, 4 << 20, &aligns);
        let body = &ops[..ops.len() - 4_000];
        let chunks = body.chunks(1_000);
        let mut sizes = vec![0; n];
        let (mut live, mut peak_live) = (0u64, 0);
        for chunk in chunks.clone() {
            for op in chunk {
                match *op {
                    Op::Alloc { slot, size, .. } => {
                        sizes[slot as usize] = size;
                        live += size;
                    }
                    Op::Free { slot } => live -= sizes[slot as usize],
                }
            }
            peak_live = peak_live.max(live);
        }
        live_total += peak_live;

        let ours = vk.ours();
        let mut slots: Vec<_> = (0..n).map(|_| None).collect();
        let mut peak = 0;
        for chunk in chunks.clone() {
            run_ours(&ours, chunk, &mut slots, ty);
            peak = peak.max(ours.statistics().block_bytes);
        }
        rows[0].1 += peak;
        rows[0].2 += ours.statistics().block_bytes;
        slots
            .iter_mut()
            .filter_map(Option::take)
            .for_each(|a| ours.free(a));

        let vma = vk.vma();
        let mut slots: Vec<_> = (0..n).map(|_| None).collect();
        let mut peak = 0;
        for chunk in chunks.clone() {
            run_vma(&vma, chunk, &mut slots, ty);
            peak = peak.max(
                vma.calculate_statistics()
                    .unwrap()
                    .total
                    .statistics
                    .blockBytes,
            );
        }
        rows[1].1 += peak;
        rows[1].2 += vma
            .calculate_statistics()
            .unwrap()
            .total
            .statistics
            .blockBytes;
        slots
            .iter_mut()
            .filter_map(Option::take)
            .for_each(|mut a| unsafe { vma.free_memory(&mut a) });
        drop(vma);

        let gpu = Mutex::new(vk.gpu_allocator());
        let mut slots: Vec<_> = (0..n).map(|_| None).collect();
        let mut peak = 0;
        for chunk in chunks {
            run_gpu_allocator(&gpu, chunk, &mut slots, ty);
            peak = peak.max(gpu.lock().unwrap().generate_report().total_capacity_bytes);
        }
        rows[2].1 += peak;
        rows[2].2 += gpu.lock().unwrap().generate_report().total_capacity_bytes;
        slots
            .iter_mut()
            .filter_map(Option::take)
            .for_each(|a| gpu.lock().unwrap().free(a).unwrap());
    }
    let live = live_total / SEEDS;
    println!(
        "\nB2  reserved VkDeviceMemory over 100k-op churn, ~{} MiB peak live, mean of {SEEDS} seeds (deterministic)",
        live >> 20
    );
    println!(
        "  {:<16} {:>10} {:>10} {:>12}",
        "", "peak MiB", "final MiB", "peak overhead"
    );
    for (name, peak, last) in rows {
        let (peak, last) = (peak / SEEDS, last / SEEDS);
        println!(
            "  {:<16} {:>10} {:>10} {:>11.1}%",
            name,
            peak >> 20,
            last >> 20,
            (peak - live) as f64 / live as f64 * 100.0
        );
    }
}

fn device_allocators() {
    let vk = Vulkan::new();
    let ty = vk.device_local_type();
    let ours = vk.ours();
    let vma = vk.vma();
    let gpu = Mutex::new(vk.gpu_allocator());

    let aligns = [1024, 1024, 1024, 4096, 65536];
    let (ops, n) = trace(3, 4_000, 200_000, 256, 4 << 20, &aligns);
    let mut s1: Vec<_> = (0..n).map(|_| None).collect();
    let mut s2: Vec<_> = (0..n).map(|_| None).collect();
    let mut s3: Vec<_> = (0..n).map(|_| None).collect();
    compare(
        "B1  device suballocation churn, 1 thread, 4k live, 256 B..4 MiB",
        ops.len(),
        15,
        &mut [
            ("volcanic-mem", &mut || run_ours(&ours, &ops, &mut s1, ty)),
            ("VMA", &mut || run_vma(&vma, &ops, &mut s2, ty)),
            ("gpu-allocator", &mut || {
                run_gpu_allocator(&gpu, &ops, &mut s3, ty)
            }),
        ],
    );

    drop((ours, vma, gpu));
    reserved_memory(&vk, ty);
    let ours = vk.ours();
    let vma = vk.vma();
    let gpu = Mutex::new(vk.gpu_allocator());

    const THREADS: usize = 8;
    let traces: Vec<_> = (0..THREADS)
        .map(|t| trace(10 + t as u64, 500, 50_000, 256, 1 << 20, &aligns))
        .collect();
    let total: usize = traces.iter().map(|(ops, _)| ops.len()).sum();
    let threaded = |run: &(dyn Fn(&[Op], usize) + Sync)| {
        std::thread::scope(|scope| {
            for (ops, n) in &traces {
                scope.spawn(move || run(ops, *n));
            }
        })
    };
    compare(
        "B3  device suballocation churn, 8 threads",
        total,
        10,
        &mut [
            ("volcanic-mem", &mut || {
                threaded(&|ops, n| {
                    run_ours(
                        &ours,
                        ops,
                        &mut (0..n).map(|_| None).collect::<Vec<_>>(),
                        ty,
                    )
                })
            }),
            ("VMA", &mut || {
                threaded(&|ops, n| {
                    run_vma(&vma, ops, &mut (0..n).map(|_| None).collect::<Vec<_>>(), ty)
                })
            }),
            ("gpu-allocator", &mut || {
                threaded(&|ops, n| {
                    run_gpu_allocator(&gpu, ops, &mut (0..n).map(|_| None).collect::<Vec<_>>(), ty)
                })
            }),
        ],
    );
    drop((ours, vma, gpu));
}

fn main() {
    match std::env::args().nth(1).unwrap_or_default().as_str() {
        "virtual" => virtual_blocks(),
        "device" => device_allocators(),
        "fragmentation" => fragmentation(),
        "reserved" => {
            let vk = Vulkan::new();
            let ty = vk.device_local_type();
            reserved_memory(&vk, ty);
        }
        _ => {
            virtual_blocks();
            fragmentation();
            device_allocators();
        }
    }
}