tree c237a0356d01484c2f7496d7138e1c924d526fb6
parent 84a35ef54dff3c5596983e180ec10919fc432242
author Radu Berinde <radu@cockroachlabs.com> 1501897112 -0400
committer Alan Donovan <adonovan@google.com> 1503328930 +0000

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>