concept_graph/
footprint.rs

1//! What a loaded structure holds in memory, counted allocation by allocation.
2//!
3//! A served edition's resident memory is the sum of the structures it loaded
4//! plus what the allocator and the process keep on top, and a total says
5//! nothing about which structure is which. Every structure here answers
6//! `size_in_bytes`, so the accounting is added up from the structures rather
7//! than inferred from the total. No FHIR or SNOMED CT specification governs
8//! this: our own design.
9//!
10//! What a figure counts is the heap the structure's own allocations hold, at
11//! their capacity rather than their length, because a vector that reserved
12//! more than it filled holds the pages it reserved. What it does not count is
13//! the allocator's own per-allocation header and the slack a `BTreeMap` node
14//! carries; both belong to the residual a caller names against a measured
15//! process footprint.
16
17use std::mem::size_of;
18
19use roaring::RoaringBitmap;
20
21/// The bytes one container of a roaring bitmap costs beside its values.
22///
23// NOTE: roaring 0.11.5 stores `Container { key: u16, store: Store }` in a
24// vector, and `Store`'s widest variant is a `Vec` triple, so a container is a
25// 24-byte vector, an 8-byte tag, and the key in its padding.
26const CONTAINER: usize = 40;
27
28/// The heap bytes `set` holds.
29///
30/// Read through `RoaringBitmap::statistics`, whose per-container byte counts
31/// are the serialized widths rather than the in-memory ones: an array
32/// container stores `u16` values and is counted at `u32`, and a bitset
33/// container is counted in bits. Both are converted here.
34#[must_use]
35#[expect(
36    clippy::integer_division,
37    reason = "both counts are exact multiples of their divisor, so no remainder exists to lose"
38)]
39pub fn bitmap(set: &RoaringBitmap) -> usize {
40    let stats = set.statistics();
41    let containers = usize::try_from(stats.n_containers).unwrap_or(usize::MAX);
42    let arrays = usize::try_from(stats.n_bytes_array_containers).unwrap_or(usize::MAX) / 2;
43    let bitsets = usize::try_from(stats.n_bytes_bitset_containers).unwrap_or(usize::MAX) / 8;
44    let runs = usize::try_from(stats.n_bytes_run_containers).unwrap_or(usize::MAX);
45    arrays
46        .saturating_add(bitsets)
47        .saturating_add(runs)
48        .saturating_add(containers.saturating_mul(CONTAINER))
49}
50
51/// The heap bytes a list of bitmaps holds, the list's own vector included.
52#[must_use]
53pub fn bitmaps(sets: &[RoaringBitmap]) -> usize {
54    let own = sets.len().saturating_mul(size_of::<RoaringBitmap>());
55    sets.iter()
56        .fold(own, |total, set| total.saturating_add(bitmap(set)))
57}
58
59/// The heap bytes a vector holds, its unfilled capacity included.
60#[must_use]
61pub fn vector<T>(values: &Vec<T>) -> usize {
62    values.capacity().saturating_mul(size_of::<T>())
63}
64
65/// The heap bytes a vector of strings holds, the text included.
66#[must_use]
67pub fn strings(values: &Vec<String>) -> usize {
68    values.iter().fold(vector(values), |total, text| {
69        total.saturating_add(text.capacity())
70    })
71}
72
73/// The heap bytes the entries of a map hold, without the text or bitmaps in
74/// them.
75///
76/// A `BTreeMap` packs its entries into nodes, so this is the entries at their
77/// own width; the slack of a partly filled node is left to the residual.
78#[must_use]
79pub fn entries<K, V>(len: usize) -> usize {
80    len.saturating_mul(size_of::<K>().saturating_add(size_of::<V>()))
81}
82
83#[cfg(test)]
84mod tests {
85    use roaring::RoaringBitmap;
86
87    use super::{bitmap, bitmaps, entries, strings, vector};
88
89    #[test]
90    fn an_empty_bitmap_holds_nothing() {
91        assert_eq!(bitmap(&RoaringBitmap::new()), 0);
92    }
93
94    #[test]
95    fn a_sparse_bitmap_costs_two_bytes_a_value_and_one_container() {
96        let set: RoaringBitmap = (0..100).collect();
97        // One array container of at least 100 u16 values, plus its header.
98        assert!(bitmap(&set) >= 200 + 40, "{}", bitmap(&set));
99        assert!(bitmap(&set) < 1024, "{}", bitmap(&set));
100    }
101
102    #[test]
103    fn a_dense_bitmap_costs_a_bitset_container() {
104        let set: RoaringBitmap = (0..20_000).collect();
105        // 1024 u64 words is 8 KiB, whatever the cardinality above the array
106        // limit, plus the container header.
107        assert_eq!(bitmap(&set), 8192 + 40);
108    }
109
110    #[test]
111    fn a_list_of_bitmaps_carries_its_own_vector() {
112        let sets = vec![RoaringBitmap::new(), RoaringBitmap::new()];
113        assert_eq!(bitmaps(&sets), 2 * size_of::<RoaringBitmap>());
114    }
115
116    #[test]
117    fn a_vector_is_counted_at_its_capacity() {
118        let mut values: Vec<u32> = Vec::with_capacity(16);
119        values.push(1);
120        assert_eq!(vector(&values), 64);
121    }
122
123    #[test]
124    fn strings_carry_their_text() {
125        let values = vec![String::from("abcd")];
126        assert_eq!(strings(&values), vector(&values) + 4);
127    }
128
129    #[test]
130    fn map_entries_are_counted_at_their_own_width() {
131        assert_eq!(entries::<u64, u32>(10), 10 * (8 + 4));
132    }
133}
concept_graph/footprint.rs

concept_graph/
footprint.rs
