apple / apple/foundationdb

Reduce number of memcmp invocations in PTreeImpl::[upper|lower]_bound

Open
#2,877 0 comments 0 reactions 1 assignee Claimed by @sears View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.