Three WeakMaps that made caret navigation 240x faster

I build a canvas word processor. It paints documents to a <canvas> instead of the DOM and round-trips DOCX. One user edits appraisal reports that run 50 to 110 pages. On those, the caret lagged behind the arrow key.

I measured it. Each arrow keypress cost about 8 milliseconds of JavaScript before anything repainted. The frame budget is 16 milliseconds. Half of every frame vanished into deciding where the caret should land, before the paint even started. Hold the key down and frames dropped.

The fix turned out to be three small caches. Working out which three took the whole day.

The data model

The document is one immutable tree. Blocks hold paragraphs, tables nest paragraphs inside cells, and header/footer bands and footnotes sit off to the side. Two helpers flatten all of that:

Call blockById and you rebuild the entire paragraph list, then scan it for one id. A single arrow keypress ran that chain four or five times.

One more detail, and it earns its keep later: every edit returns a brand new document object. The model is a persistent data structure, so nothing mutates in place.

My theory was obvious. Replace the linear scan with a dictionary and get O(1) lookups. Before writing a line of that, I ran two experiments.

Experiment one: does the speedup exist?

I wrote a microbenchmark comparing the current rebuild-and-scan against a memoized index across document sizes.

The linear version scaled with the document, as expected: 0.16 ms at 100 paragraphs, 6 ms at 5,000. The indexed version stayed flat near 0.001 ms whatever the size. The algorithm claim held.

The benchmark also handed me an honest catch. For a single lookup on a document that changes right after, building a whole index costs more than one scan. Worth knowing before I shipped a regression.

Experiment two: does the speedup matter?

A benchmark proves a speedup is possible. It says nothing about whether real editing touches the slow path. So I instrumented the actual helpers, loaded two real reports, drove a real editing session, and counted how often each document got read.

Two results changed the plan.

Typing reads the document zero times. The insert-text command computes the new caret from the old offset plus the length of what you typed. It never looks up a block. The dictionary I was about to build would do nothing for the most common thing users do.

Navigation was far worse than the 8 milliseconds suggested on the surface. One hundred arrow keys on a 3,263-paragraph report triggered 5.87 million band-membership checks. The selection controller filters body paragraphs against the header/footer set on every keypress, and that membership test rebuilt all six band lists once per paragraph it checked. The test was quadratic, and that was where the 8 milliseconds went.

Cache on the document's identity

The persistent data structure pays off here. Every edit produces a new document object, so a WeakMap keyed on that object memoizes with no invalidation code at all. A new document misses the cache, the old one gets collected, and the key itself keeps the result correct.

I added three caches:

1. an id-to-paragraph index behind paragraphsOf, blockById, and blockIndexOf
2. a set of band paragraph ids for the membership test, so it stops rebuilding six lists per check
3. the filtered navigation list the controller reads on every keypress

The layout code already used this exact idiom, a WeakMap over the immutable layout tree, so the change read like the surrounding code instead of a bolted-on trick.

Results

The band-membership checks dropped from 5.87 million to 6 across 100 keystrokes: one build, then cache hits. Per keypress, navigation went from 8.3 ms to 0.03 ms, between 240 and 350 times faster depending on the report. The whole suite of 1,300 tests stayed green, because the memoized list holds the same paragraphs in the same order as the filter it replaced.

What I took away

Measure the algorithm, then measure the session. The benchmark told me a fast version existed. The session told me typing would not benefit and navigation was quadratic, which is the opposite of what I assumed walking in.

I got invalidation for free because the model never mutates. A content-keyed cache needs someone to remember to clear it. An identity-keyed WeakMap over a persistent structure clears itself the moment an edit swaps the object.

With lookups free, the next bottleneck stood out. The full-document relayout fires on every edit and costs 6 to 7 milliseconds on the 100-page reports, because the layout engine re-paginates the whole document for a one-paragraph change. That one sits in the backlog behind incremental layout, which has to get page-break cascades right before it can ship.