couchbaselabs / vellum / 118

82%

push

travis-ci

MB-30266 - FSTIterator.next() optimizations

The optimizations include...

* fewer byte slice comparisons of the iterator's current candidate key
  (keysStack) against the iterator's previously produced key
  (nextStart), by tracking an allowCompare flag.

* the first time through, the allowCompare flag is false, as the
  candidate key and the previous key are exactly the same, so a
  comparison can be skipped.

* each time through the loop, this optimization flips allowCompare to
  true only if we pushed another byte onto the keysStack -- meaning
  the current candidate key had one more suffix byte appended.  In
  this case, comparing against the nextStart is legit.

* however, if we're popping bytes off of the keysStack (i.e., the
  iterator is backtracking or unwinding in the state diagram) then
  keep allowCompare as false, to not bother with a bytes slice
  comparison as we've already seen and examined this state or
  candidate key already in some previous loop.

* endKeyExclusive optimization: before this commit, there would be a
  bytes slice comparison against the (potentially nil) endKeyExclusive
  whenever another byte was pushed onto the keysStack.  Instead, in
  this commit, the endKeyExclusive comparison is moved to just before
  we return from next() with a nil error.  The thinking most of the
  time, we're not running into the endKeyExclusive when we're
  traversing the state diagram, so don't bother with an
  endKeyExclusive comparison in the main loop, but only a very last
  moment.

* before this commit, the code would pop just a single state from the
  state tracking stacks and then loop back to the top of the main loop
  to rexamine the current state.  Instead, if the state tracking
  stacks represent a simple suffix of bytes that's a linear sequence
  of nodes (no multiple outbound transitions), then the optimization
  is to pop off that suffix in one shot because it doesn't need
  reexamining.

Change-Id: If875995e73b1254c07efac6... (continued)

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

1140 of 1398 relevant lines covered (81.55%)

2842.24 hits per line