Calling op.apply on an op we know to be an add ends up noticably
increasing the cost of the operation; this trivial change gets about
a 5-10% reduction in reported runtime of benchmarks doing a lot
of adds. (The other IntersectionCount benchmarks don't actually use
Add most of the time, so it doesn't show up in them.)
name old time/op new time/op delta
GetBenchData-8 4.25ms ± 0% 3.91ms ± 2% -8.04% (p=0.002 n=6+6)
Bitmap_IntersectionCount_ArrayArray-8 20.9µs ± 2% 18.7µs ± 3% -10.18% (p=0.004 n=5+6)
SliceAscending-8 24.7ms ± 0% 21.8ms ± 0% -11.74% (p=0.004 n=5+6)
SliceDescending-8 29.8ms ± 0% 27.0ms ± 0% -9.56% (p=0.004 n=5+6)
SliceAscendingStriped-8 32.0ms ± 0% 29.5ms ± 0% -8.07% (p=0.008 n=5+5)
SliceDescendingStriped-8 39.3ms ± 1% 36.8ms ± 1% -6.27% (p=0.002 n=6+6)
Two changes: First, make SliceDescending set the entire
slice, not all-but-one bits. Second, add tests that are
"striped", so it's writing to 8 parts of the slice
sequentially, rather than just going up or down the whole
thing, because that gives us some cheap indication of
cache-locality impact, which turns out to be possibly
significant.
I am aware that I don't actually ever use the length of a
after this line of code, but if I don't correctly update it,
any future change that needs that length will break
mysteriously. We humbly ask gometalinter to consider
the reply of counsel in _Arkell v. Pressdram_ (1971).
A transient bug introduced in intersectionCountArrayArray was
not caught by the tests, because it would only manifest when
two containers of different lengths were being compared. Also
improve the testing for intersectArrayArray, even though that
code hasn't been changed.
Roaring likes to call things "a" and "b", not "1" and "2",
and use "n" for length, not "l", etcetera. Adopt these
conventions to make code more readable.
Also drop the 'vb' value since it isn't expensive to
compute and the compiler can figure out that it can
reuse the value.
confirm that the number of runs comes out as expected,
and add a couple of numbers out of order to verify that
the 17-18-19 set gets coalesced into one run even
if we add 17 and 19 before 18.
The net effect of this is to not recompute "the current
value of the first array" on every loop, pretty much.
However, the swap to make sure the inner loop is on the
longer array seems to be significant for performance.
On my system, this moves runtime from ~29us per op
to ~17us per op.
If the total number of things returned was small enough to
make an array, intersectBitmapRun converted to an array. This
seems possibly-premature; future processing might well prefer
a bitmap. We know everything gets optimized before being
written out, let's not convert without a specific reason. But
also, let's use an array no matter which container is small
enough to prove that we can do so safely.
Fixes#854.
The circumstances under which bitmaps are converted between
types are not 100% nailed down, and the IntersectionCount
benchmark was actually using a bitmap for the "run" data set
as well as for the "bitmap" data set. Fix that by using
Optimize() explicitly. Also, add a second RLE set so we
can compare the difference between "one run for the entire
set" and "several runs".
Also add array/array comparisons. We use two different
lengths of arrays, because performance turns out to vary
between "first array longer" and "second array longer".
Also added a benchmark for getBenchData itself, since it's
at least one possible use case for "creating a lot of
containers".
bitmapEquals isn't currently being called ever, but it has
an arcane edge-case bug, so I've made the test case for it
and commented it out for future reference.
This commit adds some trivial stat-tracking which can be
observed at localhost:10101/debug/vars. However, writes to
a locking data structure aren't cheap, so the stat-tracking
is by default not compiled. To build it, add the build
tag `roaringstats`, which will cause the `statsHit` function
to actually do something. Otherwise, it's an empty and
inlineable function, meaning the compiler throws it away
entirely.
This would, in principle, let us get additional visibility
into edge cases and which code paths are hot. This is not
the same thing as profiling for overall performance; the
stat counts aren't affected by whether a particular code path
is using a large amount of CPU time, just reporting how
often it happens at all.
confirmed that bounds checks are still avoided by
go test -gcflags="-d=ssa/check_bce/debug=1"
./roaring.go:3387:8: Found IsSliceInBounds
./roaring.go:3388:8: Found IsSliceInBounds
./roaring.go:3436:21: Found IsSliceInBounds
