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

[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

[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

[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 #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

[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 #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

[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

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

[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

[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

[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

[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