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

Subject: Re: [Boost-users] [Multi-Index] performance difference between lower_bound() and upper_bound()
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2013-11-22 04:03:57

On Thu, Nov 21, 2013 at 5:38 PM, Joaquin M Lopez Munoz <joaquin_at_[hidden]>wrote:

> Dominique Devienne <ddevienne <at> gmail.com> writes:
> > [...] 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");
> >
> > [...] 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).
>
> There is no reason why it should, if both ops are returning the
> same range. Could you please show the custom comparison predicate you're
> using? This might shed some light on the issue.
>

Thanks Joaquín.

Unfortunately, it's not easy to share the actual BMI definition, which uses
intermediary templates for the index definitions (for reuse in other BMIs),
a custom extractor of the name to work-around VC "thunk" warnings (since
name() is a pure virtual method), and the string-type is a legacy custom
one.

I do not specify a custom comparison predicate to the BMI for name(), so it
relies on std::less and calls the custom op< of our string type, which
calls strncmp after some null checks. So it's a strict "ascii"
lexicographical order, no locale used, and I'm confident it's ordering
things correctly (it's been in place for months/years).

Thanks for confirming it should not matter. I'll try with different sets of
names in the index (the one I'm using now is very special), and I will
confirm the same ranges are returned. --DD