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: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2013-11-22 15:21:14

Dominique Devienne <ddevienne <at> gmail.com> writes:

> 
> On Thu, Nov 21, 2013 at 5:38 PM, Joaquin M Lopez Munoz <joaquin <at>
tid.es> 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.
>
> [...]
> 
> 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).

OK, this gives extra info: I thought you were using a custom comparator
to test for prefix-equality --now I see you aren't, but instead you
just rely on plain regular string comparison.

So,consider

  typedef multi_index_container<
    std::string,
    indexed_by<
      ordered_non_unique<identity<std::string>>
    > 
  > multi_t;

  multi_t c={
    "a 0","a 000","a 1","a 9","a 90","a :"
  }; 

The following

  auto first=c.lower_bound("a 0");
  auto last=c.upper_bound("a 9");
  while(first!=last)std::cout<<*first++<<", ";
  
produces the output

  a 0, a 000, a 1, a 9

while this

  auto first=c.lower_bound("a 0");
  auto last=c.lower_bound("a :");
  while(first!=last)std::cout<<*first++<<", ";

produces

  a 0, a 000, a 1, a 9, a 90,

See the difference? Is this related to your problem?

Joaquín M López Muñoz
Telefónica Digital