Skip to content

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

@sears

Description

@sears

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.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions