Module prefetch 

Memory Prefetching for Range Scans

Implements proactive prefetching to eliminate page fault latency during sequential scans of memory-mapped data.

jj.md Task 7: Prefetching for Range Scans

Goals:

• Eliminate page fault latency during scans (~50μs per fault)
• 2-3x faster cold range scans
• Better utilization of I/O bandwidth

Implementation

Uses platform-specific prefetching:

• Unix: madvise(MADV_SEQUENTIAL | MADV_WILLNEED)
• x86_64: _mm_prefetch intrinsic for CPU cache prefetching

For 1M edge scan with 4KB pages (32 edges/page):

• Without prefetch: ~31,250 page faults × 50μs = 1.56 seconds stalled
• With prefetch: Near-zero stall time

Structs

PrefetchStats

Statistics for prefetch operations (useful for debugging/tuning)

PrefetchingIterator

Iterator wrapper that adds prefetching to an existing iterator.

Constants

EDGE_SIZE

Edge size in bytes (fixed format)

PREFETCH_DISTANCE

Number of edges to prefetch ahead during iteration 16 edges = 2KB = half a page, good for L1 cache

Functions

advise_dontneed

Advise the OS that a memory region is no longer needed.

advise_random

Advise the OS that a memory region will be accessed randomly.

advise_sequential

Advise the OS about memory access patterns for a range scan.

prefetch_ahead

Prefetch data into CPU cache during iteration.