1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
//! Chunked u32 store for large fill-then-consume arrays.
//!
//! `inb_flat` in the inbound CSR build is filled by random-access scatter, then
//! consumed strictly left-to-right in Phase-4. A single flat `Vec<u32>` must
//! stay fully live until the last node is encoded, so it coexists with the
//! fully-built `inb_data` at the global RSS peak. Splitting the backing store
//! into fixed power-of-two chunks lets Phase-4 free each chunk the moment its
//! read cursor passes it, so remaining(inb_flat)+built(inb_data) peaks far below
//! their sum.
//!
//! Indexing uses shift/mask (CHUNK_LOG) so the scatter-fill hot path stays cheap.
const CHUNK_LOG: usize = 26; // 2^26 u32 = 64M slots = 256 MB per chunk
const CHUNK_LEN: usize = 1 << CHUNK_LOG;
const CHUNK_MASK: usize = CHUNK_LEN - 1;
/// Fill-then-consume u32 array split into fixed 256 MB chunks so each chunk can
/// be freed the instant its read cursor passes it (see module docs for the RSS
/// rationale). Empty inner `Vec`s mark already-freed chunks.
#[derive(Default)]
pub struct ChunkU32 {
chunks: Vec<Vec<u32>>,
}
impl ChunkU32 {
/// Returns true if no slots are allocated (len == 0).
#[allow(dead_code)]
pub fn is_empty(&self) -> bool {
self.chunks.is_empty()
}
/// Build a ChunkU32 from a flat Vec (useful in tests).
#[cfg(test)]
pub fn from_vec(v: Vec<u32>) -> Self {
let mut c = Self::zeroed(v.len());
for (i, &x) in v.iter().enumerate() {
c.set(i, x);
}
c
}
/// Allocate `len` u32 slots, zero-initialized, across power-of-two chunks.
pub fn zeroed(len: usize) -> Self {
let nchunks = len.div_ceil(CHUNK_LEN);
let mut chunks = Vec::with_capacity(nchunks);
let mut remaining = len;
for _ in 0..nchunks {
let this = remaining.min(CHUNK_LEN);
chunks.push(vec![0u32; this]);
remaining -= this;
}
ChunkU32 { chunks }
}
/// Store `val` at `idx` (shift/mask chunk lookup; hot scatter-fill path).
#[inline(always)]
pub fn set(&mut self, idx: usize, val: u32) {
let c = idx >> CHUNK_LOG;
let o = idx & CHUNK_MASK;
self.chunks[c][o] = val;
}
/// Get the value at `idx`.
#[inline(always)]
pub fn get(&self, idx: usize) -> u32 {
let c = idx >> CHUNK_LOG;
let o = idx & CHUNK_MASK;
self.chunks[c][o]
}
/// Free every chunk whose slots are entirely below `boundary` (exclusive).
/// Idempotent: already-freed chunks stay empty. Call as the Phase-4 read
/// cursor advances so consumed backing memory is returned promptly.
/// Uses MADV_FREE (after drop) to hint the OS to reclaim pages.
pub fn free_below(&mut self, boundary: usize) {
let last_chunk = boundary >> CHUNK_LOG; // chunks strictly before this are fully consumed
for c in 0..last_chunk {
if !self.chunks[c].is_empty() {
#[cfg(target_os = "linux")]
let (ptr, len) = {
let chunk = &self.chunks[c];
(
chunk.as_ptr() as *mut libc::c_void,
chunk.len() * std::mem::size_of::<u32>(),
)
};
self.chunks[c] = Vec::new();
// MADV_FREE after drop: pages are now in glibc's free-list;
// the hint tells the kernel it can reclaim them under pressure
// without corrupting glibc's bookkeeping (unlike MADV_DONTNEED
// which zero-fills immediately and can corrupt free-list metadata).
#[cfg(target_os = "linux")]
unsafe {
libc::madvise(ptr, len, 8 /* MADV_FREE */);
}
}
}
}
/// Copy the slots [start, end) into `out` (cleared first). The range may
/// straddle a chunk boundary; both source chunks must still be live.
pub fn copy_range(&self, start: usize, end: usize, out: &mut Vec<u32>) {
out.clear();
let mut i = start;
while i < end {
let c = i >> CHUNK_LOG;
let o = i & CHUNK_MASK;
let chunk = &self.chunks[c];
let take = (CHUNK_LEN - o).min(end - i);
out.extend_from_slice(&chunk[o..o + take]);
i += take;
}
}
/// Return a direct slice for `[start, end)` when the range lies entirely
/// within a single chunk. Returns `None` when the range straddles a boundary
/// (caller must fall back to `get` or `copy_range`). Zero-cost for the
/// common case where a node's adjacency list fits inside one 256 MB chunk.
#[inline(always)]
pub fn range_slice(&self, start: usize, end: usize) -> Option<&[u32]> {
if start >= end {
return Some(&[]);
}
let c0 = start >> CHUNK_LOG;
let c1 = (end - 1) >> CHUNK_LOG;
if c0 == c1 {
let o0 = start & CHUNK_MASK;
let o1 = end & CHUNK_MASK;
// end is exclusive; if end falls exactly on a chunk boundary, o1==0
// which means the slice ends at the chunk's last element.
let end_off = if o1 == 0 { CHUNK_LEN } else { o1 };
Some(&self.chunks[c0][o0..end_off])
} else {
None
}
}
}