# 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.