uber / h3-go / 36468931543

100%

push

github

perf: flat hash sets and cached pentagon radii for PolygonToCells in x/h3go (#140)

Follow-up to #139, applying the same open-addressing idea to the polygon
flood fill, which was the last map-backed traversal in x/h3go and the one
remaining place Go trailed cgo on time.

- Add cellSet, a linear-probing hash set of cells with a zero-value ready
  state and doubling growth, and move hashSlot from grid.go beside it.
- PolygonToCells now dedups traced seeds and tracks found cells in cellSets.
  The output slice is appended in discovery order, so the final copy out of
  the found map is gone, and each generation's search set is the tail of
  the output the previous generation appended, so the per-generation
  nextSearch buffer is gone too. The one-ring scratch buffer is a fixed
  array on the stack.
- The polygon size estimators called Pentagons(res) and projected a full
  pentagon boundary on every call to get the pentagon radius, which was 60%
  of PolygonToCells allocations. Cache the radius per resolution at package
  init using the same code path, so the values are unchanged.

benchstat, Go before vs after (Apple M3 Max, count=6):

                           │     old     │            new             │
                           │   sec/op    │   sec/op     vs base       │
PolygonToCells/impl=go-16    164.4µ ± 2%   139.0µ ± 2%  -15.43% (p=0.002 n=6)
GeoPolygonCells/impl=go-16   166.5µ ± 2%   140.0µ ± 0%  -15.90% (p=0.002 n=6)

                           │     old      │             new             │
                           │     B/op     │     B/op      vs base       │
PolygonToCells/impl=go-16    33.69Ki ± 0%   25.20Ki ± 0%  -25.19% (p=0.002 n=6)

                           │     old     │            new            │
                           │  allocs/op  │ allocs/op   vs base       │
PolygonToCells/impl=go-16     98.00 ± 0%   15.00 ± 0%  -84.69% (p=0.002 n=6)

Against cgo the Go path was 15% slower before and is now 2% faster.

Co-authored-by: ... (continued)

103 of 103 new or added lines in 3 files covered. (100.0%)

4320 of 4320 relevant lines covered (100.0%)

3062884.44 hits per line