ReRe: performance - some details (and shellsort)

[Jeff Sturm]

Norman Hendrich wrote:
> Yes, I do know the effect of the -ms parameter. However, it doesn't have
> much effect for the ShellSort demo. Most cpu time is spend in the
> shellsort() algorithm, not in the object allocation.  Naturally, I had
> to use -mx48M for the ShellSort 1000000 demo, all others were run with
> the 16 MB default.

Hmm... ok, the object allocation is small but not really negligible.  I
added some separate timings to your code and ran it with both the IBM
JDK and gcj-2.95.  Just for kicks I also tried --no-bounds-check:


[jsturm@toronto Hendrich]$ javac -O ShellSort.java
[jsturm@toronto Hendrich]$ java -mx64m ShellSort 1000000
Shellsort self test started...
...generating random numbers... done (13163 ms elapsed)
...sorting... done (83918 ms elapsed)
...checking... done (578 ms elapsed)
ok.
[jsturm@toronto Hendrich]$ gcj -O3 ShellSort.java
    --main=ShellSort -o shellsort
[jsturm@toronto Hendrich]$ ./shellsort 1000000
Shellsort self test started...
...generating random numbers... done (8997 ms elapsed)
...sorting... done (64058 ms elapsed)
...checking... done (1180 ms elapsed)
ok.
[jsturm@toronto Hendrich]$ gcj --no-bounds-check -O3 ShellSort.java
    --main=ShellSort -o shellsort
[jsturm@toronto Hendrich]$ ./shellsort 1000000
Shellsort self test started...
...generating random numbers... done (9037 ms elapsed)
...sorting... done (58656 ms elapsed)
...checking... done (1088 ms elapsed)
ok.


Next I modified ShellSort to be a legal C program, and ran it again...
it finished in under 12 seconds.  Darn.  What's so inefficient about the
Java code?  Array handling?

I think I figured it out... I removed the calls to _Jv_CheckArrayStore
from ShellSort.s and ran again:


[jsturm@toronto Hendrich]$ ./shellsort 1000000
Shellsort self test started...
...generating random numbers... done (8996 ms elapsed)
...sorting... done (16981 ms elapsed)
...checking... done (1041 ms elapsed)
ok.


That's more like it!  I wonder if this call could somehow be optimized
away, if the compiler is smart enough to know that it is reassigning
values from the same array... hmm... I wonder what happens if I replace
"Object" with "Double" in the source and compile/run again:


[jsturm@toronto Hendrich]$ gcj --no-bounds-check -O3
    ShellSort.java --main=ShellSort -o shellsort
[jsturm@toronto Hendrich]$ ./shellsort 1000000
Shellsort self test started...
...generating random numbers... done (9313 ms elapsed)
...sorting... done (16245 ms elapsed)
...checking... done (681 ms elapsed)
ok.


That's it.  If we help the compiler a little it can optimize away the
the call to _Jv_CheckArrayStore().

It looks like the IBM JIT didn't benefit from this modification...
sheesh... you'd think a JIT would be smarter than that.  Oh well, now we
have a test program that'll demonstrate a five-fold improvement over the
JDK ;)

Well that was fun...


> The JDK probably didn't GC, because the shellsort demo allocates all
> arrays at program start and doesn't request objects afterwards.
> I don't know about gcj.

The JDK might GC in places you don't expect.  For instance, when running
out of heap, it attempts to GC to reclaim/compact memory before it
expands the heap.  Starting with a large heap avoids that overhead.


-- 
Jeff Sturm
jsturm@sigma6.com