[Patch] libstdc++/22102 (Re: Hunting for performance...)

[Paolo Carlini]

Hi Howard,

and thanks again for your extremely helpful feedback.

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

Indeed, this is what you find in current GCC.

> 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).

Agreed.

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

Agreed, again.

> 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.

Ok. Fine. Then the below probably would be an improvement wrt the
current GCC situation. If nobody (myseld included ;) finds major flaws
in it during the next days, I'd like to have it in mainline first, and
then in 4_0-branch too, since it fixes a (performance) regression (in
some cases). Then, for mainline only, I'd like to also implement in
RB-tree code the additional insert at the lower bound, for the full
glory of Howard, LWG, and, well, GCC! ;)

(already passes tests on x86-linux)

Paolo.

//////////////////
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CL_22102
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20050617/7a085fa1/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch_22102
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20050617/7a085fa1/attachment-0001.ksh>