Re: Hunting for performance regressions in libstdc++

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

On Jun 17, 2005, at 12:20 PM, Paolo Carlini wrote:

> Paolo Carlini wrote:
>
> > Thanks for the explanation. Indeed, now I understand: unconsciously I
> > was considering the map/set case, *not* the multimap/multiset case. 
> > Only
> > in latter case you see clearly the difference and your pseudocode is 
> > ok
> > for *both*.
> Well, not completely. I mean, my mistake ultimately is that your
> discussion is focused on multimap/multiset, whereas we (libstdc++-v3)
> have to improve our code wrt before/after also in case of map/set...

Sure.  And in the unique key containers, you are right that "<" and ">" 
are more appropriate.  The pseudo code we were looking at came from a 
section describing the efficiency related to the "as close to the hint 
as possible" rule.  That same section also states:

> Note: The "as close as possible to hint" rule has no effect on the 
> algorithms used to insert into containers with unique keys. When x 
> does not yet exist in a container, lower_bound, upper_bound and 
> "insert without hint" all refer to the same location. And when x does 
> already exist in a unique-key container, no insertion is performed.

Of course for consistency, we would like the before/after complexity 
behavior to be the same for unique key containers as the non-unique key 
containers.  For the unique-key containers, the current proposed 
resolution to lwg 233 (adjacent) would work fine.  This would require 
both a before check and an after check, and the order of the checks 
wouldn't matter.  Only when dealing with non-unique key containers does 
the current "adjacent" wording of lwg 233 leave clients with 
insufficient control.

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.

-Howard