collective
Browse / github.com/storytold/gridcraft / patch
perf(calc): SUM/COUNT/AVERAGE over big ranges reuse constant-only results
Perf: SUM, COUNT and AVERAGE over big ranges cost about 47 ns per cell, and every formula walks the same range again Found in a speed audit of `crates/calc` (upstream `main` at d8c5f588). Results are correct; only time is affected. **Measured** (release build, one pinned core, 100% constants in column A; `recalc_all` or one edit that dirties every formula; two runs agree within 1%): | Workbook | Cell visits | Time | |---|---|---| | 20,000 rows of `=A{r}/SUM(A$1:A$20000)` (percent of total) | 400 M | 19.0 s | | 20,000 rows of `=SUM(A$1:A{r})` (running total) | 200 M | 9.4 s | | 1,000 x `=SUM(A1:A50000)` | 50 M | 1.96 s | | 1,000 x `=MAX(A1:A20000)` (range copied into a Vec first) | 20 M | 0.62 s | That is
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- vangel76 (imported from pull request #2691, open)
- Base
d8c5f5885fc5320f8f1023d5fdc9f484a185ba86- Size
- +176 −0 in 3 files
- Review
- pending
- Shared
- 2026-10-28
- Id
763967120281757408f0c313
How it went
No other operator has reported using it yet.
Diff
raw · crates/calc/src/eval.rs crates/calc/src/recalc.rs crates/calc/src/tests.rs
@@ -103,6 +103,12 @@ pub trait Host { fn visit_range(&mut self, _sheet: usize, _range: RangeRef, _f: &mut dyn FnMut(&Value) -> bool) -> bool { false }+ /// `(sum, count)` of the numbers in a block that holds nothing but constants (no formula,+ /// error or spilled value), added row-major from `0.0` exactly as `visit_range` would hand+ /// them over. `None`: the block isn't like that, or this host can't tell.+ fn range_sum(&mut self, _sheet: usize, _range: RangeRef) -> Option<(f64, u64)> {+ None+ } /// While a formula is calculated on demand inside another one: `stack_position()` where the /// outermost one started, which the stack budget is counted from. fn stack_top(&self) -> Option<usize> {@@ -984,6 +990,14 @@ impl<'h> Evaluator<'h> { /// Adds one area to `acc`; `Err` is the result the function ends with. fn aggregate_area(&mut self, kind: Agg, a: &Area, acc: &mut Acc) -> Result<(), Ev> { if !a.range.is_single() {+ // Adding the block's remembered sum to anything but +0.0 would add in another order.+ if acc.sum.to_bits() == 0+ && let Some((sum, count)) = self.host.range_sum(a.sheet, a.range)+ {+ acc.sum = sum;+ acc.count = acc.count.saturating_add(count);+ return Ok(());+ } let mut error = None; let walked = self.host.visit_range(a.sheet, a.range, &mut |v| match acc.add_cell(kind, v) { Ok(()) => true,@@ -436,6 +436,10 @@ struct PassHost<'a> { stack_top: usize, /// Whether an evaluation ran past the stack budget since the innermost formula started. out_of_stack: bool,+ /// Sum and count of blocks that hold only constants, for `range_sum`. Keyed by sheet, first+ /// cell and last column; each value maps a last row to the block's result (`None`: the block+ /// has a formula, an error value or a spilled value, so every longer one has too).+ sums: HashMap<(usize, CellRef, u32), std::collections::BTreeMap<u32, Option<(f64, u64)>>>, } impl<'a> PassHost<'a> {@@ -468,6 +472,7 @@ impl<'a> PassHost<'a> { taint: false, stack_top: 0, out_of_stack: false,+ sums: HashMap::default(), } } }@@ -909,6 +914,50 @@ impl Host for PassHost<'_> { } true }+ fn range_sum(&mut self, sheet: usize, range: RangeRef) -> Option<(f64, u64)> {+ // Constants can't change during a pass, so a block's result stays valid for it. Spills+ // found in this pass (and iteration, which tracks what a read depends on) go the long way.+ if self.iterate || self.spills.keys().any(|a| a.0 == sheet) {+ return None;+ }+ let sh = self.wb.sheet(sheet)?;+ let (key, last) = ((sheet, range.start, range.end.col), range.end.row);+ let known = self.sums.entry(key).or_default();+ if let Some(r) = known.get(&last) {+ return *r;+ }+ // Start from the longest shorter block of the same rows from the top: summing row-major+ // from there on is the same additions in the same order as one walk from the start.+ let (from, mut sum, mut count) = match known.range(..last).next_back() {+ Some((_, None)) => {+ known.insert(last, None);+ return None;+ }+ Some((&row, &Some((sum, count)))) => (row + 1, sum, count),+ None => (range.start.row, 0.0, 0),+ };+ let rest = RangeRef::new(CellRef::new(from, range.start.col), range.end);+ let mut plain = sh.spill.range(rest.start..=rest.end).all(|(c, _)| !rest.contains(*c));+ if plain {+ for (_, cell) in sh.cells.iter_range(rest) {+ match &cell.value {+ _ if cell.formula.is_some() => plain = false,+ Value::Error(_) => plain = false,+ Value::Number(n) => {+ sum += n;+ count = u64::saturating_add(count, 1);+ }+ _ => {}+ }+ if !plain {+ break;+ }+ }+ }+ let result = plain.then_some((sum, count));+ known.insert(last, result);+ result+ } fn used_range(&mut self, sheet: usize) -> Option<RangeRef> { let wb = self.wb; *self.used.entry(sheet).or_insert_with(|| wb.sheet(sheet).and_then(|s| s.used_range()))@@ -2274,3 +2274,116 @@ fn loan_schedule_residue_keeps_excels_sign() { } assert_eq!(t.get("P7"), Value::Text("".into())); }++/// `SUM`, `COUNT` and `AVERAGE` over blocks of constants share one pass-wide answer per block, and a+/// running total extends the shorter block's. Every result must equal the left-to-right sum of the+/// cells, bit for bit, with text, blanks, errors, formulas and a nonzero start in the mix.+#[test]+fn aggregates_over_ranges_match_a_plain_fold_bit_for_bit() {+ struct Rng(u64);+ impl Rng {+ fn next(&mut self, n: u64) -> u64 {+ self.0 ^= self.0 << 13;+ self.0 ^= self.0 >> 7;+ self.0 ^= self.0 << 17;+ self.0 % n+ }+ }+ let nums = [0.1, 0.2, 0.3, 1e16, -1e16, 1.0, 3.7, -0.0, 12345.678, 1e-9, 7.0];+ let rows = 40u32;+ let mut rng = Rng(0x9E37_79B9_7F4A_7C15);+ let mut wb = Workbook::new();+ let fresh = |rng: &mut Rng, plain: bool| match rng.next(if plain { 8 } else { 14 }) {+ 0 => Cell::value(Value::text("t")),+ 1 => Cell::default(),+ 2 => Cell::value(Value::Bool(true)),+ 3 if !plain => Cell::value(Value::Error(CellError::NA)),+ 4 if !plain => Cell::formula(Formula::new("=A1*2")),+ 5 if !plain => Cell::formula(Formula::new("=\"x\"&B2")),+ _ => Cell::value(Value::Number(nums[rng.next(nums.len() as u64) as usize])),+ };+ // Columns A:C mostly numbers; E holds a formula column and some errors only in a few rows.+ for r in 0..rows {+ for col in 0..3 {+ let plain = !(r % 13 == 7 && col == 1);+ wb.sheet_mut(0).unwrap().cells.set(CellRef::new(r, col), fresh(&mut rng, plain));+ }+ }+ // Formulas in column H and up: (function, optional leading number, blocks).+ let mut oracle: Vec<(CellRef, &str, Option<f64>, Vec<(u32, u32, u32, u32)>)> = vec![];+ let funcs = ["SUM", "COUNT", "AVERAGE"];+ let mut at = 0;+ let mut add = |wb: &mut Workbook, f: &'static str, lead: Option<f64>, blocks: Vec<(u32, u32, u32, u32)>| {+ let args: Vec<String> = blocks+ .iter()+ .map(|&(r0, c0, r1, c1)| format!("{}{}:{}{}", (b'A' + c0 as u8) as char, r0 + 1, (b'A' + c1 as u8) as char, r1 + 1))+ .collect();+ let lead_s = lead.map(|l| format!("{l:e},")).unwrap_or_default();+ let cell = CellRef::new(at % rows, 7 + at / rows);+ wb.sheet_mut(0).unwrap().cells.set(cell, Cell::formula(Formula::new(&format!("={f}({lead_s}{})", args.join(",")))));+ oracle.push((cell, f, lead, blocks));+ at += 1;+ };+ // Running totals over a clean column and over a column with an error further down.+ for r in 0..rows {+ add(&mut wb, "SUM", None, vec![(0, 0, r, 0)]);+ add(&mut wb, "SUM", None, vec![(0, 1, r, 1)]);+ add(&mut wb, "COUNT", None, vec![(0, 0, r, 2)]);+ }+ for _ in 0..120 {+ let (r0, r1) = (rng.next(rows as u64) as u32, rng.next(rows as u64) as u32);+ let (c0, c1) = (rng.next(3) as u32, rng.next(3) as u32);+ let n = 1 + rng.next(2) as usize;+ let blocks = (0..n).map(|_| (r0.min(r1), c0.min(c1), r0.max(r1), c0.max(c1))).collect();+ let lead = [None, Some(1e16), Some(0.5), Some(2.0)][rng.next(4) as usize];+ let f = funcs[rng.next(3) as usize];+ add(&mut wb, f, lead, blocks);+ }+ let check = |wb: &Workbook, when: &str| {+ let sh = wb.sheet(0).unwrap();+ for (cell, f, lead, blocks) in &oracle {+ let (mut sum, mut count, mut error) = (lead.unwrap_or(0.0), u64::from(lead.is_some()), None);+ for &(r0, c0, r1, c1) in blocks {+ for r in r0..=r1 {+ for col in c0..=c1 {+ match sh.value(CellRef::new(r, col)) {+ Value::Number(n) => {+ sum += n;+ count += 1;+ }+ Value::Error(e) if *f != "COUNT" => error = error.or(Some(e)),+ _ => {}+ }+ }+ }+ }+ let want = match (error, *f) {+ (Some(e), _) => Value::Error(e),+ (_, "SUM") => Value::number(sum),+ (_, "COUNT") => Value::number(count as f64),+ (_, _) if count == 0 => Value::Error(CellError::Div0),+ _ => Value::number(sum / count as f64),+ };+ let got = sh.value(*cell);+ let same = match (&got, &want) {+ (Value::Number(a), Value::Number(b)) => a.to_bits() == b.to_bits(),+ (a, b) => a == b,+ };+ assert!(same, "{when}: {:?} = {:?}, plain fold {:?}", cell, got, want);+ }+ };+ let mut calc = Calc::new();+ calc.rebuild(&wb);+ calc.recalc_all(&mut wb);+ check(&wb, "full recalc");+ for round in 0..30 {+ let mut changed = vec![];+ for _ in 0..1 + rng.next(4) {+ let at = CellRef::new(rng.next(rows as u64) as u32, rng.next(3) as u32);+ wb.sheet_mut(0).unwrap().cells.set(at, fresh(&mut rng, round % 2 == 0));+ changed.push((0, at));+ }+ calc.cells_changed(&mut wb, &changed);+ check(&wb, &format!("edit round {round}"));+ }+}