uber / h3-go / 36462911629

100%

push

github

perf: open-addressing seen set for safe grid disk BFS in x/h3go (#139)

Port the visited-set half of uber/h3#1217 to the pure-Go safe grid disk
traversal. The C PR replaces a recursive fallback with a BFS backed by an
open-addressing hash set sized at twice the disk; x/h3go was already a
queue-based BFS, so the remaining gap was the Go map used to track visited
cells. Replace it with a flat slice hash set (zero Cell as the empty
marker, linear probing) and use each completed ring as the queue for the
next, which drops the separate queue and its growth.

Add BenchmarkGridDiskPentagon to paritytest so the pentagon fallback path
is measured at k=10..40.

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

                                 │     old     │            new             │
                                 │   sec/op    │   sec/op     vs base       │
GridDiskDistancesSafe/impl=go-16   8.905µ ± 6%   3.858µ ± 3%  -56.68% (p=0.002 n=6)
GridDiskPentagon/k=10/impl=go-16   51.53µ ± 5%   30.36µ ± 1%  -41.09% (p=0.002 n=6)
GridDiskPentagon/k=20/impl=go-16   223.6µ ± 2%   121.9µ ± 3%  -45.47% (p=0.002 n=6)
GridDiskPentagon/k=30/impl=go-16   501.3µ ± 2%   273.4µ ± 4%  -45.46% (p=0.002 n=6)
GridDiskPentagon/k=40/impl=go-16   939.9µ ± 2%   496.2µ ± 2%  -47.20% (p=0.002 n=6)
geomean                            137.0µ        72.02µ       -47.45%

allocs/op: GridDiskDistancesSafe 20 -> 4; GridDiskPentagon 30/47/65/91 -> 5.

Co-authored-by: Claude Fable 5.1 <noreply@anthropic.com>

23 of 23 new or added lines in 1 file covered. (100.0%)

4267 of 4267 relevant lines covered (100.0%)

3083464.19 hits per line