nigig-org/PLAN_PERF_OPTIMIZATION.md

Plan: Performance optimization of the doc + spreadsheet engines

Measurement-driven, phased performance work on the two core engines (spreadsheet-engine, doc-engine) and the UI paths that sit on top of them, applying the techniques in the Algorithmica "High-Performance Computing" book (https://en.algorithmica.org/hpc/): profiling first, then CPU basics, branchless code, memory hierarchy and data layout, hashing and search for small-N dispatch, SIMD, strings and CRDT hot paths, I/O, and only then parallelism.

This plan follows the existing benchmark culture in this repo (BENCH_BASELINE.md): benches are measurements, not assertions; they run in --release; wall-clock numbers are compared by hand against a baseline file, never asserted in CI.

Every phase has a Source (the Algorithmica chapter that motivates it), Targets (concrete file-level hotspots), Actions, and a Gate (the measured bar that must be hit before the next phase starts). Phases are ordered so the cheap, safe wins land before the risky structural work, and the CRDT invariants (deterministic op order) are protected by the existing RNG property tests through every phase.

Baseline to reproduce before starting

Benchmark	Crate	Measures
bench_formula_parse_eval_chain	spreadsheet-engine	parse + evaluate a 1000-cell SUM/IF chain
bench_grid_random_access_10k	spreadsheet-engine	10k random get_cell_value lookups
bench_range_agg_sum_10k	spreadsheet-engine	SUM over a 10k-cell dense range
bench_crdt_materialize_2k	doc-engine	materialize() on a 2k-char doc
bench_crdt_insert_char_1k	doc-engine	insert char into a 1k-char block
bench_crdt_save_wire	doc-ui	full crdt_save_wire + save_doc_state
bench_projection_layout_50	doc-ui	layout_projection for 50 blocks
bench_import_500k	both	500KB .docx / .xlsx import
bench_dashboard_list_saved	both UI	list_saved_docs / list_spreadsheet_files

Record these into BENCH_BASELINE.md before any code change. Treat the debug profile as non-comparable (3-5x slower, shifts ratios).

Phase 0 — Measurement infrastructure

• Goal: ground truth before touching anything; repeatable before/after table per phase.
• Source: HPC "Analyzing performance".
• Actions:
  • Add a benches/ crate (or #[bench]-backed, #[ignore]-d test harness like the CAD profile_benchmarks.rs) under each engine with the benchmarks above. Criterion or divan, release-only.
  • Add a headless perf record --call-graph dwarf / samply runbook for the two engines (no makepad dependency) plus targeted profile captures for the UI loops (render_cache, import).
  • Extend BENCH_BASELINE.md with the resulting numbers.
• Gate: every benchmark above has a recorded number that CI can reproduce on a clean checkout.

Phase 1 — Compiler & codegen hygiene

• Goal: biggest free win, zero behavioral risk.
• Source: HPC "Compiler" (separate compilation, inlining, constant folding) and "PGO".
• Targets: release profile in Cargo.toml, formula2.rs eval loop.
• Actions:
  • Release: lto = true, codegen-units = 1 (tune 4/8/16), a native runtime feature with a portable fallback, debug = false for deps. A/B on Phase 0 benches; confirm makepad/render crates behave.
  • Add a repeatable PGO (profile-guided optimization) script driving formula eval + CRDT materialize + import; measure, keep the script.
  • Replace the &dyn EvalContext dynamic dispatch in the hot evaluate path (formula2.rs:1125) with an enum or generic context; do the same for any Box<dyn> walkers in crdt/document.rs.
  • #[inline(always)] only the proven hot leafs (get_cell_value, CellId hashing, op lookup); review hot clone() sites (materialize_block_text, doc_import::plain_text_paragraphs).
• Gate: 5-20% on formula/projection benches; all tests green; identical behavior.

Phase 2 — Memory hierarchy & data layout

• Goal: cache locality, data-oriented design, smaller types. The single biggest structural target in the spreadsheet path.
• Source: HPC "Memory" (cache, data-oriented design, small & fast types).
• Targets: spreadsheet-engine/src/data.rs cell storage; dep tracking; doc CRDT materialize.
• Actions:
  • Grid storage: replace the HashMap<CellId, CellData> hot sheet path with a dense packed grid for the populated bounding box (rows as Vec<Option<CellData>>, SoA numbers/strings), plus a sparse overflow map for far cells. Applies to range eval, spill values (data.rs:1665), autofill, and rendering.
  • Iterate rows-major (linear, prefetchable) instead of HashMap keys for SUM/COUNTIF/render passes.
  • Narrow types: row_heights/col_widths HashMap<u32,f32> → Vec<f32> indexed within bounds; consider packing CellId down if still u64 after the dense grid lands.
  • Deps (data.rs:1721-1722): HashMap<CellId, HashSet<CellId>> → small SmallVec adjacency (most cells have <4 deps; reads beat HashSet).
  • Doc engine: materialize() clones text per block and builds Vec<String> per char (crdt/document.rs:252) — compact to Vec<char>/string chunks via an arena; avoid per-OpId String actor ids in hot walks.
• Gate: perf cache-miss count on formula/import drops 30%+; range-eval bench >=1.5x.

Phase 3 — Branchless code & ILP

• Goal: straight-line happy paths, fewer mispredictions.
• Source: HPC "CPU" (pipelining, branchless selection).
• Targets: formula2.rs cycle detection, cell lookup, aggregate loops, autofill.rs.
• Actions:
  • Replace RefCell<HashSet<(u32,u32)>> cycle probing (data.rs:1275) with a depth budget so the common no-cycle path is a straight scan, no hash lookups.
  • Cell lookup → index arithmetic (base + row*stride + col) instead of hashing; indexed check instead of map.get.
  • Manual unroll x4-8 in SUM/AVERAGE/MIN/MAX/SUMPRODUCT and autofill; keep state in locals (no RefCell/dyn in inner loops); no format! in eval-path error/budget branches.
• Gate: branch-miss % down on the profile; sum-of-10k bench ~1.3x+.

Phase 4 — Hashing & search for small-N dispatch

• Goal: have a hash map not a hash drag.
• Source: HPC "Hash tables", "Binary search".
• Targets: remaining maps, dashboard file lists.
• Actions:
  • Upgrade hashers on HashMap<CellId,_> (e.g. foldhash/ rustc-hash) — cheap immediate win.
  • Tiny-N dispatches (few sheets, col/row widths, CRDT op indices): BTreeMap/HashMap → Vec + partition_point.
  • Cache dashboard listings (list_saved_docs, list_spreadsheet_files) sorted once; rescan on mtime change, not per frame.
• Gate: map-heavy benches >=1.2x; dashboard refresh no longer scans disk per frame.

Phase 5 — SIMD

• Goal: vectorize only where profiles and the dense grid say so.
• Source: HPC "SIMD".
• Targets: dense-grid aggregates, import string scanning, UTF-8 width counting.
• Actions:
  • Enable autovectorization on dense-grid SUM/COLUMN/ROW/SUMPRODUCT/ COUNTIF/AVERAGE and formatting passes; Phase 1 native flags should already be emitting SIMD.
  • If profiling confirms the bottleneck: hand-vectorize chosen hot scalar loops (#[target_feature] + runtime dispatch) for numeric aggregates and for string scanning (whitespace/§/| split in doc_import.rs, RTF/XML walkers, text width in text_measure.rs / projection_layout.rs).
• Gate: >=2x on aggregate-range benches and import parser hot loops.

Phase 6 — Strings & CRDT (correctness-sensitive)

• Goal: fewer, smaller allocations per edit; incremental layout.
• Source: HPC "String algorithms", "Data structures" (avoid re-allocation).
• Targets: doc-engine/src/crdt/document.rs, doc-ui projection_layout.rs, projection_session.rs, both persistence paths.
• Actions:
  • Per-char String atoms → Vec<char>/char-array atoms; CRDT walkers (visit_text, materialize_block_text) borrow slices instead of clone+push.
  • Incremental projection: layout_projection rebuilds per keystroke (projection_layout.rs:418) — dirty-range layer so typing in block 3 does not re-layout blocks 1-50. glyph_index_of (O(n)) → Fenwick tree over block/line lengths (O(log n)).
  • Save path: crdt_save_wire serializes the whole doc on every edit (workspace.rs:446/848, save_doc_state) — debounce (200-500ms) and/or op-log delta + occasional snapshot instead of full to_json per keystroke. Same for spreadsheet save().
  • Import (doc_import.rs): reuse buffers per paragraph.
• Gate: typing latency flat at 10k-char doc; save no longer blocks the UI thread; CRDT + RNG property tests pass unchanged.

Phase 7 — I/O & persistence

• Goal: never block the UI thread on a full-document write.
• Source: HPC "Fast I/O" (buffered, batched, mmap).
• Targets: persistence modules, import paths, dashboard lists.
• Actions:
  • Background-save queue (single worker) for doc & spreadsheet autosave; UI thread never does sync fs::write of a whole doc.
  • .xlsx/.odt/.docx import: mmap large files; single-pass read/scan.
  • Dashboard file listings: cache + mtime guard (ties into Phase 4).
• Gate: 1-5MB office-file import dropped 30%+; no UI hitches during autosave.

Phase 8 — Horizontal parallelism (last, and only if needed)

• Goal: multicore scaling after the single-core work is done.
• Source: HPC "Concurrency".
• Targets: engine-only, never inside makepad draw/handle.
• Actions:
  • Parallel dirty-cell recalculation (chunk sheets per core; join at boundaries) via rayon or a hand-rolled scoped pool.
  • Parallel import parse (zip-entry decode) if benches justify.
• Gate: >=3x on large-workbook recalc with unchanged formula results and identical ordering behavior.

Phase 9 — Regression gate & rollout

• Port the top benches into CI (cargo bench); wire perf smoke tests into the existing tests.rs / tests_pure.rs (CRDT RNG property tests especially — invariant preservation is non-negotiable).
• Update BENCH_BASELINE.md and the PHASE*_SUMMARY.md docs with the phase table; each phase 1-8 ships its before/after numbers.
• Mobile/config check (pageflipnav / Android): target-cpu=native fallbacks, no unsupported intrinsics at runtime, keep CI on the portable path.

Ordering and gates

0 (measure) -> 1 (codegen) -> 2 (layout) -> 3 (branchless/ILP)
  -> 4 (hash/search) -> 5 (SIMD) -> 6 (strings/CRDT) -> 7 (IO)
  -> 8 (parallelism) -> 9 (regression gate)

Phase 6 is the riskiest for the CRDT invariants, so it lands after the safe wins and carries its own property-test gate. Nothing in phases 1-8 may change observable model behavior; every phase is gated on the existing test suites plus the baseline numbers.

Risks

• CRDT determinism: changes to materialize/op iteration must keep deterministic order; RNG tests are the gate.
• target-cpu=native breaks portable/mobile builds — feature-gated with a fallback.
• HashMap-to-dense-grid resize cost on huge sparse imports — keep the sparse overflow map; profile first.
• Premature SIMD/parallelism — phases 5/8 explicitly gated on profiles showing the bottleneck.