image/draw: finding the closest palette color is slow for large palettes #81936

Results for the paletteGrid change to image/draw's drawPaletted, on tip (1e963f8), Apple M2 Pro, darwin/arm64.

Output is unchanged. Every result below that has output was checked against the old code by SHA-256 of the encoded GIF or of the paletted pixels, and all of them match.

Benchmarks

10 alternating old/new runs of prebuilt test binaries. The old binary is HEAD's draw.go and draw_test.go with the new bench_test.go, so that BenchmarkPalettedWebSafeRGBA exists on both sides. Every other image/draw and image/gif benchmark, 23 of 26 including gif Decode, shows no significant change (all p > 0.05).

pkg: image/draw
                       │   old.txt    │               new.txt               │
                       │    sec/op    │   sec/op     vs base                │
PalettedFill-10           5.348µ ± 1%   5.355µ ± 0%        ~ (p=0.956 n=10)
PalettedRGBA-10           751.4µ ± 1%   751.0µ ± 1%        ~ (p=0.971 n=10)
PalettedWebSafeRGBA-10   33.042m ± 2%   5.967m ± 1%  -81.94% (p=0.000 n=10)

pkg: image/gif
                           │   old.txt    │               new.txt               │
                           │    sec/op    │   sec/op     vs base                │
EncodeRandomPaletted-10       2.950m ± 0%   2.940m ± 0%        ~ (p=0.631 n=10)
EncodeRandomRGBA-10          123.91m ± 2%   21.23m ± 1%  -82.87% (p=0.000 n=10)
EncodeRealisticPaletted-10    103.5µ ± 1%   103.2µ ± 1%        ~ (p=0.436 n=10)
EncodeRealisticRGBA-10        5.583m ± 2%   2.158m ± 1%  -61.35% (p=0.000 n=10)

                           │   old.txt    │               new.txt                │
                           │     B/op     │     B/op      vs base                │
EncodeRandomRGBA-10          407.5Ki ± 0%   550.0Ki ± 0%  +34.97% (p=0.000 n=10)
EncodeRealisticRGBA-10       103.5Ki ± 0%   159.5Ki ± 0%  +54.13% (p=0.000 n=10)
                           │  old.txt   │                new.txt                │
                           │ allocs/op  │ allocs/op   vs base                   │
EncodeRandomRGBA-10          13.00 ± 0%   28.00 ± 0%  +115.38% (p=0.000 n=10)
EncodeRealisticRGBA-10       13.00 ± 0%   23.00 ± 0%   +76.92% (p=0.000 n=10)

End-to-end

Each case is timed as the best of several runs, alternating between the old and new builds. The photo is a real 4000x2670 JPEG, scaled with nearest neighbor to the sizes shown.

Throughput with all 10 CPUs encoding 60 GIFs of 1000x667 at once:

The extra allocation per encode is small next to the encode's own, and does not show up as GC pressure.

amd64

Not measured on real amd64 hardware. Under Rosetta 2 on the same machine, which is translated code and only a rough signal, the pattern is the same:

goarch: amd64
PalettedRGBA-10           1.145m ± 16%   1.142m ± 8%        ~ (p=0.240 n=6)
PalettedWebSafeRGBA-10   43.681m ±  5%   6.885m ± 7%  -84.24% (p=0.002 n=6)
EncodeRandomRGBA-10      153.53m ±  2%   24.32m ± 7%  -84.16% (p=0.002 n=6)
EncodeRealisticRGBA-10    7.169m ±  6%   2.345m ± 1%  -67.29% (p=0.002 n=6)

It would help if someone could run the benchmarks on a real amd64 machine.

Tests

• ./all.bash: ALL TESTS PASSED.
• go vet image/draw image/gif: clean.
• go test -count=1 image/...: all packages pass.
• go test -race image/draw image/gif: pass.
• go vet plus a test build of image/draw succeed for linux/386, linux/arm, linux/amd64, linux/ppc64le, linux/s390x, windows/386, js/wasm and wasip1/wasm.
• The image/draw and image/gif tests pass as amd64 binaries under Rosetta 2.

The new tests catch all 11 hand-made bugs I tried in the grid:

• a strict < where the list bound needs <=;
• ties going to the higher index;
• a farthest distance using half a cell;
• a nearest distance that ignores the cell;
• one alpha slab used for every alpha;
• the cell index dropping the blue channel;
• no range check on the palette;
• no range check on the pixel;
• a panic on the memory-cap path;
• a color dropped on the memory-cap path;
• a wrong whole-palette list.

Outside the CL, I also ran differential tests against the old code:

• 7 source kinds × 28 palettes × Src/FloydSteinberg × 3 rectangles;
• a fuzz target comparing old and new over 17 to 256 color palettes and 256x256 images;
• a separately written harness, run on the previous revision of this change with the same algorithm: 6M direct paletteGrid.index checks against the linear search, and 14.5M fuzz runs.

None of them found a mismatch.

Costs

• Memory: 32 KiB of cells per alpha slab plus the candidate lists. An opaque image uses one slab. The lists are capped at 256 KiB.
• Worst case: small images whose colors rarely share a cell. Random noise at 64x64 is 3x slower, and 128x128 is 1.25x slower. From 256x256 up, noise is faster again. Photos, graphics and video frames are faster at every size that uses the grid.
• Test time: image/draw's tests take 0.75 s instead of 0.02 s, mostly TestPaletted comparing against the generic drawing path.
• Code size: about 1.5 KB of machine code on arm64. drawPaletted grows by 384 bytes, and paletteGrid.index and paletteGrid.fill add 1088 bytes between them.