So with the switch to a new linter, we get a lot of new warnings,
and the majority of them are harmless probably, but a few might be
real. Variously just use _ to suppress warnings, or report errors.
There's probably things here that deserve better fixes, but we can
always revisit it.
Data loss was occuring after a cluster restart. The issue was during the
unmarshaling of the op log when multiple values had been written to the log. The
lines in question were like "changed = changed || b.DirectAdd(v)" in which the
DirectAdd would only be executed when changed was initially false, once it was
true, it would never be executed again.
Since we always use the same cmp function, we don't need to
actually *call* a function -- we can just inline it. Or, in
fact, omit the computation entirely; comparing the result of
the subtraction to zero is (very slightly) more expensive than
comparing the magnitudes of two numbers.
Also fix a spurious comment and gofmt issues.
The upstream btree code has a test file, this is an import
of that test file, adjusted/adapted to make it work with our
de-genericized uint64/*Container implementation, so we have some
tests and benchmarks available for the btree implementation itself.
Did some benchmarking with b+tree values. The actual interactions
appear to be slightly inconsistent; some values seem to help more
in cases with higher OpN in benchmarks, others with lower OpN. It
appears that the practical consideration may be what happens
when a snapshot gets triggered; smaller kx/kd appear to reduce
costs there, but increase costs between snapshots. This is a
bit of guesswork.
Numbers are slighly under powers of 2, because that means that the
total actual sizes of k and d end up fitting nicely in alloc
pool sizes.
You might wonder why `i <= bitmapN-4`. Answer: The compiler isn't
smart enough for the stride analysis to figure out that `i <= bitmapN`
actually guarantees that. If you set the limit to something not a
multiple of stride, though, it can't figure out *anything* about
things. But for some reason, `i < bitmapN-3` fails badly (it
actually adds bounds checks not present with `i < bitmapN`), but
`i <= bitmapN - 4` works.
This reduces runtime of bitmapRepair by about 14%.
Treating a pointer as a pointer to a large array of bytes,
or converting back the other way, isn't totally insane, but
it does create slices with an extremely large cap. This bit
me while I was trying to build the 16-byte packed Container
structure, but it's probably actually worth fixing in general.
It used to be useful/desireable to set the other slices to nil when
setting a new slice type, it's no longer useful, take some of those
out.
Also reuse the already-computed run count when converting arrays
and bitmaps to runs.
It turns out the logic for "don't update everything if
the incoming slice pointer is the stash" is wrong; it should
really be "don't update everything if the incoming slice
pointer is the one we already have".
The reason this breaks is that one of the tests directly
sets the mapped bit. This breaks my assumption that we'd
never be using the stash and have the mapped bit set, and
that in turn breaks my assumption that the pointer
of an incoming array can't be the stash address unless
we were previously using the stash. If unmap moved us
to non-stashed memory, then a future write could try to
write, notice that it would fit in the stash, copy the
data ... and not update the pointer because the stash
pointer was handled separately.
This way, if you do that, you can end up not using the
stash when you probably could, but you get the expected
behavior. But also, don't set the mapped bit directly.
(I guess there's a good reason to for the test case,
which is using it to verify that unmaps happen when
modifications happen.)
Also the unmap functions should indicate that they have
successfully unmapped, which may help performance in
some test cases.
Noticed in profiling that unmap wasn't being inlined. Also noticed
that every call is on a specific container type, so now they're
specialized and small enough to inline.
This implementation, controlled by the build flag "container24s",
is similar to the single-slice container implementation, but goes
a bit further. First, instead of using a native slice as its internal
storage, it uses pointer/len/cap as distinct values, and only int32
ranges for len and cap. Second, it has a small region of additional
storage which it uses as a backing store by default for arrays or
runs. The idea is that, if you request a new empty array container,
you get one with a pre-allocated virtual slice big enough for five
values, actually stored in the Container. This is useful because
Go's allocator has size classes for 16 and 32 bytes, and the
Container comes in at 24 bytes worth of storage -- meaning that if
you allocate a container, you're allocating 32 bytes anyway, so we
might as well use that space to avoid extra allocations.
This includes some test fixups because DeepEqual was testing
too much equality in some tests.
Also, we simplify unionArrayArray to postpone creating a Container
until we're ready.
On a 64-bit machine, the slices in a Container consume 72
bytes, and the Container itself is 80. But we only use one
slice at a time! This patch shifts us to keeping a single
slice in the Container, and converting provided slices to
and from that type when we want to update it. (It is not
safe to access the slice through the wrong type.)
We also add some new tests, conditional on a build tag
called `roaringparanoia`. These tests will be optimized
away entirely by the compiler when the tag isn't
present, because the conditionals use a const. These catch
possible errors like trying to access the bitmap slice
of a non-bitmap container.
We also eliminate all direct creation of Container literals,
so we can mess with the internals more. (On reflection
and study, we decided not to go to the fancier design where
references to .n and .typ were also converted to function
calls, which would have allowed packing those attributes
more tightly, because it was a lot more overhead and a lot
of work to keep track of.)
There's some circumstances where we appear to have been
relying on incorrect guesses about the nature of containers.
For instance, in xorBitmapRun, there's logic that makes sense
only if the output's a run container, but it's not, it's a
bitmap container. This creates strange behavior sometimes,
though. Several of these are corrected now.
This consolidates a number of changes. The first is significant
reductions in allocation and copying during UnionInPlace
operations on very sparse containers -- for instance, combining
two array containers with one item each.
We fix up the logic for identifying and handling cases where
only one of the containers being unioned together has a given
key.
We generally favor cloning an existing container over unioning
it into a new empty container.
When unioning two containers, we were using unionIntoTargetSingle
on those two containers, into an empty bitmap. For more, we were
creating an empty bitmap, then unioning all the others into
it; it's faster to clone the first, then union the others into
it.
The overall logic for UnionInPlace is cleaned up and simplified
a bit. However, it's then complexified a bit, because it turns
out that while it's a bad idea to convert single-item arrays to
bitmaps to union them, by a few hundred items, the bitmap
conversion saves a lot of time even if it costs an allocation.
The value of N picked here is sort of arbitrary, but
512 seems to be about right. The big problem is a massive
performance hit in cases where, say, there's only a
couple of items per container, and the bitmap conversion
is extremely expensive. If you wait until N reaches
the array size cap, though, you take a very noticeable
performance hit (can be a factor of 2.5-3 in simple
testing).
We also add some stat counters, and rename an internal
method on the `handledIters` type.
Add a benchmark to test a specific case where UnionInPlace is
underperforming the naive union operation badly.
Also, the UnionBulk test was reusing a bitmap, meaning that it ended
up doing a lot of unions into a bitmap that already had all the
bits it was supposed to have. This broke a couple of other tests
in unexpected ways.
We also now use UnionInPlace in importRoaring, and test it
in the container combinations tests via a wrapper.
