formualizer_eval/engine/
lookup_index_cache.rs

1use std::hash::{Hash, Hasher};
2use std::sync::atomic::{AtomicUsize, Ordering};
3use std::sync::{Arc, RwLock};
4
5use formualizer_common::{ExcelError, LiteralValue, SheetId};
6use rustc_hash::FxHashMap;
7use smallvec::SmallVec;
8
9use crate::builtins::lookup::lookup_utils::cmp_for_lookup;
10use crate::engine::{DateSystem, range_view::RangeView};
11
12#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
13pub struct LookupIndexKey {
14    pub(crate) sheet_id: SheetId,
15    pub(crate) start_row: u32,
16    pub(crate) start_col: u32,
17    pub(crate) end_row: u32,
18    pub(crate) end_col: u32,
19    pub(crate) axis: LookupAxis,
20    pub(crate) snapshot_id: u64,
21}
22
23#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
24pub enum LookupAxis {
25    ColumnInView(usize),
26    RowInView(usize),
27}
28
29#[derive(Debug, Eq, PartialEq)]
30pub enum LookupHashKey {
31    Number(u64),
32    Text(Box<str>),
33    Boolean(bool),
34    Empty,
35}
36
37impl Hash for LookupHashKey {
38    fn hash<H: Hasher>(&self, state: &mut H) {
39        match self {
40            Self::Number(bits) => {
41                0u8.hash(state);
42                bits.hash(state);
43            }
44            Self::Text(text) => {
45                1u8.hash(state);
46                text.hash(state);
47            }
48            Self::Boolean(value) => {
49                2u8.hash(state);
50                value.hash(state);
51            }
52            Self::Empty => {
53                3u8.hash(state);
54            }
55        }
56    }
57}
58
59impl LookupHashKey {
60    fn from_needle(value: &LiteralValue, date_system: DateSystem) -> Option<Self> {
61        // Blank needles retain numeric-zero coercion; blank candidates do not.
62        if matches!(value, LiteralValue::Empty) {
63            Some(Self::Number(0.0f64.to_bits()))
64        } else {
65            Self::from_literal(value, date_system)
66        }
67    }
68
69    pub(crate) fn from_literal(value: &LiteralValue, date_system: DateSystem) -> Option<Self> {
70        match value {
71            LiteralValue::Number(n) => Some(Self::Number(normalize_f64_bits(*n))),
72            LiteralValue::Int(i) => Some(Self::Number(normalize_f64_bits(*i as f64))),
73            LiteralValue::Text(s) => Some(Self::Text(s.to_lowercase().into_boxed_str())),
74            LiteralValue::Boolean(b) => Some(Self::Boolean(*b)),
75            LiteralValue::Empty => None,
76            // Temporal values are numbers in Excel: key them by their serial so
77            // an exact lookup finds them whether the needle or the cell (or
78            // both) carry a temporal type rather than a plain numeric.
79            LiteralValue::Date(_) | LiteralValue::DateTime(_) | LiteralValue::Time(_) => value
80                .as_serial_number_for(date_system)
81                .map(|serial| Self::Number(normalize_f64_bits(serial))),
82            LiteralValue::Error(_)
83            | LiteralValue::Array(_)
84            | LiteralValue::Duration(_)
85            | LiteralValue::Pending => None,
86        }
87    }
88}
89
90fn normalize_f64_bits(n: f64) -> u64 {
91    if n.is_nan() {
92        return f64::NAN.to_bits();
93    }
94    let rounded = n.round();
95    if (n - rounded).abs() < 1e-12 {
96        // Exact comparisons identify signed zero; the index must do so too.
97        if rounded == 0.0 {
98            0.0f64.to_bits()
99        } else {
100            rounded.to_bits()
101        }
102    } else {
103        n.to_bits()
104    }
105}
106
107#[derive(Debug, Clone, Default)]
108pub struct DuplicateIndices {
109    pub(crate) first: usize,
110    pub(crate) last: usize,
111    pub(crate) all: SmallVec<[usize; 1]>,
112}
113
114pub struct LookupIndex {
115    pub(crate) len: usize,
116    date_system: DateSystem,
117    pub(crate) bytes: usize,
118    pub(crate) entries: FxHashMap<LookupHashKey, DuplicateIndices>,
119    pub(crate) cell_values: Box<[LiteralValue]>,
120}
121
122#[cfg(test)]
123thread_local! {
124    static BUILD_ATTEMPTS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
125}
126
127#[cfg(test)]
128pub(crate) fn take_build_attempts() -> usize {
129    BUILD_ATTEMPTS.with(|c| c.replace(0))
130}
131
132impl LookupIndex {
133    pub(crate) fn build(
134        view: &RangeView<'_>,
135        axis: LookupAxis,
136        date_system: DateSystem,
137    ) -> Result<BuildOutcome, ExcelError> {
138        #[cfg(test)]
139        BUILD_ATTEMPTS.with(|c| c.set(c.get() + 1));
140        let (rows, cols) = view.dims();
141        let len = match axis {
142            LookupAxis::ColumnInView(col) => {
143                if col >= cols {
144                    return Ok(BuildOutcome::Degenerate);
145                }
146                rows
147            }
148            LookupAxis::RowInView(row) => {
149                if row >= rows {
150                    return Ok(BuildOutcome::Degenerate);
151                }
152                cols
153            }
154        };
155        if len == 0 {
156            return Ok(BuildOutcome::Degenerate);
157        }
158
159        let mut entries: FxHashMap<LookupHashKey, DuplicateIndices> =
160            FxHashMap::with_capacity_and_hasher(len, Default::default());
161        let mut cell_values = Vec::with_capacity(len);
162        let mut error_count = 0usize;
163
164        for idx in 0..len {
165            let value = match axis {
166                LookupAxis::ColumnInView(col) => view.get_cell(idx, col),
167                LookupAxis::RowInView(row) => view.get_cell(row, idx),
168            };
169            if matches!(value, LiteralValue::Error(_)) {
170                error_count += 1;
171            }
172            if let Some(key) = LookupHashKey::from_literal(&value, date_system) {
173                let dups = entries.entry(key).or_insert_with(|| DuplicateIndices {
174                    first: idx,
175                    last: idx,
176                    all: SmallVec::new(),
177                });
178                if dups.all.is_empty() {
179                    dups.first = idx;
180                }
181                dups.last = idx;
182                dups.all.push(idx);
183            }
184            cell_values.push(value);
185        }
186
187        if error_count > 0 {
188            return Ok(BuildOutcome::ErrorInLookupAxis);
189        }
190
191        // Sized for distinct keys up front; a column of repeated keys
192        // gives the unused buckets back.
193        if entries.len().saturating_mul(2) < entries.capacity() {
194            entries.shrink_to_fit();
195        }
196        let bytes = retained_bytes(&cell_values, &entries);
197        Ok(BuildOutcome::Built(Self {
198            len,
199            date_system,
200            bytes,
201            entries,
202            cell_values: cell_values.into_boxed_slice(),
203        }))
204    }
205
206    pub(crate) fn find_first_exact(&self, needle: &LiteralValue) -> Option<usize> {
207        let hash_key = LookupHashKey::from_needle(needle, self.date_system)?;
208        if let Some(dups) = self.entries.get(&hash_key) {
209            for &idx in &dups.all {
210                if cmp_for_lookup(needle, &self.cell_values[idx], self.date_system) == Some(0) {
211                    return Some(idx);
212                }
213            }
214        }
215        None
216    }
217
218    pub(crate) fn find_last_exact(&self, needle: &LiteralValue) -> Option<usize> {
219        let hash_key = LookupHashKey::from_needle(needle, self.date_system)?;
220        if let Some(dups) = self.entries.get(&hash_key) {
221            for &idx in dups.all.iter().rev() {
222                if cmp_for_lookup(needle, &self.cell_values[idx], self.date_system) == Some(0) {
223                    return Some(idx);
224                }
225            }
226        }
227        None
228    }
229}
230
231fn retained_bytes(
232    values: &[LiteralValue],
233    entries: &FxHashMap<LookupHashKey, DuplicateIndices>,
234) -> usize {
235    // HashMap capacity excludes control bytes and vacant buckets. Round up to
236    // the backing power-of-two bucket count; allocator bookkeeping is estimated.
237    let buckets = if entries.capacity() == 0 {
238        0
239    } else {
240        entries.capacity().saturating_add(1).next_power_of_two()
241    };
242    let mut bytes = values
243        .len()
244        .saturating_mul(std::mem::size_of::<LiteralValue>())
245        .saturating_add(
246            buckets.saturating_mul(std::mem::size_of::<(LookupHashKey, DuplicateIndices)>() + 1),
247        )
248        .saturating_add(256);
249    for value in values {
250        bytes = bytes.saturating_add(literal_payload_bytes(value));
251    }
252    for (key, indices) in entries {
253        if let LookupHashKey::Text(text) = key {
254            bytes = bytes.saturating_add(text.len());
255        }
256        if indices.all.spilled() {
257            bytes = bytes.saturating_add(
258                indices
259                    .all
260                    .capacity()
261                    .saturating_mul(std::mem::size_of::<usize>()),
262            );
263        }
264    }
265    bytes
266}
267
268fn literal_payload_bytes(value: &LiteralValue) -> usize {
269    match value {
270        LiteralValue::Text(text) => text.capacity(),
271        LiteralValue::Array(rows) => rows.iter().fold(
272            rows.capacity()
273                .saturating_mul(std::mem::size_of::<Vec<LiteralValue>>()),
274            |bytes, row| {
275                row.iter().fold(
276                    bytes.saturating_add(
277                        row.capacity()
278                            .saturating_mul(std::mem::size_of::<LiteralValue>()),
279                    ),
280                    |bytes, value| bytes.saturating_add(literal_payload_bytes(value)),
281                )
282            },
283        ),
284        _ => 0,
285    }
286}
287
288pub(crate) fn estimate_bytes(len: usize, entries: usize) -> usize {
289    len.saturating_mul(std::mem::size_of::<LiteralValue>().saturating_add(8))
290        .saturating_add(entries.saturating_mul(96))
291        .saturating_add(256)
292}
293
294pub(crate) enum BuildOutcome {
295    Built(LookupIndex),
296    ErrorInLookupAxis,
297    Degenerate,
298}
299
300const LOOKUP_INDEX_BUILD_THRESHOLD: u32 = 3;
301const CAP_REJECTED: u32 = u32::MAX;
302const CALL_COUNT_PRUNE_LIMIT: usize = 4096;
303
304#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
305pub struct LookupIndexCacheReport {
306    pub(crate) builds: usize,
307    pub(crate) hits: usize,
308    pub(crate) misses: usize,
309    pub(crate) skipped_volatile: usize,
310    pub(crate) skipped_error: usize,
311    pub(crate) skipped_tiny: usize,
312    pub(crate) skipped_cap: usize,
313    pub(crate) skipped_below_threshold: usize,
314    pub(crate) bytes_in_cache: usize,
315    pub(crate) entries_count: usize,
316}
317
318pub struct LookupIndexCache {
319    inner: RwLock<FxHashMap<LookupIndexKey, Arc<LookupIndex>>>,
320    call_counts: RwLock<FxHashMap<LookupIndexKey, u32>>,
321    volatile_keys: RwLock<FxHashMap<LookupIndexKey, ()>>,
322    build_threshold: u32,
323    bytes_in_use: AtomicUsize,
324    max_bytes: usize,
325    builds: AtomicUsize,
326    hits: AtomicUsize,
327    misses: AtomicUsize,
328    skipped_volatile: AtomicUsize,
329    skipped_error: AtomicUsize,
330    skipped_tiny: AtomicUsize,
331    skipped_cap: AtomicUsize,
332    skipped_below_threshold: AtomicUsize,
333    /// Program 3: builds in progress. Parallel members of a lookup family
334    /// miss the cache together; one builds the index and the others wait
335    /// for it instead of each building (and allocating) a copy.
336    in_flight: std::sync::Mutex<FxHashMap<LookupIndexKey, Arc<BuildFlight>>>,
337    /// Index builds started from `single_flight` (tests).
338    #[cfg(test)]
339    pub(crate) flights_built: AtomicUsize,
340}
341
342/// The outcome of one in-progress build, shared by the callers waiting on it.
343pub(crate) type BuildFlight = std::sync::OnceLock<Option<Arc<LookupIndex>>>;
344
345fn volatile_key(mut key: LookupIndexKey) -> LookupIndexKey {
346    key.snapshot_id = 0;
347    key
348}
349
350impl LookupIndexCache {
351    pub(crate) fn new(max_bytes: usize) -> Self {
352        Self {
353            inner: RwLock::new(FxHashMap::default()),
354            call_counts: RwLock::new(FxHashMap::default()),
355            volatile_keys: RwLock::new(FxHashMap::default()),
356            build_threshold: LOOKUP_INDEX_BUILD_THRESHOLD,
357            bytes_in_use: AtomicUsize::new(0),
358            max_bytes,
359            builds: AtomicUsize::new(0),
360            hits: AtomicUsize::new(0),
361            misses: AtomicUsize::new(0),
362            skipped_volatile: AtomicUsize::new(0),
363            skipped_error: AtomicUsize::new(0),
364            skipped_tiny: AtomicUsize::new(0),
365            skipped_cap: AtomicUsize::new(0),
366            skipped_below_threshold: AtomicUsize::new(0),
367            in_flight: std::sync::Mutex::new(FxHashMap::default()),
368            #[cfg(test)]
369            flights_built: AtomicUsize::new(0),
370        }
371    }
372
373    /// Run `build` once for `key` among concurrent callers: the first
374    /// caller builds, the others block until it has finished and share its
375    /// outcome.
376    pub(crate) fn single_flight(
377        &self,
378        key: LookupIndexKey,
379        build: impl FnOnce() -> Option<Arc<LookupIndex>>,
380    ) -> Option<Arc<LookupIndex>> {
381        let flight = {
382            let Ok(mut guard) = self.in_flight.lock() else {
383                return build();
384            };
385            Arc::clone(guard.entry(key).or_default())
386        };
387        let mut built = false;
388        let outcome = flight
389            .get_or_init(|| {
390                built = true;
391                build()
392            })
393            .clone();
394        // A waiter's shared outcome is a cache hit (as a duplicate build
395        // finding the entry in `insert_if_room` was).
396        if !built && outcome.is_some() {
397            self.hits.fetch_add(1, Ordering::Relaxed);
398        }
399        if let Ok(mut guard) = self.in_flight.lock()
400            && guard.get(&key).is_some_and(|f| Arc::ptr_eq(f, &flight))
401        {
402            guard.remove(&key);
403        }
404        outcome
405    }
406
407    // Called only at an exclusive Engine mutation boundary, after all evaluation
408    // workers have joined. No old-generation builder can race this reclamation.
409    pub(crate) fn clear(&mut self) {
410        self.inner
411            .get_mut()
412            .unwrap_or_else(|p| p.into_inner())
413            .clear();
414        self.call_counts
415            .get_mut()
416            .unwrap_or_else(|p| p.into_inner())
417            .clear();
418        self.volatile_keys
419            .get_mut()
420            .unwrap_or_else(|p| p.into_inner())
421            .clear();
422        self.bytes_in_use.store(0, Ordering::Relaxed);
423        self.in_flight
424            .get_mut()
425            .unwrap_or_else(|p| p.into_inner())
426            .clear();
427    }
428
429    pub(crate) fn get(&self, key: &LookupIndexKey) -> Option<Arc<LookupIndex>> {
430        let found = self
431            .inner
432            .read()
433            .ok()
434            .and_then(|guard| guard.get(key).cloned());
435        if found.is_some() {
436            self.hits.fetch_add(1, Ordering::Relaxed);
437        } else {
438            self.misses.fetch_add(1, Ordering::Relaxed);
439        }
440        found
441    }
442
443    /// A builder's re-check after its `get` missed: an entry published in
444    /// between is a hit (no second miss is counted).
445    pub(crate) fn recheck(&self, key: &LookupIndexKey) -> Option<Arc<LookupIndex>> {
446        let found = self
447            .inner
448            .read()
449            .ok()
450            .and_then(|guard| guard.get(key).cloned());
451        if found.is_some() {
452            self.hits.fetch_add(1, Ordering::Relaxed);
453        }
454        found
455    }
456
457    pub(crate) fn should_build(&self, key: LookupIndexKey) -> bool {
458        let Ok(mut guard) = self.call_counts.write() else {
459            self.skipped_below_threshold.fetch_add(1, Ordering::Relaxed);
460            return false;
461        };
462        if guard.len() > CALL_COUNT_PRUNE_LIMIT {
463            guard.retain(|existing_key, _| existing_key.snapshot_id == key.snapshot_id);
464        }
465        let count = guard.entry(key).or_insert(0);
466        if *count == CAP_REJECTED {
467            self.skipped_cap.fetch_add(1, Ordering::Relaxed);
468            return false;
469        }
470        *count = count.saturating_add(1).min(CAP_REJECTED - 1);
471        if *count <= self.build_threshold {
472            self.skipped_below_threshold.fetch_add(1, Ordering::Relaxed);
473            return false;
474        }
475        true
476    }
477
478    pub(crate) fn would_exceed_cap(&self, bytes: usize) -> bool {
479        self.bytes_in_use
480            .load(Ordering::Relaxed)
481            .saturating_add(bytes)
482            > self.max_bytes
483    }
484
485    pub(crate) fn is_known_volatile(&self, key: &LookupIndexKey) -> bool {
486        let volatile_key = volatile_key(*key);
487        self.volatile_keys
488            .read()
489            .map(|guard| guard.contains_key(&volatile_key))
490            .unwrap_or(false)
491    }
492
493    pub(crate) fn note_volatile_key(&self, key: LookupIndexKey) {
494        if let Ok(mut guard) = self.volatile_keys.write() {
495            if guard.len() > CALL_COUNT_PRUNE_LIMIT {
496                guard.clear();
497            }
498            guard.insert(volatile_key(key), ());
499        }
500    }
501
502    pub(crate) fn insert_if_room(
503        &self,
504        key: LookupIndexKey,
505        index: LookupIndex,
506    ) -> Option<Arc<LookupIndex>> {
507        let bytes = index.bytes;
508        if let Ok(mut guard) = self.inner.write() {
509            if let Some(existing) = guard.get(&key) {
510                self.hits.fetch_add(1, Ordering::Relaxed);
511                return Some(existing.clone());
512            }
513            // Serialize duplicate detection, admission and accounting. The earlier
514            // preflight estimate is only a hint and cannot reserve concurrent space.
515            let current = self.bytes_in_use.load(Ordering::Relaxed);
516            if bytes > self.max_bytes.saturating_sub(current) {
517                self.skipped_cap.fetch_add(1, Ordering::Relaxed);
518                // Actual payloads (especially text) can exceed the preflight
519                // estimate. Do not rebuild and discard them on every later call.
520                if let Ok(mut counts) = self.call_counts.write() {
521                    counts.insert(key, CAP_REJECTED);
522                }
523                return None;
524            }
525            let index = Arc::new(index);
526            guard.insert(key, index.clone());
527            self.bytes_in_use.fetch_add(bytes, Ordering::Relaxed);
528            self.builds.fetch_add(1, Ordering::Relaxed);
529            Some(index)
530        } else {
531            None
532        }
533    }
534
535    pub(crate) fn note_skipped_volatile(&self) {
536        self.skipped_volatile.fetch_add(1, Ordering::Relaxed);
537    }
538
539    pub(crate) fn note_skipped_error(&self) {
540        self.skipped_error.fetch_add(1, Ordering::Relaxed);
541    }
542
543    pub(crate) fn note_skipped_tiny(&self) {
544        self.skipped_tiny.fetch_add(1, Ordering::Relaxed);
545    }
546
547    pub(crate) fn note_skipped_cap(&self) {
548        self.skipped_cap.fetch_add(1, Ordering::Relaxed);
549    }
550
551    pub(crate) fn reset_counters(&self) {
552        self.builds.store(0, Ordering::Relaxed);
553        self.hits.store(0, Ordering::Relaxed);
554        self.misses.store(0, Ordering::Relaxed);
555        self.skipped_volatile.store(0, Ordering::Relaxed);
556        self.skipped_error.store(0, Ordering::Relaxed);
557        self.skipped_tiny.store(0, Ordering::Relaxed);
558        self.skipped_cap.store(0, Ordering::Relaxed);
559        self.skipped_below_threshold.store(0, Ordering::Relaxed);
560    }
561
562    pub(crate) fn report(&self) -> LookupIndexCacheReport {
563        let guard = self.inner.read().ok();
564        let entries_count = guard.as_ref().map_or(0, |guard| guard.len());
565        LookupIndexCacheReport {
566            builds: self.builds.load(Ordering::Relaxed),
567            hits: self.hits.load(Ordering::Relaxed),
568            misses: self.misses.load(Ordering::Relaxed),
569            skipped_volatile: self.skipped_volatile.load(Ordering::Relaxed),
570            skipped_error: self.skipped_error.load(Ordering::Relaxed),
571            skipped_tiny: self.skipped_tiny.load(Ordering::Relaxed),
572            skipped_cap: self.skipped_cap.load(Ordering::Relaxed),
573            skipped_below_threshold: self.skipped_below_threshold.load(Ordering::Relaxed),
574            bytes_in_cache: self.bytes_in_use.load(Ordering::Relaxed),
575            entries_count,
576        }
577    }
578}
579
580#[cfg(test)]
581mod tests {
582    use super::*;
583    use chrono::NaiveTime;
584
585    fn key(col: u32) -> LookupIndexKey {
586        LookupIndexKey {
587            sheet_id: 0,
588            start_row: 0,
589            start_col: col,
590            end_row: 128,
591            end_col: col,
592            axis: LookupAxis::ColumnInView(0),
593            snapshot_id: 1,
594        }
595    }
596    fn index(bytes: usize) -> LookupIndex {
597        LookupIndex {
598            len: 0,
599            date_system: DateSystem::Excel1900,
600            bytes,
601            entries: FxHashMap::default(),
602            cell_values: Box::new([]),
603        }
604    }
605
606    #[test]
607    fn exact_index_selects_signed_zero_and_temporal_zero_duplicates() {
608        assert_eq!(
609            LookupHashKey::from_literal(&LiteralValue::Empty, DateSystem::Excel1900),
610            None
611        );
612        assert_eq!(
613            LookupHashKey::from_needle(&LiteralValue::Empty, DateSystem::Excel1900),
614            Some(LookupHashKey::Number(0.0f64.to_bits()))
615        );
616        let midnight = LiteralValue::Time(NaiveTime::from_hms_opt(0, 0, 0).unwrap());
617        let values = vec![
618            LiteralValue::Empty,
619            LiteralValue::Boolean(false),
620            LiteralValue::Text("0".into()),
621            LiteralValue::Number(-0.0),
622            midnight.clone(),
623            LiteralValue::Number(0.0),
624            LiteralValue::Boolean(false),
625            LiteralValue::Text("0".into()),
626        ];
627        let view = RangeView::from_owned_rows(
628            values.into_iter().map(|value| vec![value]).collect(),
629            DateSystem::Excel1900,
630        );
631        let BuildOutcome::Built(index) =
632            LookupIndex::build(&view, LookupAxis::ColumnInView(0), DateSystem::Excel1900).unwrap()
633        else {
634            panic!("expected a lookup index");
635        };
636
637        assert_eq!(index.find_first_exact(&LiteralValue::Number(0.0)), Some(3));
638        assert_eq!(index.find_last_exact(&LiteralValue::Number(-0.0)), Some(5));
639        assert_eq!(index.find_first_exact(&midnight), Some(3));
640        assert_eq!(index.find_last_exact(&midnight), Some(5));
641        assert_eq!(index.find_first_exact(&LiteralValue::Empty), Some(3));
642        assert_eq!(index.find_last_exact(&LiteralValue::Empty), Some(5));
643
644        let temporal_only_view = RangeView::from_owned_rows(
645            vec![
646                vec![LiteralValue::Empty],
647                vec![LiteralValue::Boolean(false)],
648                vec![LiteralValue::Text("0".into())],
649                vec![midnight],
650            ],
651            DateSystem::Excel1900,
652        );
653        let BuildOutcome::Built(temporal_only) = LookupIndex::build(
654            &temporal_only_view,
655            LookupAxis::ColumnInView(0),
656            DateSystem::Excel1900,
657        )
658        .unwrap() else {
659            panic!("expected a temporal lookup index");
660        };
661        assert_eq!(
662            temporal_only.find_first_exact(&LiteralValue::Number(0.0)),
663            Some(3)
664        );
665    }
666
667    #[test]
668    fn concurrent_admission_and_duplicate_races_obey_cap() {
669        for duplicate in [false, true] {
670            let mut cache = LookupIndexCache::new(if duplicate { 1024 } else { 4096 });
671            let barrier = std::sync::Barrier::new(16);
672            std::thread::scope(|scope| {
673                let handles: Vec<_> = (0..16)
674                    .map(|i| {
675                        let cache = &cache;
676                        let barrier = &barrier;
677                        scope.spawn(move || {
678                            barrier.wait();
679                            cache.insert_if_room(key(if duplicate { 0 } else { i }), index(1024))
680                        })
681                    })
682                    .collect();
683                let admitted: Vec<_> = handles
684                    .into_iter()
685                    .filter_map(|h| h.join().unwrap())
686                    .collect();
687                assert_eq!(admitted.len(), if duplicate { 16 } else { 4 });
688                if duplicate {
689                    assert!(admitted.iter().all(|item| Arc::ptr_eq(item, &admitted[0])));
690                }
691            });
692            let report = cache.report();
693            assert_eq!(report.bytes_in_cache, cache.max_bytes);
694            assert_eq!(report.builds, if duplicate { 1 } else { 4 });
695            assert_eq!(report.entries_count, report.builds);
696            assert_eq!(report.skipped_cap, if duplicate { 0 } else { 12 });
697            cache.clear();
698            assert_eq!(cache.report().bytes_in_cache, 0);
699            assert_eq!(cache.report().entries_count, 0);
700            assert!(cache.insert_if_room(key(0), index(1024)).is_some());
701        }
702    }
703
704    #[test]
705    fn retained_text_and_duplicate_heap_payloads_are_charged() {
706        let mut entries = FxHashMap::default();
707        let mut text = String::with_capacity(4096);
708        text.push_str("LONG KEY");
709        let values = [LiteralValue::Text(text)];
710        let empty_bytes = retained_bytes(&[], &entries);
711        assert_eq!(
712            retained_bytes(&values, &entries) - empty_bytes,
713            std::mem::size_of::<LiteralValue>() + 4096
714        );
715        let mut dups = DuplicateIndices::default();
716        dups.all.extend(0..100);
717        let heap_bytes = dups.all.capacity() * std::mem::size_of::<usize>();
718        entries.insert(LookupHashKey::Text("long key".into()), dups);
719        let charged = retained_bytes(&values, &entries);
720        assert!(charged >= empty_bytes + 4096 + 8 + heap_bytes);
721        entries
722            .get_mut(&LookupHashKey::Text("long key".into()))
723            .unwrap()
724            .all = SmallVec::new();
725        assert_eq!(charged - retained_bytes(&values, &entries), heap_bytes);
726        let cache = LookupIndexCache::new(charged - 1);
727        assert!(cache.insert_if_room(key(0), index(charged)).is_none());
728    }
729}
formualizer_eval/engine/lookup_index_cache.rs

formualizer_eval/engine/
lookup_index_cache.rs
