prefetch-index

A small crate to prefetch an element of an array.

Provides prefetch_index<T>(data: &[T], index: usize) that prefetches the cache line containing (the first byte of) slice[index]. prefetch_index_nta is also provided for non-temporal accesses.

This can be used too overlap multiple independent memory accesses, and is particularly useful when the CPU's reorder buffer is not sufficiently long to start loading memory by itself.

fn batched_pointer_chasing_prefetch() {
    // batch size
    const B: usize = 32;

    // Each index of `data` points to a pseudo-random other index.
    let data: Vec<u64> = setup();
    // Start indices.
    let mut indices: [usize; B] = from_fn(|i| i * data.len() / B + i);

    let start = std::time::Instant::now();
    let mut sum = 0;
    for _ in 0..data.len() / B {
        for idx in &mut indices {
            // Jump from the current index to data[idx].
            *idx = data[*idx] as usize;
            // Prefetch for the next index.
            prefetch_index(&data, *idx);  // <--------------------
            // Simulate some work to fill the CPU reorder buffer.
            let mut x: usize = 1;
            for _ in 0..16 {
                x = x.wrapping_mul(*idx);
                sum += x;
            }
        }
    }
    black_box(sum);
    let duration = start.elapsed();
    let ns_per_it = duration.as_nanos() as f64 / (data.len() as f64);
    eprintln!("With prefetch:    {:?}  {:5.2} ns/it", duration, ns_per_it);
}

On my machine (i7 10750H) at 3.0GHz, the version without prefetching is 40 ns/it, while the version with prefetching is 8 ns/it, i.e., 5x faster!