[Bug libgcj/23495] New: java.lang.String.equals is suboptimal

[Bug libgcj/23495] New: java.lang.String.equals is suboptimal

[greenrd at greenrd dot org]

I can see a way to improve the speed of java.lang.String.equals. On x86,
sizeof(void *) is 2*sizeof(jchar), whilst on x86_64, sizeof (void *) is
4*sizeof(jchar). So it should be more efficient to compare as many elements as
possible in batches of 2 (on e.g. x86) or 4 (on e.g. x86_64), by casting the
arrays to void **. (If length % 2 != 0, it is not possible to compare all the
elements in this way, of course, but all but the last can be.)

My LD_PRELOAD tests show performance improvements of up to 49% for comparing two
equal 10-character strings with this change, and up to 91% for comparing two
equal 110-character strings. There is no significant degradation for the common
case where the two strings differ in the first character, nor for the case of
very small equal strings. These results were obtained on x86 with -O2 -g
-march=athlon-xp (without -march=athlon-xp the improvements are smaller). I
would expect the improvements to be even better on x86_64, because it can
compare 4 jchars at a time.

I haven't investigated alignment issues, however. It's possible that this change
will not be faster for all arches, in which case it could be maybe #ifdef'd.

-- 
           Summary: java.lang.String.equals is suboptimal
           Product: gcc
           Version: 4.0.2
            Status: UNCONFIRMED
          Severity: minor
          Priority: P2
         Component: libgcj
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: greenrd at greenrd dot org
                CC: gcc-bugs at gcc dot gnu dot org,java-prs at gcc dot gnu
                    dot org


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[greenrd at greenrd dot org]

------- Additional Comments From greenrd at greenrd dot org  2005-08-20 16:29 -------
Created an attachment (id=9549)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=9549&action=view)
Benchmark

This is the equality benchmark I used. Uncomment the //ca [0] = 'b'; line and
negate the assertion to convert it into an inequality benchmark.

-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-20 19:10 -------
Hmm, doing a profiling, I noticed that equals does its own loop instead of using memcmp which is 
most likely more efficient as memcmp is optimized for each target by the OS.

-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-20 19:41 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-08-20 19:41:09
               date|                            |


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[tromey at gcc dot gnu dot org]

------- Additional Comments From tromey at gcc dot gnu dot org  2005-08-22 21:54 -------
Robin, could you do another test where you use memcmp instead of
a hand-written loop?


-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[greenrd at greenrd dot org]

------- Additional Comments From greenrd at greenrd dot org  2005-08-28 23:25 -------
memcmp (which is compiled for i686 in fedora because it is part of glibc) is
actually less efficient than the current code on my athlon! I was so surprised,
I ran the memcmp benchmark again, and the results differed by no more than +/-2%.

Here are the wallclock times in ms, followed by the advantage of block compare
over the current code. n is the length of the strings tested.

n   | Current | block compare | memcmp | Advantage of block compare
-------------------------------------------------------------------
10  | 10717   | 9236          | 11957  | 16%
30  | 16427   | 14618         | 19884  | 12%
50  | 22181   | 17539         | 27550  | 26%
70  | 28052   | 20978         | 35243  | 34%
90  | 32966   | 24695         | 42815  | 33%
110 | 42975   | 28453         | 55036  | 51%

All these tests were done on x86 with the same -O, -g and -f flags as make
bootstrap uses by default, using LD_PRELOAD to "hot-replace" the code, and
without the assertion enabled in the benchmark.

The advantage of block compare rises to 54% for n=10 and 81% for n=110 if
-march=athlon-xp is used (to compile both the original code and my block compare
code).

-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[pinskia at physics dot uc dot edu]

------- Additional Comments From pinskia at physics dot uc dot edu  2005-08-28 23:32 -------
Subject: Re:  java.lang.String.equals is suboptimal


On Aug 28, 2005, at 7:25 PM, greenrd at greenrd dot org wrote:

>
> ------- Additional Comments From greenrd at greenrd dot org  
> 2005-08-28 23:25 -------
> memcmp (which is compiled for i686 in fedora because it is part of 
> glibc) is
> actually less efficient than the current code on my athlon! I was so 
> surprised,
> I ran the memcmp benchmark again, and the results differed by no more 
> than +/-2%.
>
> Here are the wallclock times in ms, followed by the advantage of block 
> compare
> over the current code. n is the length of the strings tested.
>
> n   | Current | block compare | memcmp | Advantage of block compare
> -------------------------------------------------------------------
> 10  | 10717   | 9236          | 11957  | 16%
> 30  | 16427   | 14618         | 19884  | 12%
> 50  | 22181   | 17539         | 27550  | 26%
> 70  | 28052   | 20978         | 35243  | 34%
> 90  | 32966   | 24695         | 42815  | 33%
> 110 | 42975   | 28453         | 55036  | 51%
>
> All these tests were done on x86 with the same -O, -g and -f flags as 
> make
> bootstrap uses by default, using LD_PRELOAD to "hot-replace" the code, 
> and
> without the assertion enabled in the benchmark.

This seems like something glibc's memcmp should be doing also, could
you report a bug to glibc about this comparison?  Also glibc's memcmp
could be improved by doing 128 byte (SSE2 and altivec) comparison
at a time so we get a nice speed up there too.

-- Pinski



-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[greenrd at greenrd dot org]

------- Additional Comments From greenrd at greenrd dot org  2005-08-30 01:17 -------
(In reply to comment #7)
> This seems like something glibc's memcmp should be doing also, could
> you report a bug to glibc about this comparison?

Actually I was wrong - it's not glibc's memcmp that's being used here, it's the
gcc inlined memcmp (see http://sources.redhat.com/bugzilla/show_bug.cgi?id=1262
), which uses the "CISC-style" instructions REP MOVSB. This performs badly in
_every_ case on athlon-xp compared to a "RISC-style" loop. (Indeed this is
documented - it's surprising that gcc has been using the wrong substitution for
so long!) So I will submit a more conservative bug about changing the inlined
memcmp into a loop, against gcc. And will test it on pentium 4 as well.

The block-compare is harder to argue for at the gcc level because it is quite
complicated for the case of memcmp on big-endian (see the glibc implementation)
and therefore probably isn't a good case for inlining, at least not on x86.

However, the block-compare makes perfect sense for the simpler case of
java.lang.String.equals, as my results show.

-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[tromey at gcc dot gnu dot org]

------- Comment #14 from tromey at gcc dot gnu dot org  2006-03-10 00:48 -------
I checked in a patch using memcpy and memcmp.
This didn't yield as dramatic a speedup for me, but did do ok.


-- 

tromey at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.2.0


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[tromey at gcc dot gnu dot org]

------- Comment #13 from tromey at gcc dot gnu dot org  2006-03-10 00:39 -------
Subject: Bug 23495

Author: tromey
Date: Fri Mar 10 00:39:49 2006
New Revision: 111919

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=111919
Log:
        PR libgcj/23495:
        * java/lang/natString.cc (_Jv_NewString): Use memcpy.
        (equals): Use memcmp.
        (contentEquals): Likewise.
        (getChars): Use memcpy.
        (toCharArray): Likewise.
        (regionMatches): Use memcmp.
        (regionMatches): Likewise.
        (startsWith): Likewise.
        (concat): Use memcpy.
        (valueOf): Likewise.

Modified:
    trunk/libjava/ChangeLog
    trunk/libjava/java/lang/natString.cc


-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[tromey at gcc dot gnu dot org]

------- Comment #12 from tromey at gcc dot gnu dot org  2006-03-09 19:17 -------
Fair enough.  I'm handling this.


-- 

tromey at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |tromey at gcc dot gnu dot
                   |dot org                     |org
             Status|WAITING                     |ASSIGNED
   Last reconfirmed|2005-08-20 19:41:09         |2006-03-09 19:17:54
               date|                            |


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[greenrd at gcc dot gnu dot org]

------- Comment #11 from greenrd at gcc dot gnu dot org  2006-03-08 14:39 -------
Sorry, I can't submit patches to libjava because I'm tainted (except for the
packages that are new in Mustang, which I haven't seen). Even though this is a
small change, I prefer to err on the side of caution.


-- 


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[tromey at gcc dot gnu dot org]

------- Comment #10 from tromey at gcc dot gnu dot org  2006-03-08 00:54 -------
Actually, Robin, could you send your current patch for this?
It seems like we should simply put it in.


-- 

tromey at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING


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

[Bug libgcj/23495] java.lang.String.equals is suboptimal

[tromey at gcc dot gnu dot org]

------- Comment #9 from tromey at gcc dot gnu dot org  2006-02-06 22:12 -------
This seems to have stalled.

I think my preferred solution here would be to use memcmp and
let gcc and glibc fight it out for the best implementation.
How far are we from having that be a reasonable approach?


-- 

tromey at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tromey at gcc dot gnu dot
                   |                            |org


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