Hunting for performance regressions in libstdc++

[Howard Hinnant]

On Jun 17, 2005, at 11:30 AM, Paolo Carlini wrote:

> For instance, the first one, case ignore hint if
> wrong (suppose, for clarity of explanation on my part that p != begin 
> &&
> p != end) would be:
>
>     if (x < *p && x > *(p - 1))
>        insert x before p
>     else
>        insert x without hint

Consider the sequence:

a b b c

and assume we are inserting another b with hint p pointing to the 2nd b:

a b b c
     ^
     |
     p
     -
     b

In this case, the hint is not wrong and so the new b should be inserted 
between the two existing b's:

a b b b c
     ^
     |
    new

However in your altered algorithm the first test "x < *p" will evaluate 
to false (b < b is false), and so the "insert x without hint" branch 
will be taken instead of the desired "insert x before p".

However if we instead said:

     if (x <= *p && x >= *(p - 1))
        insert x before p
     else
        insert x without hint

The first test is: b <= b which is true.
The second test is b >= b which is also true.

The "insert x before p" branch will be taken as desired.

Do you have a counter example where the use of "<=" and ">=" do not 
work as desired?

-Howard