uber / h3-go / 36476859224

100%

master: 100%

push

github

perf: generic flat hash table and buffer reuse for CellsToMultiPolygon in x/h3go

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 an alias for 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)
DirectedEdges   ... (continued)

123 of 123 new or added lines in 7 files covered. (100.0%)

4350 of 4350 relevant lines covered (100.0%)

3046060.17 hits per line