]> git.apps.os.sepia.ceph.com Git - ceph.git/commit
inverval_set: optimize subset_of with sequential search
authorZac Medico <zmedico@gmail.com>
Tue, 26 Sep 2017 06:13:57 +0000 (23:13 -0700)
committerZac Medico <zmedico@gmail.com>
Wed, 27 Sep 2017 00:33:35 +0000 (17:33 -0700)
commit5c3775815a433a028618b239f5a4bebacff3dc4b
treea94e6a499f58ac8b8f1ec7915ac013219e14e7b1
parent85f3227885dd631a3c2b5f284c485d07b7b0fdcb
inverval_set: optimize subset_of with sequential search

Optimize subset_of to use sequential search when it
performs better than the lower_bound method, for set
size ratios smaller than 10. This is analogous to
intersection_of behavior since commit 825470fcf919.

The subset_of method can be used in some cases as a
less-expensive alternative to the intersection_of
method, since subset_of can return early if any element
of the smaller set is not contained in the larger set,
and intersection_of has the added burden of storing
the intersecting elements.

Signed-off-by: Zac Medico <zmedico@gmail.com>
src/include/interval_set.h
src/test/common/test_interval_set.cc