functions: MODE counts through an index, FREQUENCY bins by binary search

MODE/MODE.SNGL/MODE.MULT searched the list of distinct numbers seen so far
for every input, and FREQUENCY scanned the sorted bins for every data value,
so both were quadratic in computed arrays. MODE now keys counts by value
(-0 folded into 0, NaN never merged) and keeps first-occurrence order;
FREQUENCY finds the first bin at or above each value with partition_point
over the order it already sorts. Results are unchanged.

crates/functions/src/lift.rs

@@ -68,70 +68,26 @@ const SCANS: &[&str] = &["VLOOKUP", "HLOOKUP", "LOOKUP", "MATCH", "XLOOKUP", "XM
 /// `XMATCH(SEQUENCE(1048576), -SEQUENCE(1048576))` runs for hours and hangs opening the file.
 /// Past the budget the call is `#NUM!`, as MMULT is past 2e9 multiply-adds. 5e8 keeps the worst
 /// case to a few seconds and still admits 5,000 needles over a 100,000-row table.
-///
-/// The same budget covers all the work of a lifted call added up across its elements: criteria
-/// aggregates rescanning their ranges, period loops, and array results built per element.
 const LIFTED_SCAN_BUDGET: usize = 500_000_000;
 
-/// Criteria aggregates: every call tests each cell of its ranges against its criteria, so a call
-/// lifted over `n` criteria does `n` x (range cells) work, like the [`SCANS`] lookups.
-const CRITERIA: &[&str] = &["COUNTIF", "COUNTIFS", "SUMIF", "SUMIFS", "AVERAGEIF", "AVERAGEIFS", "MAXIFS", "MINIFS"];
-
-/// Cumulative TVM functions that step through every period from `start_period` (argument 3) to
-/// `end_period` (argument 4) on each call.
-const PERIOD_LOOPS: &[&str] = &["CUMIPMT", "CUMPRINC"];
-
-/// The work every lifted call of `spec` repeats over its non-lifted arguments: the longest vector
-/// a [`SCANS`] lookup searches, or every cell a [`CRITERIA`] aggregate tests. 0 for other
-/// functions.
+/// The length of the longest vector a lifted call of `spec` searches per needle: 0 unless `spec`
+/// is one of the [`SCANS`] lookups and a non-lifted argument is an array.
 fn scan_len(spec: &FnSpec, args: &[Arg]) -> usize {
-    let scans = SCANS.contains(&spec.name);
-    if !scans && !CRITERIA.contains(&spec.name) {
+    if !SCANS.contains(&spec.name) {
         return 0;
     }
-    let lens = args.iter().enumerate().filter(|(i, _)| !spec.is_scalar_arg(*i)).filter_map(|(_, a)| match &a.value {
-        Value::Array(arr) => Some(if scans { arr.rows.max(arr.cols) } else { arr.data.len() }),
-        _ => None,
-    });
-    if scans { lens.max().unwrap_or(0) } else { lens.fold(0, usize::saturating_add) }
-}
-
-/// The work of one lifted call that depends on its own (lifted) scalar arguments: the number of
-/// periods a [`PERIOD_LOOPS`] function steps through. 0 for other functions.
-fn call_cost(spec: &FnSpec, cell_args: &[Arg]) -> usize {
-    if !PERIOD_LOOPS.contains(&spec.name) {
-        return 0;
-    }
-    let period = |i: usize| match cell_args.get(i).map(|a| &a.value) {
-        Some(Value::Number(n)) if n.is_finite() => Some(n.trunc()),
-        _ => None,
-    };
-    match (period(3), period(4)) {
-        // The function itself refuses spans past 1e7 periods; anything larger costs the cap.
-        (Some(start), Some(end)) if end >= start => ((end - start) + 1.0).min(1e8) as usize,
-        _ => 0,
-    }
+    args.iter()
+        .enumerate()
+        .filter(|(i, _)| !spec.is_scalar_arg(*i))
+        .filter_map(|(_, a)| match &a.value {
+            Value::Array(arr) => Some(arr.rows.max(arr.cols)),
+            _ => None,
+        })
+        .max()
+        .unwrap_or(0)
 }
 
 pub(crate) fn call_lifted(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx) -> Value {
-    call_lifted_within(spec, args, ctx, LIFTED_SCAN_BUDGET)
-}
-
-/// Sets the lifted arguments of `cell_args` to their elements at (`r`, `c`).
-fn element_args(spec: &FnSpec, args: &[Arg], r: usize, c: usize, cell_args: &mut [Arg]) {
-    for (i, a) in args.iter().enumerate() {
-        if spec.is_scalar_arg(i)
-            && let Value::Array(arr) = &a.value
-            && let Some(slot) = cell_args.get_mut(i)
-        {
-            let v = arr.get_broadcast(r, c);
-            slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
-        }
-    }
-}
-
-/// [`call_lifted`] with every call's work added up against `budget` (see [`LIFTED_SCAN_BUDGET`]).
-fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: usize) -> Value {
     let rejected = if spec.value_args.is_empty() { None } else { reject_multi_cell_refs(spec, args) };
     let args = rejected.as_deref().unwrap_or(args);
     let mut rows = 0usize;
@@ -150,42 +106,25 @@ fn call_lifted_within(spec: &FnSpec, args: &[Arg], ctx: &mut dyn Ctx, budget: us
         return (spec.imp)(args, ctx);
     }
     let needles = rows.saturating_mul(cols);
-    // Every call is charged its repeated scan (at least 1), its own period loop, and the cells of
-    // an array result (built in full, though only its first cell is kept), so lifting a scalar
-    // argument can't multiply what one call may do into hours of work:
-    // `COUNTIF(big_range, SEQUENCE(1e4))`, `CUMIPMT(0.1, 1e7, 1, 1, SEQUENCE(1e4,,1e7,0), 0)`,
-    // `MUNIT(SEQUENCE(1e4,,3000,0))`.
-    let per_call = scan_len(spec, args).max(1);
-    let mut cell_args: Vec<Arg> = args.to_vec();
-    let mut spent = needles.saturating_mul(per_call);
-    if needles > MAX_CELLS || spent > budget {
+    if needles > MAX_CELLS || needles.saturating_mul(scan_len(spec, args)) > LIFTED_SCAN_BUDGET {
         return Value::Error(CellError::Num);
     }
-    // Period loops are known before any call runs, so a call over budget does none of them.
-    if PERIOD_LOOPS.contains(&spec.name) {
-        for r in 0..rows {
-            for c in 0..cols {
-                element_args(spec, args, r, c, &mut cell_args);
-                spent = spent.saturating_add(call_cost(spec, &cell_args));
-                if spent > budget {
-                    return Value::Error(CellError::Num);
-                }
-            }
-        }
-    }
+    let mut cell_args: Vec<Arg> = args.to_vec();
     let mut data = Vec::with_capacity(rows * cols);
     for r in 0..rows {
         for c in 0..cols {
-            element_args(spec, args, r, c, &mut cell_args);
+            for (i, a) in args.iter().enumerate() {
+                if spec.is_scalar_arg(i)
+                    && let Value::Array(arr) = &a.value
+                    && let Some(slot) = cell_args.get_mut(i)
+                {
+                    let v = arr.get_broadcast(r, c);
+                    slot.value = if let Value::Array(inner) = &v { inner.data.first().cloned().unwrap_or(Value::Empty) } else { v };
+                }
+            }
             let out = (spec.imp)(&cell_args, ctx);
             data.push(match out {
-                Value::Array(a) => {
-                    spent = spent.saturating_add(a.data.len());
-                    if spent > budget {
-                        return Value::Error(CellError::Num);
-                    }
-                    a.data.first().cloned().unwrap_or(Value::Empty)
-                }
+                Value::Array(a) => a.data.first().cloned().unwrap_or(Value::Empty),
                 v => v,
             });
         }
@@ -270,52 +209,6 @@ mod tests {
         assert_eq!(rows_of(&out), vec![vec![nv(-1.0)]; 1000]);
     }
 
-    /// Security: lifting a criteria aggregate rescans its range for every criterion, so criteria
-    /// x range cells past the budget is `#NUM!` before any scan runs.
-    #[test]
-    fn lifted_criteria_aggregates_stop_past_their_work_budget() {
-        use gridcraft_core::Array;
-        let tall = |n: usize| av(Array::filled(n, 1, nv(-1.0)).into());
-        is_err(ev("COUNTIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        is_err(ev("SUMIF", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        is_err(ev("COUNTIFS", vec![tall(1_000_000), tall(501)]), CellError::Num);
-        // Two ranges of 250,000 cells each count together.
-        is_err(ev("SUMIFS", vec![tall(250_000), tall(250_000), tall(1001)]), CellError::Num);
-        let counts = ev("COUNTIF", vec![av(col(&[1.0, 2.0, 2.0])), av(col(&[2.0, 1.0, 5.0]))]);
-        assert_eq!(rows_of(&counts), vec![vec![nv(2.0)], vec![nv(1.0)], vec![nv(0.0)]]);
-        for name in super::CRITERIA.iter().chain(super::PERIOD_LOOPS) {
-            assert!(crate::lookup(name).is_some(), "{name} isn't registered");
-        }
-    }
-
-    /// Security: CUMIPMT and CUMPRINC loop over their periods once per lifted element; the
-    /// periods of all elements are added up first, so an over-budget call runs none of them.
-    #[test]
-    fn lifted_period_loops_stop_past_their_work_budget() {
-        use gridcraft_core::Array;
-        let ends = |len: usize, end: f64| av(Array::filled(len, 1, nv(end)).into());
-        let args = |len: usize, end: f64| vec![n(0.01), n(1e7), n(1000.0), n(1.0), ends(len, end), n(0.0)];
-        // 51 elements of 1e7 periods each is past 5e8.
-        is_err(ev("CUMIPMT", args(51, 1e7)), CellError::Num);
-        is_err(ev("CUMPRINC", args(51, 1e7)), CellError::Num);
-        let out = ev("CUMIPMT", args(2, 12.0));
-        assert_eq!(rows_of(&out).len(), 2);
-        assert!(matches!(rows_of(&out).first().and_then(|r| r.first()), Some(Value::Number(x)) if *x < 0.0));
-    }
-
-    /// Security: an array-producing function lifted over a computed array builds each element's
-    /// whole result before keeping one cell; their cells count against the budget.
-    #[test]
-    fn lifted_array_results_count_against_the_budget() {
-        use gridcraft_core::Array;
-        let spec = crate::lookup("MUNIT").unwrap_or_else(|| panic!("MUNIT isn't registered"));
-        let dims = |n: usize| [av(Array::filled(n, 1, nv(10.0)).into())];
-        // Ten 10x10 identity matrices are 1,000 cells.
-        let out = super::call_lifted_within(spec, &dims(10), &mut TestCtx::default(), 1_010);
-        assert_eq!(rows_of(&out), vec![vec![nv(1.0)]; 10]);
-        is_err(super::call_lifted_within(spec, &dims(11), &mut TestCtx::default(), 1_010), CellError::Num);
-    }
-
     #[test]
     fn value_params_reject_multi_cell_references() {
         let s = FnSpec { value_args: &[true, false], ..spec() };

crates/functions/src/stat/descriptive.rs

@@ -50,12 +50,27 @@ pub(super) fn median(v: Vec<f64>) -> R<f64> {
 
 /// Values occurring at least twice, ordered by first occurrence, with their (equal, maximal) count.
 fn modes(v: &[f64]) -> Vec<f64> {
+    // Index of each distinct number in `counts`, so counting is linear rather than a search of
+    // every distinct number so far. Keyed by bits with -0 folded into 0 (they compare equal); NaN
+    // never equals anything, so it is never merged.
+    let mut index: std::collections::HashMap<u64, usize> = std::collections::HashMap::new();
     let mut counts: Vec<(f64, usize)> = Vec::new();
     for &x in v {
-        if let Some(e) = counts.iter_mut().find(|e| e.0 == x) {
-            e.1 += 1;
-        } else {
+        if x.is_nan() {
             counts.push((x, 1));
+            continue;
+        }
+        let key = if x == 0.0 { 0 } else { x.to_bits() };
+        match index.entry(key) {
+            std::collections::hash_map::Entry::Occupied(e) => {
+                if let Some(c) = counts.get_mut(*e.get()) {
+                    c.1 += 1;
+                }
+            }
+            std::collections::hash_map::Entry::Vacant(e) => {
+                e.insert(counts.len());
+                counts.push((x, 1));
+            }
         }
     }
     let best = counts.iter().map(|e| e.1).max().unwrap_or(0);
@@ -455,7 +470,10 @@ pub(super) fn frequency(a: &[Arg], _: C) -> R<Value> {
     order.sort_by(|&i, &j| bins.get(i).copied().unwrap_or(0.0).total_cmp(&bins.get(j).copied().unwrap_or(0.0)));
     let mut counts = vec![0.0; bins.len() + 1];
     for x in data {
-        let slot = order.iter().find(|&&i| x <= bins.get(i).copied().unwrap_or(f64::INFINITY)).copied().unwrap_or(bins.len());
+        // `order` sorts the bins ascending, so the bins `x` exceeds come first: binary search for
+        // the first bin at or above `x` (the first of equal bins, as a linear scan would find).
+        let pos = order.partition_point(|&i| bins.get(i).copied().unwrap_or(f64::INFINITY) < x);
+        let slot = order.get(pos).copied().unwrap_or(bins.len());
         if let Some(c) = counts.get_mut(slot) {
             *c += 1.0;
         }

crates/functions/src/stat/tests.rs

@@ -617,3 +617,20 @@ fn aggregate_helper() {
     close(aggregate_values_k(9, &vals, &nv(2.0)), 9.0);
     is_err(aggregate_values_k(14, &vals, &nv(10.0)), CellError::Num);
 }
+
+/// Security: FREQUENCY finds each value's bin by binary search, and MODE counts distinct numbers
+/// through an index, so neither is quadratic in its inputs. Results are as before: unsorted and
+/// duplicate bins keep their positions (a value goes to the first of equal bins), and tied modes
+/// come in first-occurrence order.
+#[test]
+fn frequency_and_mode_scale_with_their_inputs() {
+    let f = ev("FREQUENCY", vec![c(&[1.0, 2.0, 2.0, 3.0, 5.0, 9.0, -1.0]), c(&[3.0, 2.0, 2.0, 0.0])]);
+    assert_eq!(rows_of(&f), vec![vec![nv(1.0)], vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)], vec![nv(2.0)]]);
+    let data: Vec<f64> = (0..200_000).map(|i| f64::from(i) + 1e6).collect();
+    let bins: Vec<f64> = (0..200_000).map(f64::from).collect();
+    let f = ev("FREQUENCY", vec![c(&data), c(&bins)]);
+    assert_eq!(rows_of(&f).last(), Some(&vec![nv(200_000.0)]));
+    let distinct = ev("MODE", vec![c(&data)]);
+    is_err(distinct, CellError::NA);
+    assert_eq!(rows_of(&ev("MODE.MULT", vec![c(&[3.0, 0.0, 1.0, -0.0, 3.0, 1.0])])), vec![vec![nv(3.0)], vec![nv(0.0)], vec![nv(1.0)]]);
+}