sg

← Writing

The Lock Was Fine

· systems · performance

When I zoomed all the way out on a fresh Fractal canvas, the overview filled in one cell at a time. The server took 8.9 seconds to build it, and the browser got the last image at 9.1. I suspected the lock that guards the canvas, and fixing that lock would have meant changing how every canvas is stored. It was held for 5 milliseconds in total. The time went somewhere much more ordinary.

Fractal stores strokes in tiles, and when you zoom out, art drawn deeper in shows up as cell images. For each cell, the server rasterizes everything inside it, meaning it draws it as pixels in a 256 × 256 PNG, and sends it down. Four workers do the rasterizing.

Agents wrote most of that code. Finding where the time went, and what to change, was my part (how that split works).

The obvious suspect#

The lock was my first suspect because of how every cell image starts. The server takes the canvas read lock, copies every stroke that reaches into the cell, and sorts the copies into paint order. At the overview, a cell over the middle of the artwork holds every nested scene below it, so that's a lot of copying under a lock that writes also need.

A plan for growing the showcase art said the same thing in one line: "Expect slow first builds and lock contention with writes." My suspicion came from reading the code, before any measurement.

If the lock were the problem, the fix would be expensive. Fractal is one Go process, and each canvas lives in memory behind one sync.RWMutex lock that disk snapshots also read through. The plan for saving to disk already named the way out if waiting on this lock became a problem: a copy-on-write tile map, where a write makes a fresh copy instead of making readers wait. That would change how every canvas is stored, so before changing anything, I measured.

What the lock actually did#

To check the lock, I timed every stage of building a cell. I froze a test set of 1,869 strokes and 211,085 points and replayed it into a private server through the normal WebSocket connection, with client and server both on one M5. Temporary timers wrapped each stage of a cell build: snapshot, raster, PNG encode, marshal, socket write.

For the cold overview:

StagemsMeasured as
Backend completion8,919Wall clock, subscribe to last reply
Read-lock hold5.018Sum over all snapshots
Longest single hold1.738One snapshot
Rasterization24,344Sum across 4 workers
PNG encoding94Sum across 4 workers

The four workers ran at the same time, so their sums don't add up to wall-clock time, but the lock rows are tiny either way. Waiting to get the read lock took 1.46 to 7.38 microseconds in total per view, across every view that needed images. Five milliseconds of lock can't explain nine seconds of anything.

The code agreed: only the snapshot runs under the lock, and a worker rasterizes the copy after the lock is released.

So the plan was right that first builds were slow, but at the size I measured, it had the cause wrong.

Where the 8.9 seconds went#

The table points at rasterization: 24.3 seconds of worker time, against 94 ms of PNG encoding. The same run's memory numbers pointed at why drawing was so slow. It allocated 45.916 GiB of memory and triggered 1,815 garbage collections, yet afterward the process held only about 92 MiB. The 46 GiB was never held at once. It was churn: short-lived memory, asked for and thrown away over and over.

Go's memory profile was blunt about which code asked for it. One function, polygonSpans, accounted for 94.15% of sampled allocated bytes.1 The profile below is trimmed, and it adds up all my profiling runs, not just the one above, so its totals are far bigger than 46 GiB. The shares are what matter:

Type: alloc_space
      flat  flat%   sum%        cum   cum%
  419.68GB 94.15% 94.15%   431.57GB 96.81%  canvas.polygonSpans
    9.68GB  2.17% 96.32%    12.88GB  2.89%  internal/reflectlite.Swapper
    9.29GB  2.08% 98.40%   441.85GB 99.12%  canvas.geometrySpans
    3.20GB  0.72% 99.12%     3.20GB  0.72%  internal/reflectlite.unsafe_New
         0     0% 99.28%    12.88GB  2.89%  sort.Slice

To see what that function was doing, I looked at the worst overview cell, which took 8.83 seconds by itself with 499 strokes in its snapshot. A build with extra counters recorded what happened inside it:

  • 202,329,021 polygon scans
  • 729,312,494 edge tests
  • 8,917,624 scans that found any crossing at all

So 95.59% of the scans found nothing, and each of those still allocated a list for its results and sorted it.

Why most scans come up empty#

The empty scans come from how the rasterizer measures coverage. To work out exactly how much of each pixel a stroke covers, it splits each pixel row into eight horizontal strips, then splits again at every break in the geometry, such as every vertex (corner) of the stroke's outline. For each strip, it asks every polygon in the stroke which spans, or stretches of the row, it covers at that height. To answer, it walks every edge of the polygon.

Strip scan over one pixel rowA stroke made of 10 polygons crosses one pixel row. The row is cut into 8 strips plus a cut at each polygon vertex height inside it, and every strip's mid-height is a sample. At the marked height all 10 polygons are scanned edge by edge; 2 return a span and 8 return nothing.A stroke is 10 polygons12345678910one pixel rowThe row, magnified8 equal strips, plus a cut at each vertex heightvertex cutvertex cutvertex cutvertex cut12 strips after the cuts, each sampled at mid-heightthis heightAt this height, all 10 polygons are scanned, edge by edge12345678910nothing foundspan foundnothing found
One pixel row of a ten-polygon stroke. At the marked height, the crossing test runs on all ten polygons; two return a span and eight return nothing.

The overview makes this worse. Art from many zoom levels gets squeezed into one 256-pixel cell, so each row has more vertices and more strips, and every strip still scans every polygon, even ones nowhere near that height. The counters found 287,444 span evaluations in that cell, which works out to roughly 700 polygons scanned per evaluation (a figure I derived rather than measured). Most of them answer "nothing here."

The first fix: stop paying for empty scans#

Every empty scan paid for a list and a sort it never used, so that was the first thing I changed. Here's the fix, against the function as it was (trimmed):

diff · go
 func polygonSpans(poly []xy, y float64) []span {
 	if len(poly) < 3 {
 		return nil
 	}
-	intersections := make([]crossing, 0, len(poly))
+	var intersections []crossing
 	for i, a := range poly {
 		b := poly[(i+1)%len(poly)]
 		if (a.y <= y && b.y > y) || (b.y <= y && a.y > y) {
 			// ...winding direction...
+			if intersections == nil {
+				intersections = make([]crossing, 0, len(poly))
+			}
 			intersections = append(intersections, crossing{ /* x, wind */ })
 		}
 	}
+	if len(intersections) < 2 {
+		return nil
+	}
 	sort.Slice(intersections, func(i, j int) bool { /* by x */ })

The old version allocated a full-size list before it knew whether anything crossed. Then it handed the list to sort.Slice, which uses reflection (Go inspecting types at runtime) and allocates too: the reflectlite rows in the profile. The new version allocates on the first real crossing, and skips the sort when there are fewer than two. Coverage math, the fill rule, and paint order are untouched, and across 960 compared cells, every decoded image matched the old output exactly.

Three more fixes, one profile at a time#

The first fix wasn't going to be enough on its own, because skipping empty allocations doesn't skip the walking: every strip still tests every edge of every polygon. The plan for this performance work said so up front. I made one change at a time, took a new profile before choosing the next, and gave each change its own before-and-after run.

Each fix got three runs on a second frozen set of 1,792 strokes. Every run started a fresh server with a few timers added and loaded the same overview through a script.2 On this set, the first fix alone cut total allocation from 30.425 GiB to 8.041 GiB, and process CPU from 39.3 to 12.2 core-seconds.

FixBefore (ms)After (ms)
Allocate on first crossing12,186.34,250.3
Typed sorts4,250.32,852.6
Vertical bounds2,820.81,906.2
Scratch buffers1,906.2831.9

Typed sorts means slices.SortFunc instead of sort.Slice, so no reflection.

Vertical bounds skips any polygon whose top-to-bottom range misses the sampled height. In one dense overview cell, polygon calls fell from 116.9 million to 8.1 million. Allocation barely moved, because this fix cut walking, not allocating.

Scratch buffers are working memory reused within one cell render. They took allocation from 6.365 GiB to 0.214 GiB.

Last, I measured the whole first round end to end in a real browser, with normal Go builds and no timers. The cold overview's time to ready went from 6,098.1 ms to 639.9 ms, one sample each, and Go CPU for that load went from 19,760 ms to 1,460 ms.3 The round also changed the client and how data reaches it, so not all of that belongs to the rasterizer.

What I left alone#

None of this touched the lock. The performance plan ruled that out in plain terms: don't redesign the locking, and don't move rendering out of a lock it doesn't even hold. So the locking and the disk saving stayed, and Fractal is still one Go process with one RWMutex per canvas. All four raster fixes landed in one file: 62 lines added, 15 removed.

I didn't add workers either. The four were already fighting heavy allocation, and more workers can't split one 8.8-second cell.

One lock change did come up and was put off: sorting the copied strokes after releasing the lock instead of before. It would shorten holds that were already measured in milliseconds. The sort still runs under the lock today.

What it cost, and what's left#

The fixes weren't free. Scratch buffers made the helper functions messier, and it's harder to track which code owns each reused list. Every reused list now lives for one render only. The vertical-bounds check made sparse cells slower at the time: 225.87 ms to 236.24 ms per 3,000 renders, about 4.6%. A later active-edge sweep replaced that check, and the habit of walking every polygon and edge at every sample height.

The lock question isn't fully closed. My test set had 1,869 strokes, with 499 in the worst cell, but the showcase plan was written for art about the size of today's live showcase, roughly 20,000 strokes, with around 2,500 strokes per central overview cell and over 8,000 in the biggest tier. The lock still copies every stroke a cell touches, and nobody has measured it at that size.

Writes are even less tested. In a separate test, two viewers watched one small stroke get added to a cell and then undone. The rebuild's snapshot held the read lock for 0.0646 ms and 0.1038 ms. With so few users, that says nothing about writes under real load.

The performance plan wrote down what would reopen the lock question: a profile, taken after the raster fixes, where picking snapshot strokes or waiting on the lock dominates. Until someone takes that profile, a lock redesign stays a suspicion.

Footnotes

  1. The CPU profile was less clear-cut. polygonSpans and the code it called took 24.1% of samples. A large share sat in the Go runtime, sleeping or waiting, and I can't cleanly blame that on the garbage collector. The memory profile was the one that pointed at a single function. ↩

  2. Because these runs used a different stroke set, their starting point doesn't line up with the 8.9 seconds above. Each row in the table also compares against its own fresh starting run. That's why 2,852.6 becomes 2,820.8 between rows. The rows don't multiply into one overall speedup. ↩

  3. The round's 6,098.1 ms starting point doesn't match the per-fix runs' 12,186.3 ms either. The setups differ, and I can't explain the gap. ↩