[Boost-users] [Multi-Index] performance difference between lower_bound() and upper_bound()

Subject: [Boost-users] [Multi-Index] performance difference between lower_bound() and upper_bound()
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2013-11-21 09:14:56

I have a multi-index BMI (Boost 1.44), with an ordered_non_unique index on
a"name" string field, which is lexicographically ordered.

I'm searching for the range of values of the form "$prefix $integer", i.e.
"foo 1", "foo 99", etc...

to obtain this "range", I initially used (pseudo-code):

auto begin = by_name_index().lower_bound(prefix + " 0");
auto end = by_name_index().upper_bound(prefix + " 9");

and within the range I test the suffix for its number'ness and keep the
largest number.

But I was surprised to see it performed badly for large number of calls.

I switched to using instead:

auto begin = by_name_index().lower_bound(prefix + " 0");
auto end = by_name_index().lower_bound(prefix + " :");

And this performs much better (20x).

The "corpus" of names of this particular test may be skewing the results,
since entries are added to the BMI with monotonically increasing number
suffixes, and all entries have the prefix I'm looking for, yet I'm very
surprised of such a large performance difference between the lower/upper
version, and the lower/lower version.

Anyone has a clue what could be going on? Thanks, --DD

PS: I'm assuming the two versions are equivalent. Let me know if I'm
mistaken please. This is not yet thoroughly tested.