collective
Browse / github.com/storytold/gridcraft / patch
perf(calc): find formulas a cleared cell may unblock from a set of #SPILL! cells
Perf: clearing one cell scans every formula in the workbook, and each changed cell scans a 64x64 window Found in a speed audit of `crates/calc` (upstream `main` at d8c5f588). Results are correct; only time is affected. **Cause.** In `Calc::cells_changed` (`recalc.rs`), when a changed cell is now empty, the "an emptied cell can unblock an anchor" step walks every key of `graph.nodes` and looks up each one's cached value (`sh.value(c) == #SPILL!`). The same loop runs in `run` for every area a formula stopped spilling over. In addition each changed cell scans a 64 x 64 window of stored cells for `#SPILL!` values, one tree descent per row. **Measured** (release build, one pinned core): 100,000 for
- Status
- open
- Score
- 0.00
- Adopters
- 0 other operators
- Author
- vangel76 (imported from pull request #2696, open)
- Base
89ac453efa7ea03a3ab0b0d24fd85ca51172f5cc- Size
- +167 −24 in 2 files
- Review
- pending
- Shared
- 2026-10-28
- Id
a41e9c84e792cfa7cc7a06a8
How it went
No other operator has reported using it yet.
Diff
raw · crates/calc/src/recalc.rs crates/calc/src/tests.rs
@@ -10,7 +10,7 @@ //! and the formulas that read one are evaluated again until the loop settles //! (`PassHost::iterate_loops`). -use std::collections::{BTreeSet, VecDeque};+use std::collections::{BTreeMap, BTreeSet, VecDeque}; use std::hash::{BuildHasherDefault, Hasher}; use gridcraft_core::{Array, CellError, CellRef, RangeRef, Value};@@ -38,11 +38,61 @@ pub struct Calc { /// Cells whose formulas have errors from cycles. pub circular: Vec<Key>, pub last_recalc_cells: usize,+ /// The cells whose value is `#SPILL!`, kept so that finding the formulas an emptied cell or a+ /// freed spill area may unblock doesn't walk every formula or window of cells. Filled in+ /// `rebuild`, kept up to date by `cells_changed` and by the write-back of a run; an entry is+ /// always checked against the workbook before it is used.+ spill_errors: SpillErrors,+}++/// A set of cells by row, each row's columns in their own set: a window of rows and columns is+/// found by one column range per row that has an entry, so the cost follows the cells in the+/// window, not those to the side of it in the same rows.+#[derive(Clone, Debug, Default)]+struct SpillErrors {+ rows: BTreeMap<(usize, u32), BTreeSet<u32>>,+}++impl SpillErrors {+ fn is_empty(&self) -> bool {+ self.rows.is_empty()+ }++ fn clear(&mut self) {+ self.rows.clear();+ }++ fn insert(&mut self, (sheet, c): Key) {+ self.rows.entry((sheet, c.row)).or_default().insert(c.col);+ }++ fn remove(&mut self, (sheet, c): &Key) {+ if let Some(cols) = self.rows.get_mut(&(*sheet, c.row)) {+ cols.remove(&c.col);+ if cols.is_empty() {+ self.rows.remove(&(*sheet, c.row));+ }+ }+ }++ /// The cells of `sheet` in `rows` x `cols` (both inclusive), in row-major order.+ fn range(&self, sheet: usize, rows: (u32, u32), cols: (u32, u32)) -> impl Iterator<Item = CellRef> + '_ {+ self.rows+ .range((sheet, rows.0)..=(sheet, rows.1))+ .flat_map(move |(&(_, row), set)| set.range(cols.0..=cols.1).map(move |&col| CellRef::new(row, col)))+ } } impl Default for Calc { fn default() -> Self {- Calc { graph: Graph::default(), rng: 0x9E37_79B9_7F4A_7C15, fixed_now: None, circular: vec![], last_recalc_cells: 0 }+ Calc {+ graph: Graph::default(),+ rng: 0x9E37_79B9_7F4A_7C15,+ fixed_now: None,+ circular: vec![],+ last_recalc_cells: 0,+ spill_errors: SpillErrors::default(),+ } } } @@ -126,8 +176,12 @@ impl Calc { pub fn rebuild(&mut self, wb: &Workbook) { self.graph = Graph::default(); let mut circ = Vec::new();+ self.spill_errors.clear(); for (si, sheet) in wb.sheets.iter().enumerate() { for (c, cell) in sheet.cells.iter() {+ if cell.value == Value::Error(CellError::Spill) {+ self.spill_errors.insert((si, c));+ } if let Some(f) = &cell.formula && let Some(e) = f.expr() {@@ -185,6 +239,20 @@ impl Calc { out } + /// The cells of `sheet` in `rows` x `cols` (inclusive, `cols` a lower and an upper column) that+ /// show `#SPILL!`, in row-major order.+ fn spill_errors_in(&self, wb: &Workbook, sheet: usize, rows: (u32, u32), cols: (u32, u32)) -> Vec<CellRef> {+ let Some(sh) = wb.sheet(sheet) else { return Vec::new() };+ self.spill_errors.range(sheet, rows, cols).filter(|c| sh.cells.get(*c).is_some_and(|x| x.value == Value::Error(CellError::Spill))).collect()+ }++ /// The formulas showing `#SPILL!` on `sheet` at or above and to the left of `end`: what a+ /// cell emptied or a spill area freed there may unblock.+ fn unblock_candidates(&self, wb: &Workbook, sheet: usize, end: CellRef) -> Vec<Key> {+ let cells = self.spill_errors_in(wb, sheet, (0, end.row), (0, end.col));+ cells.into_iter().filter(|c| self.graph.nodes.contains_key(&(sheet, *c))).map(|c| (sheet, c)).collect()+ }+ /// Recalculates every formula (F9 / Ctrl+Alt+F9, and after loading). pub fn recalc_all(&mut self, wb: &mut Workbook) { self.rebuild(wb);@@ -206,6 +274,11 @@ impl Calc { pub fn cells_changed(&mut self, wb: &mut Workbook, changed: &[Key]) { let mut cleared: Vec<(usize, RangeRef)> = Vec::new(); for &k in changed {+ if wb.sheet(k.0).and_then(|s| s.cell(k.1)).is_some_and(|c| c.value == Value::Error(CellError::Spill)) {+ self.spill_errors.insert(k);+ } else {+ self.spill_errors.remove(&k);+ } let formula = wb.sheet(k.0).and_then(|s| s.cell(k.1)).and_then(|c| c.formula.clone()); match formula.and_then(|f| f.expr()) { Some(e) => {@@ -228,6 +301,7 @@ impl Calc { && cell.formula.is_some() { cell.value = Value::Error(CellError::Name);+ self.spill_errors.remove(&k); } } }@@ -250,10 +324,9 @@ impl Calc { seeds.push((k.0, *anchor)); } }- for (c, cell) in sh.cells.iter_range(RangeRef::new(CellRef::new(k.1.row.saturating_sub(64), k.1.col.saturating_sub(64)), k.1)) {- if c != k.1 && cell.value == Value::Error(CellError::Spill) {- seeds.push((k.0, c));- }+ if !self.spill_errors.is_empty() {+ let (r0, c0) = (k.1.row.saturating_sub(64), k.1.col.saturating_sub(64));+ seeds.extend(self.spill_errors_in(wb, k.0, (r0, k.1.row), (c0, k.1.col)).into_iter().filter(|c| *c != k.1).map(|c| (k.0, c))); } if !sh.cells.has(k.1) { match emptied.iter_mut().find(|x| x.0 == k.0) {@@ -265,11 +338,7 @@ impl Calc { } // An emptied cell can unblock an anchor any distance above or to the left of it. for (si, end) in emptied {- for &(s, c) in self.graph.nodes.keys() {- if s == si && c.row <= end.row && c.col <= end.col && wb.sheet(s).is_some_and(|sh| sh.value(c) == Value::Error(CellError::Spill)) {- seeds.push((s, c));- }- }+ seeds.extend(self.unblock_candidates(wb, si, end)); } // Spill areas of changed anchors also change. for &k in changed {@@ -373,10 +442,15 @@ impl Calc { let mut freed: Vec<(usize, RangeRef)> = Vec::new(); for (k, v) in results { let Some(sheet) = wb.sheet_mut(k.0) else { continue };- if let Some(cell) = sheet.cells.get_mut(k.1)- && cell.value != v- {- cell.value = v;+ if let Some(cell) = sheet.cells.get_mut(k.1) {+ if v == Value::Error(CellError::Spill) {+ self.spill_errors.insert(k);+ } else {+ self.spill_errors.remove(&k);+ }+ if cell.value != v {+ cell.value = v;+ } } } for k in &dirty {@@ -412,6 +486,7 @@ impl Calc { if blocked { if let Some(cell) = sheet.cells.get_mut(k.1) { cell.value = Value::Error(CellError::Spill);+ self.spill_errors.insert(*k); } // Not blocked while the pass ran (it would have been #SPILL! there), so // blocked by another array of this pass: the formulas that read this one,@@ -457,15 +532,7 @@ impl Calc { } // An area a formula no longer spills over may unblock another formula's array. for (si, o) in freed {- for &(s, c) in self.graph.nodes.keys() {- if s == si- && c.row <= o.end.row- && c.col <= o.end.col- && wb.sheet(s).is_some_and(|sh| sh.value(c) == Value::Error(CellError::Spill))- {- spill_changes.push((s, c));- }- }+ spill_changes.extend(self.unblock_candidates(wb, si, o.end)); } if full { // Everything was already evaluated once; spill dependents need another pass.@@ -2274,3 +2274,79 @@ fn loan_schedule_residue_keeps_excels_sign() { } assert_eq!(t.get("P7"), Value::Text("".into())); }++#[test]+fn clearing_a_cell_unblocks_the_arrays_above_and_left_of_it() {+ let mut t = T::new();+ for r in 1..=50 {+ t.set(&format!("D{r}"), &format!("={r}*2"));+ }+ t.set("B2", "7");+ t.set("B1", "=SEQUENCE(3)");+ t.set("C1", "=SEQUENCE(1,3)");+ t.set("A20", "=B1+1");+ assert_eq!(t.get("B1"), Value::Error(CellError::Spill));+ assert_eq!(t.get("A20"), Value::Error(CellError::Spill));+ // Emptied: the array above it spills.+ t.wb.sheet_mut(0).unwrap().cells.remove(c("B2"));+ t.calc.cells_changed(&mut t.wb, &[(0, c("B2"))]);+ assert_eq!(t.num("B3"), 3.0);+ assert_eq!(t.num("A20"), 2.0);+ // Typing over the area blocks it again; far from it, nothing is disturbed.+ t.set("B3", "9");+ assert_eq!(t.get("B1"), Value::Error(CellError::Spill));+ t.set("D50", "1");+ assert_eq!(t.get("B1"), Value::Error(CellError::Spill));+ assert_eq!(t.num("D49"), 98.0);+ // Clearing it again frees the array.+ t.set("B3", "");+ assert_eq!(t.num("B3"), 3.0);+}++/// A sheet with `#SPILL!` cells in rows 0..64, columns 100..16384 (as blocked arrays leave), none+/// near column A.+fn spill_error_field() -> T {+ let mut t = T::new();+ let sh = t.wb.sheet_mut(0).unwrap();+ for r in 0..64 {+ for col in 100..16_384 {+ sh.cells.set(CellRef::new(r, col), Cell::value(Value::Error(CellError::Spill)));+ }+ }+ t.calc.recalc_all(&mut t.wb);+ t+}++#[test]+fn an_edit_far_left_of_many_spill_errors_does_not_disturb_them() {+ let mut t = spill_error_field();+ t.set("A65", "5");+ assert_eq!(t.num("A65"), 5.0);+ assert_eq!(t.get("CW1"), Value::Error(CellError::Spill));+ assert_eq!(t.get("XFD64"), Value::Error(CellError::Spill));+ // A blocked formula inside the window is still found when a cell to its right is cleared.+ t.set("DA66", "7");+ t.set("CZ66", "=SEQUENCE(1,3)");+ assert_eq!(t.get("CZ66"), Value::Error(CellError::Spill));+ t.wb.sheet_mut(0).unwrap().cells.remove(c("DA66"));+ t.calc.cells_changed(&mut t.wb, &[(0, c("DA66"))]);+ assert_eq!(t.num("DA66"), 2.0);+}++/// Probe: single-cell edits in column A below a block of `#SPILL!` cells to its right.+/// `cargo test -p gridcraft-calc --release -- --ignored --nocapture spill_error_field_probe`+#[test]+#[ignore]+#[allow(clippy::disallowed_methods)]+fn spill_error_field_probe() {+ let mut t = spill_error_field();+ let mut best = std::time::Duration::MAX;+ for i in 0..9 {+ let start = std::time::Instant::now();+ for _ in 0..100 {+ t.set("A65", &format!("{i}"));+ }+ best = best.min(start.elapsed());+ }+ eprintln!("100 edits of A65 beside 1,040,000 spill errors: best of 9 = {best:?}");+}