jpountz opened a new pull request, #13692:
URL: https://github.com/apache/lucene/pull/13692
Advancing within a block consists of finding the first index within an array
of 128 values whose value is greater than or equal a target. Given the small
size, it's not obvious whether it's better to perform a linear search, a binary
search or something else... It is surprisingly hard to beat the linear search
that we are using today.
Experiments suggested that the following approach works in practice:
- First check if the next item in the array is greater than or equal to the
target.
- Then find the first 4-values interval that contains our target.
- Then perform a branchless binary search within this interval of 4 values.
This approach still biases heavily towards the case when the target is very
close to the current index, only a bit less than a linear search.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
