Reduce number of memcmp invocations in PTreeImpl::[upper|lower]_bound
- Dominant language
- C++
- Stars
- 16.7k
- Forks
- 1.6k
- Avg merge
- 1d 20h
- Merged PRs (30d)
- 126
Description
The storage server spends a large fraction of its time in `PTreeImpl::lower_bound` and `PTreeImpl::upper_bound`. These methods work by invoking `T::operator<()` in a few redundant ways.
Both methods populate a vector of tree nodes, invoking `x < node->data` each time they push a value on the end. At return, they invoke `x < node->data` again as they pop any nodes that are not less than / greater than `x` off the end of the vector.
`lower_bound` further computes `node->data < x` each time it pushes something onto the vector.
Reimplement the two methods to invoke the equivalent of `memcmp(node->data, x)` at most once for each node encountered during the traversal.
Note that, in the common case, `operator<` ends up compiling down to `__memcmp_sse4_1`. Be careful not to break that optimization.
Contributor guide
Assessment
This issue has not been assessed yet.