go /
tools /
43e94ff2028def3d10b2a2159622f59510ea75a1 x/tools/container/intsets: use root block
The root block was used as a sentinel. This means we always need to
allocate a second block on the heap, even if the set has a few small
elements.
We now use the root block: it is always the block with the smallest
offset. The logic becomes very messy if there is no sentinel; to avoid
this we still use a sentinel (a special singleton block) and return it
in when appropriate in the first, last, next wrappers.
Also adding some benchmarks and making some optimizations:
name old time/op new time/op delta
Popcount-4 2.18ns ± 1% 2.21ns ± 1% +1.47%
InsertProbeSparse_2_10-4 76.2ns ±23% 37.2ns ± 1% -51.21%
InsertProbeSparse_10_10-4 240ns ±15% 162ns ± 4% -32.58%
InsertProbeSparse_10_1000-4 419ns ± 4% 371ns ±19% -11.43%
InsertProbeSparse_100_100-4 2.30µs ± 1% 1.93µs ± 1% -16.08%
InsertProbeSparse_100_10000-4 2.12µs ± 3% 2.07µs ± 1% -2.11%
UnionDifferenceSparse-4 165µs ±16% 170µs ± 9% ~
UnionDifferenceHashTable-4 310µs ±10% 291µs ±17% ~
AppendTo-4 11.0µs ± 0% 11.0µs ± 0% -0.35%
name old alloc/op new alloc/op delta
Popcount-4 0.00B ±NaN% 0.00B ±NaN% ~
InsertProbeSparse_2_10-4 64.0B ± 0% 0.0B ±NaN% -100.00%
InsertProbeSparse_10_10-4 64.0B ± 0% 0.0B ±NaN% -100.00%
InsertProbeSparse_10_1000-4 256B ± 0% 192B ± 0% -25.00%
InsertProbeSparse_100_100-4 64.0B ± 0% 0.0B ±NaN% -100.00%
InsertProbeSparse_100_10000-4 256B ± 0% 192B ± 0% -25.00%
UnionDifferenceSparse-4 59.4kB ± 0% 59.2kB ± 0% -0.32%
UnionDifferenceHashTable-4 138kB ± 0% 138kB ± 0% ~
AppendTo-4 0.00B ±NaN% 0.00B ±NaN% ~
name old allocs/op new allocs/op delta
Popcount-4 0.00 ±NaN% 0.00 ±NaN% ~
InsertProbeSparse_2_10-4 1.00 ± 0% 0.00 ±NaN% -100.00%
InsertProbeSparse_10_10-4 1.00 ± 0% 0.00 ±NaN% -100.00%
InsertProbeSparse_10_1000-4 4.00 ± 0% 3.00 ± 0% -25.00%
InsertProbeSparse_100_100-4 1.00 ± 0% 0.00 ±NaN% -100.00%
InsertProbeSparse_100_10000-4 4.00 ± 0% 3.00 ± 0% -25.00%
UnionDifferenceSparse-4 928 ± 0% 925 ± 0% -0.32%
UnionDifferenceHashTable-4 271 ± 0% 271 ± 0% ~
AppendTo-4 0.00 ±NaN% 0.00 ±NaN% ~
Fixes golang/go#21311.
Change-Id: Ie472a2afa269c21cb33b22ffdac8dd2594b816ac
Reviewed-on: https://go-review.googlesource.com/53431
Reviewed-by: Alan Donovan <adonovan@google.com>
2 files changed
