Sunday, February 7, 2010

Groovy++ Performance - Now we're talkin'

This is a follow-up of my last post, where I compared the runtimes of the quicksort algorithm implemented in Java, Scala, Groovy and Groovy++. Groovy++ came up with a significant improvement over Groovy. But there was a comment by ait (Thanks ait) on how to improve the performance of the Groovy++ implementation even further, by changing a single line. In fact, this improved the performance dramatically.

In the previous post I showed the de-compiled byte code of the Groovy++ implementation of the algorithm. There were two things that were different from the Java byte code: array access via ArraysMethods.getAt(index) and the integer boxing und calculation. Ait recommended to change the following line

into


Obviously, this tackles the integer handling problem. After changing this line I ran the code again and had a look at the timings. The results are amazing. Here they are for sorting 100.000 and 1.000.000 integers:

n100.0001.000.000
Java1295
Scala1295
Groovy375041700
Groovy++ (old version)5154900
Groovy++ (new version)19130


This is marvellous! Now Groovy++ is really on a par with Java and Scala!


De-compiling the byte code again shows the difference. Here's the old byte code:

And here is the new version:

Still, there is no native array access, but the integer boxing is gone, it's primitive integer calculations.

Ait (Is that you, Alex?) will come up with a post with more details. I'll provide a link here then.


Update: These are the numbers for Java, Scala and Groovy with shifting instead of division. Only Groovy can take advantage of this:
n100.0001.000.000
Java1190
Scala1290
Groovy190022000
Groovy++ (new version)19130






19 comments:

marvotron said...

what about the groovy version with that change? :)

Roy Mustang said...

I'm think g++rails.

Who's with me?

Francois Hensley said...

Even the normal groovy version shows significant improvements. On local machine

Before Changes : 1193
After Changes : 449

The times do fluctuate somewhat, but the increase is still significant.

Nick Wiedenbrueck said...

@marvotron: The Groovy version for Groovy++ was 1.8.0-beta-1-SNAPSHOT.

dhukas said...

you should also change this line in java, scala and groovy an post the results again - if this all should make sense at all...

marvotron said...

i didnt mean what version of groovy i meant what francois did and dhukas said.

what are the timings if they all do a left shift?

Nick Wiedenbrueck said...

Added results for Java, Scala and Groovy with shifting instead of division.

chubbard said...

That's very encouraging that this optimization made that much of an improvement, but that means general purpose division is waaaaaay to slow in Groovy++ and Groovy. It's an old technique to use bit shifting to improve dividing by a power of 2 to approximate integer division. However, that's a minor improvement as noted by the relatively small change in Java and Scala when switching between division -> shifting. Which means division in Java and Scala are much more efficient than in Groovy variants. Is there any hope to improving Groovy's implementation of division to improve general purpose performance?

Nick Wiedenbrueck said...

@chubbard I was thinking about that, too. Maybe this could go well into the compiler.

jlorenzen said...
This comment has been removed by the author.
jlorenzen said...

I'm liking what I am seeing from groovy++. Wish it would automatically detect it instead of having to annotate it. Does this just point out the significant performance issues with #groovy? Wonder what the #grails community thinks of this? Wonder how bad this was prior to groovy version 1.6.x which is when they implemented huge performance improvements? Wonder if this would improve once jdk1 .7 invokedynamic becomes available for the JVM dynamic languages?

Nick Wiedenbrueck said...

Actually I did run the same test before Groovy 1.6, see previous post. It didn't make a significant change.

Christopher Wong said...

The reason why that division operation is so slow is that Groovy defaults to non-integral division. The result is a BigDecimal. I believe Groovy defaults to something that is more friendly (mathematically speaking) at the expense of performance.

If you only want integral division, you should use the intdiv() method. That is, instead of

(L+R)/2

You really want

(L+R).intdiv(2)

This is more general than the left shift operator.

Nick Wiedenbrueck said...

@Christopher: Oh yeah, thanks. I missed that. I will check out the performance ...

Nick Wiedenbrueck said...

Now I've got the numbers for /, intdiv() and >> for 100.000 integers with Groovy++:

/: 500ms
intdiv(): 32ms
>> 15ms

and for 1.000.000 integers:

/: 4900ms
intdiv(): 249ms
>>: 130ms

ochronus said...

It's nice to see JVM based language implementations rise! While I'm more a ruby guy, groovy is also very nice and also it can be used along with jruby if needed.

Anonymous said...

I'm glad that some people care about these metrics... but most of us Grails devs make CRUD apps where we don't really write heavy math and loops like this much.
Great for under-the-hood plugin s where power is needed, though!

Umran said...

Hi,
Nice article.

Any idea how i can dynamically load a Groovy++ source class file in java and execute a certain method in it?

Here's a sample code of loading a groovy source file (HelloWorld.groovy) and executing the run method:


ClassLoader parent = getClass().getClassLoader();
GroovyClassLoader loader = new GroovyClassLoader(parent);
Class groovyClass = loader.parseClass(new File("src/test/groovy/script/HelloWorld.groovy"));

// let's call some method on an instance
GroovyObject groovyObject = (GroovyObject) groovyClass.newInstance();
Object[] args = {};
groovyObject.invokeMethod("run", args);


I got the code from:
http://groovy.codehaus.org/Embedding+Groovy

Thanks.

keyzero said...

I went through a similar thought process to solve a Project Euler problem using plain Groovy! You can read about my attempts here - KeyZero Solution 14