Re: Hunting for performance regressions in libstdc++

[Howard Hinnant <hinnant at twcny dot rr dot com>]

On Jun 17, 2005, at 2:30 PM, Paolo Carlini wrote:

> Howard Hinnant wrote:
>
> > [snip]
> >
> > Note that the behavior of "adjacent" semantics is allowed but not
> > required by the proposed wording in N1780.  This allows a nice
> > migration path from "after" semantics.  You can implement "before"
> > semantics today but still check "after" and remain backwards
> > compatible indefinitely.
>
> Ok, I think my only remaining doubt is the following (don't know if you
> want to help to clarify this point, not really part of DR 233 ;) 
> AFAICS,
> in case of map/set things seem less efficient, the worst case being *3*
> comparisons. That is, x < *p, then, if it fails, *p < x and x < *(p +
> 1). Or?!?

The current standard has "after" semantics which costs 2 comparisons 
assuming a good hint.

The current resolution to lwg 233:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#233

proposes "adjacent" semantics which would cost 2 to 3 comparisons 
assuming a good hint (i.e. you must check before and after).

N1780 proposes "before" semantics which would cost 2 comparisons 
assuming a good hint.

With either "before" or "after" semantics, the vendor is free to spend 
1 more comparison to implement "adjacent" semantics.  This may or may 
not be more expensive for the client.  That 1 more comparison might 
save an additional Log N comparisons (or it might not).  It is a 
gamble.  The current resolution to lwg 233 mandates that gamble.

-Howard