[Bug c++/38986] New: comparing lengths of 2 strings reads through both strings completely

[Bug c++/38986] New: comparing lengths of 2 strings reads through both strings completely

[esigra at gmail dot com]

Suppose that someone wants to see if a string is shorter than another and
writes:
   #include <string.h>
   bool f(char const * const a, char const * const b) {return strlen(a) <=
strlen(b);}

Then g++ generates this:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        subl    $4, %esp
        movl    8(%ebp), %eax
        movl    %eax, (%esp)
        call    strlen
        movl    %eax, %ebx
        movl    12(%ebp), %eax
        movl    %eax, (%esp)
        call    strlen
        cmpl    %eax, %ebx
        setbe   %al
        addl    $4, %esp
        popl    %ebx
        popl    %ebp
        ret

But it looks like this code reads through both strings completely! This is
obviously very efficient if one of the strings is much longer than the other.
It should of course only read as far into each string as the shortest of them
is long. The generated code should be similar to what this would give:
bool g(char const * a, char const * b) {
   for (;; ++a, ++b)
      if      (not *a)
         return true;
      else if (not *b)
         return false;
}


-- 
           Summary: comparing lengths of 2 strings reads through both
                    strings completely
           Product: gcc
           Version: 4.3.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: esigra at gmail dot com


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

[Bug c++/38986] comparing lengths of 2 strings reads through both strings completely

[bangerth at gmail dot com]

------- Comment #1 from bangerth at gmail dot com  2009-01-30 15:13 -------
Yes, I think this would be an optimizing compiler could potentially perform.
At the same time I think you are expecting too much from the compiler: it
would have to have a semantic understanding of what the strlen function
does and that the result can be obtained by merging the two calls to strlen,
then merging the two loops, and then truncating them.

I don't think that this sort of analysis is going to be available in compilers
anytime soon. Since you already have the solution, maybe this is the way to
go!

Best
 W.


-- 

bangerth at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bangerth at gmail dot com
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |WONTFIX


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

[Bug c++/38986] comparing lengths of 2 strings reads through both strings completely

[esigra at gmail dot com]

------- Comment #2 from esigra at gmail dot com  2009-01-30 16:12 -------
GCC already understands the semantics of strlen. If one of the operands to "<"
is a constant and the other is strlen, it is optimized (such as "strlen(str) >=
1). It just seems like the case with strlen on both sides is missing.


-- 


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

[Bug c++/38986] comparing lengths of 2 strings reads through both strings completely

[falk at debian dot org]

------- Comment #3 from falk at debian dot org  2009-02-01 10:50 -------
The main problem is that just replacing the code by the below loop won't
necessarily give a speedup. strlen is usually implemented in highly efficient
and platform-specific assembly that treats several bytes at a time. I don't
think the vectorizer will give equally efficient code for the loop. Also, in
normal applications almost all strings are pretty short (and not of very
unequal length). Probably the best way to motivate somebody to look into this
is if you gave benchmark results that show a noticeable improvement for some
real-world application.


-- 


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