nordisk/nornir

tests/structural_alloc.rs

//! **The structural pair loop allocates per KEPT pair, not per candidate.**
//! A counting global allocator around `structural_pairs` over a synthetic
//! population where most candidates fail the floor: the count is printed (the
//! before/after of the change) and bounded by the pairs found plus the pass's
//! fixed bookkeeping.

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

struct Counting;
static ALLOCS: AtomicUsize = AtomicUsize::new(0);

unsafe impl GlobalAlloc for Counting {
    unsafe fn alloc(&self, l: Layout) -> *mut u8 {
        ALLOCS.fetch_add(1, Relaxed);
        unsafe { System.alloc(l) }
    }
    unsafe fn dealloc(&self, p: *mut u8, l: Layout) {
        unsafe { System.dealloc(p, l) }
    }
    unsafe fn realloc(&self, p: *mut u8, l: Layout, n: usize) -> *mut u8 {
        ALLOCS.fetch_add(1, Relaxed);
        unsafe { System.realloc(p, l, n) }
    }
}

#[global_allocator]
static A: Counting = Counting;

#[test]
fn the_pair_loop_allocates_per_kept_pair_not_per_candidate() {
    use nornir::clone_signals::structure::{Features, STRUCT_FLOOR, structural_pairs_on};
    let mut f = Features::default();
    // 400 functions over 40 rare features: every function shares rare
    // features with ~60 others (candidates), few pass the floor
    for i in 0..400u32 {
        let feats: Vec<(String, String)> = (0..6).map(|k| { let x = (i * 7 + k * 13) % 40; (format!("t:r{x}"), format!("r{x}")) })
            .chain([(format!("p:own{i}"), "own".to_string()), (format!("c:own{i}"), "own".to_string())])
            .collect();
        f.push(u64::from(i), &feats, &[]);
    }
    // 40 real pairs: two functions each sharing four rare features of their own
    for g in 0..40u32 {
        for side in 0..2u32 {
            let feats: Vec<(String, String)> = (0..4).map(|k| (format!("t:pair{g}-{k}"), "pair".to_string())).chain([(format!("c:side{g}-{side}"), "own".to_string())]).collect();
            f.push(u64::from(10_000 + g * 2 + side), &feats, &[]);
        }
    }
    let before = ALLOCS.load(Relaxed);
    let (pairs, stats) = structural_pairs_on(&f, STRUCT_FLOOR, None, 1);
    let used = ALLOCS.load(Relaxed) - before;
    eprintln!("structural_pairs: {} candidate(s), {} pair(s), {used} allocation(s)", stats.candidates, pairs.len());
    assert!(pairs.len() >= 40 && stats.candidates > 10 * pairs.len(), "the population is candidate-heavy: {stats:?}");
    // the postings map and the per-row result slots are the pass's own; every
    // other allocation belongs to a KEPT pair (its shared list)
    assert!(used < 2 * pairs.len() + 4 * f.n() + 200, "{used} allocations for {} pairs over {} candidates", pairs.len(), stats.candidates);
}