uber / h3-go / 36480078553

100%

push

github

perf: generic flat hash table and buffer reuse for CellsToMultiPolygon in x/h3go (#141)

Generalize the open-addressing cell set from PR 140 into flatTable[K Index, V],
a linear-probing table keyed by any H3 index type with an inline value. cellSet
becomes a thin wrapper over flatTable[Cell, struct{}], and the value field is
placed first so a set entry stays 8 bytes (Go pads a trailing zero-size field).

Use it in CellsToMultiPolygon, which was the last parity benchmark where the
pure-Go path was materially slower than cgo (188 allocs/op):

- buildArcs indexes edge to arc position in a flatTable[DirectedEdge, int]
  instead of a Go map, and enumerates each cell's edges into a stack array via
  the new appendDirectedEdges instead of a heap slice per cell.
- buildOutlineLoops counts a loop's arcs first and allocates its vertex slice
  once (one vertex per arc, two at Class III resolutions), then appends every
  edge boundary straight into it through the new DirectedEdge.appendBoundary.
- The stable sorts move from sort.SliceStable to slices.SortStableFunc.

The boundary builders now append into a caller-supplied slice. Cell.Boundary
and DirectedEdge.Boundary preallocate their maximum size, so they make one
allocation instead of growing through four, and callers that consume the
result immediately (CellArea, EdgeLength, Vertex.LatLng, hexRadiusKm) get the
buffer on the stack.

Output ordering is unchanged; the cgo parity tests cover it.

benchstat, Go implementation only, 10 runs each, Apple M3 Max:

                         │   old (6b129ec)   │             new              │
                         │      sec/op       │   sec/op     vs base         │
CellsToMultiPolygon      46.25µ ± 13%   33.18µ ± 4%  -28.27% (p=0.000 n=10)
CellToBoundary           477.5n ±  6%   426.2n ± 2%  -10.76% (p=0.000 n=10)
DirectedEdgeBoundary     880.7n ± 40%   325.5n ± 5%  -63.04% (p=0.000 n=10)
VertexLatLng             221.0n ± 17%   179.4n ± 3%  -18.85% (p=0.000 n=10)
Di... (continued)

127 of 127 new or added lines in 6 files covered. (100.0%)

4356 of 4356 relevant lines covered (100.0%)

3042986.57 hits per line