[Bug libstdc++/44413] New: inefficient code for std::string::compare on x86-64

[Bug libstdc++/44413] New: inefficient code for std::string::compare on x86-64

[dgohman at gmail dot com]

This code:

#include <string>
int foo(const std::string &a, const std::string &b) { return a.compare(b); }

compiles to code like this on x86-64:
[...]
        subq    %rdx, %r8
        movl    $2147483647, %eax
        cmpq    $2147483647, %r8
        jg      .L2
        movl    $-2147483648, %eax
        cmpq    $-2147483648, %r8
        cmovge  %r8d, %eax
.L2:
[...]

Since compare need only return a value greater, less, or equal to zero, the
code in _S_compare would be more efficient as simple code that just returns -1,
0, or 1 on most targets where difference_type is wider than int.


-- 
           Summary: inefficient code for std::string::compare on x86-64
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dgohman at gmail dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[redi at gcc dot gnu dot org]

------- Comment #1 from redi at gcc dot gnu dot org  2010-06-04 16:52 -------
Seems like a reasonable suggestion for improvement. I don't know if anyone
relies on the current behaviour, so it might not get changed.


-- 

redi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2010-06-04 16:52:15
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo dot carlini at oracle dot com]

------- Comment #2 from paolo dot carlini at oracle dot com  2010-06-07 14:52 -------
I think Jon is right on both accounts: the request is reasonable, but, even
before that last changes, thus since the very beginning of v3:

        if (!__r)
          __r =  __size - __osize;

thus, I think we want something that while efficient preserves this behavior
(without overflowing). I'm not sure we can do much better, given the
constraints...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[dgohman at gmail dot com]

------- Comment #3 from dgohman at gmail dot com  2010-06-08 14:54 -------
Callers of compare are already exposed to __builtin_memcmp result values (with
default traits) which vary depending on the target and compiler flags.

And since _S_compare is only used as a tie-breaker after the memcmp, it's hard
to imagine any code innocently relying on it returning a particular value.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo dot carlini at oracle dot com]

------- Comment #4 from paolo dot carlini at oracle dot com  2010-06-08 15:09 -------
I'm not convinced. The code at issue is used when memcmp returns zero, thus one
string is a prefix of the other, a well defined situation. For *eons* we have
been returning a number which is much larger (in modulo) if one string is much
longer. Before considering changing this, I want to see a very solid real life
example, with numbers, of code benefiting from this tuning. Otherwise, I guess
we'll do it, but only when we'll break the ABI.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo dot carlini at oracle dot com]

------- Comment #5 from paolo dot carlini at oracle dot com  2010-06-08 15:59 -------
Let's do this change first in ext/vstring and let's see how people react. In
that case we also have the advantage that nothing is exported from the *.so,
thus old code linking to the new lib will not risk behaving differently all of
a sudden.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo at gcc dot gnu dot org]

------- Comment #6 from paolo at gcc dot gnu dot org  2010-06-09 09:16 -------
Subject: Bug 44413

Author: paolo
Date: Wed Jun  9 09:15:51 2010
New Revision: 160456

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160456
Log:
2010-06-09  Paolo Carlini  <paolo.carlini@oracle.com>

        PR libstdc++/44413
        * include/ext/vstring_util.h (__vstring_utility<>::_S_compare):
        Simplify, just return -1, 0, 1.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/ext/vstring_util.h


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo at gcc dot gnu dot org]

------- Comment #7 from paolo at gcc dot gnu dot org  2010-06-09 14:02 -------
Subject: Bug 44413

Author: paolo
Date: Wed Jun  9 14:02:03 2010
New Revision: 160476

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160476
Log:
2010-06-09  Paolo Carlini  <paolo.carlini@oracle.com>

        Revert:    
        2010-06-09  Paolo Carlini  <paolo.carlini@oracle.com>

        PR libstdc++/44413
        * include/ext/vstring_util.h (__vstring_utility<>::_S_compare):
        Simplify, just return -1, 0, 1.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/ext/vstring_util.h


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo dot carlini at oracle dot com]

------- Comment #8 from paolo dot carlini at oracle dot com  2010-06-09 15:13 -------
I gave this more thought, and to be honest, focusing on 64-bit targets - I
think that for 32-bit targets what we have is already good enough - I have no
idea how to substantively improve the code, given that the length of a string
is a 64-bit unsigned and the return type must be an int. Jon?


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jwakely dot gcc at gmail dot
                   |                            |com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413

[Bug libstdc++/44413] inefficient code for std::string::compare on x86-64

[paolo dot carlini at oracle dot com]

------- Comment #9 from paolo dot carlini at oracle dot com  2010-06-10 00:26 -------
As far as we can see can't be substantively improved. See also the thread
starting at: http://gcc.gnu.org/ml/libstdc++/2010-06/msg00073.html


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44413