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/engine/src/cmd.rs

@@ -440,14 +440,8 @@ pub(crate) fn commit<R>(d: &mut DocState, f: impl FnOnce(&mut Ctx) -> Result<R>)
     }
     fit_rows.sort_unstable();
     fit_rows.dedup();
-    let mut sweep: Option<(usize, MergeSweep)> = None;
     for (si, row) in fit_rows {
-        if sweep.as_ref().is_none_or(|(at, _)| *at != si) {
-            sweep = wb.sheet(si).map(|sh| (si, MergeSweep::new(sh)));
-        }
-        if let Some((_, sw)) = sweep.as_mut() {
-            fit_row_height(&mut wb, si, row, sw);
-        }
+        auto_row_height(&mut wb, si, row);
     }
     if let Some(t0) = t0 {
         eprintln!("commit: + rows {:?}", since(t0));
@@ -602,65 +596,6 @@ fn wrapped_line_count(line: &str, width: f32, size: f32, bold: bool) -> f32 {
 /// Line breaks in a cell's text count only when the cell wraps, as in Excel: with Wrap Text off
 /// a multi-line value shows on one line and AutoFit gives a one-line row.
 pub fn auto_row_height(wb: &mut Workbook, si: usize, row: u32) {
-    let Some(sh) = wb.sheet(si) else { return };
-    let mut sweep = MergeSweep::new(sh);
-    fit_row_height(wb, si, row, &mut sweep);
-}
-
-/// Most merge comparisons one auto-fit pass (a commit, or opening a workbook) makes. Past it the
-/// remaining rows keep the heights they have rather than stall on a sheet whose merges overlap
-/// the fitted rows many times over.
-const MERGE_FIT_WORK: usize = 50_000_000;
-
-/// The merged areas of one sheet that touch a row, for rows visited in ascending order: the
-/// merges are sorted by first row once and swept, so fitting many rows never rescans every merge
-/// per row. All comparisons count against [`MERGE_FIT_WORK`].
-pub(crate) struct MergeSweep {
-    by_start: Vec<gridcraft_core::RangeRef>,
-    next: usize,
-    active: Vec<gridcraft_core::RangeRef>,
-    budget: usize,
-}
-
-impl MergeSweep {
-    pub(crate) fn new(sh: &gridcraft_model::Sheet) -> Self {
-        let mut by_start: Vec<gridcraft_core::RangeRef> = sh.merges.iter().copied().filter(|m| !m.is_single()).collect();
-        by_start.sort_unstable_by_key(|m| m.start.row);
-        let budget = MERGE_FIT_WORK.saturating_sub(by_start.len());
-        Self { by_start, next: 0, active: Vec::new(), budget }
-    }
-
-    /// Takes `n` comparisons from the budget; `false` once it is spent.
-    fn charge(&mut self, n: usize) -> bool {
-        match self.budget.checked_sub(n) {
-            Some(rest) => {
-                self.budget = rest;
-                true
-            }
-            None => {
-                self.budget = 0;
-                false
-            }
-        }
-    }
-
-    /// The merges covering `row`, or `None` when the budget is spent. Rows must not decrease
-    /// between calls (skipping rows is fine).
-    fn at(&mut self, row: u32) -> Option<Vec<gridcraft_core::RangeRef>> {
-        while let Some(m) = self.by_start.get(self.next).filter(|m| m.start.row <= row) {
-            self.active.push(*m);
-            self.next += 1;
-        }
-        if !self.charge(self.active.len()) {
-            return None;
-        }
-        self.active.retain(|m| m.end.row >= row);
-        Some(self.active.clone())
-    }
-}
-
-/// [`auto_row_height`] with the sheet's merges taken from `sweep`.
-pub(crate) fn fit_row_height(wb: &mut Workbook, si: usize, row: u32, sweep: &mut MergeSweep) {
     let Some(sh) = wb.sheet(si) else { return };
     if sh.rows.get(&row).is_some_and(|i| i.custom) {
         return;
@@ -690,14 +625,9 @@ pub(crate) fn fit_row_height(wb: &mut Workbook, si: usize, row: u32, sweep: &mut
     // picked out once, and per cell the candidates are re-checked (normally none or a couple;
     // a sheet with many merges and many saved columns would otherwise scan all of them per
     // cell, rows × merges × columns).
-    // Rows are fitted in ascending order, so the merges touching this one come from a sweep over
-    // the sheet's merges sorted once, not from a scan of all of them. Out of budget: the row keeps
-    // the height it has.
-    let Some(row_merges) = sweep.at(row) else { return };
+    let row_merges: Vec<gridcraft_core::RangeRef> =
+        sh.merges.iter().copied().filter(|m| !m.is_single() && m.start.row <= row && row <= m.end.row).collect();
     for (c, cell) in sh.cells.row(row, 0, gridcraft_core::MAX_COLS - 1) {
-        if !sweep.charge(row_merges.len()) {
-            return;
-        }
         // Merged cells never auto-fit their rows, like Excel (column autofit skips them too).
         if row_merges.iter().any(|m| m.contains(CellRef::new(row, c))) {
             continue;

crates/engine/src/io.rs

@@ -93,11 +93,9 @@ fn fit_imported_rows(wb: &mut Workbook) {
         let mut rows: Vec<u32> = sh.cells.iter().map(|(c, _)| c.row).collect();
         rows.sort_unstable();
         rows.dedup();
-        // One sweep over the sheet's merges for all of its rows, in ascending order.
-        let mut sweep = crate::cmd::MergeSweep::new(sh);
         for row in rows {
             let before = wb.sheet(si).and_then(|sh| sh.rows.get(&row)).and_then(|i| i.size);
-            crate::cmd::fit_row_height(wb, si, row, &mut sweep);
+            crate::cmd::auto_row_height(wb, si, row);
             let Some(before) = before else { continue };
             let after = wb.sheet(si).and_then(|sh| sh.rows.get(&row)).and_then(|i| i.size);
             if after.is_none_or(|a| before > a + 0.5)

crates/engine/tests/it/row_autofit.rs

@@ -59,31 +59,3 @@ fn whole_row_format_keeps_hidden_rows_hidden() {
     assert!(info.size.unwrap_or(before) > before + 10.0, "hidden row still grows to its font: before={before}, size={:?}", info.size);
     assert!(info.hidden, "formatting a hidden row must not unhide it");
 }
-
-#[test]
-fn many_merges_fit_rows_the_same_and_skip_merged_cells() {
-    // Rows are fitted with one sweep over the sheet's merges; a merged cell still never grows
-    // its row, and rows next to thousands of merges still fit.
-    let mut s = gridcraft_engine::Session::new();
-    s.new_workbook();
-    let values: Vec<_> = (0..2_000).map(|i| json!([format!("v{i}")])).collect();
-    s.execute("range.setValues", json!({"range": "A1", "values": values})).unwrap();
-    {
-        let sh = sheet_mut(&mut s);
-        sh.merges.push(gridcraft_engine::core::RangeRef::parse("A3:B4").unwrap());
-        for i in 0..20_000u32 {
-            let row = 4 + i % 1_990;
-            sh.merges.push(gridcraft_engine::core::RangeRef::new(
-                gridcraft_engine::core::CellRef::new(row, 3 + (i % 7) * 2),
-                gridcraft_engine::core::CellRef::new(row + 3, 4 + (i % 7) * 2),
-            ));
-        }
-    }
-    s.execute("home.fontSize", json!({"range": "A:A", "size": 20})).unwrap();
-    let sh = s.doc().unwrap().wb.active().unwrap();
-    let default = sh.default_row_height;
-    assert!(sh.row_height(0) > 30.0 && sh.row_height(1_999) > 30.0, "rows with big text grow");
-    assert_eq!(sh.row_height(2), default, "a merged cell does not grow its row");
-    assert_eq!(sh.row_height(3), default, "nor any row of the merge");
-    assert!(sh.row_height(4) > 30.0 && sh.row_height(1_000) > 30.0, "rows beside other merges grow");
-}

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)]]);
+}