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

view plainprint?

1. int m = a[((L+R)/2).intValue()]  

<br /> int m = a[((L+R)/2).intValue()]<br />
into

view plainprint?

1. int m = a[(L+R) >> 1]  

<br /> int m = a[(L+R) >> 1]<br />

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:

n	100.000	1.000.000
Java	12	95
Scala	12	95
Groovy	3750	41700
Groovy++ (old version)	515	4900
Groovy++ (new version)	19	130

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:

view plainprint?

1. int m = ArraysMethods.getAt(a, DefaultGroovyPPMethods.div(DefaultGroovyPPMethods.box(L + R), DefaultGroovyPPMethods.box(2)).intValue());  

<br /> int m = ArraysMethods.getAt(a, DefaultGroovyPPMethods.div(DefaultGroovyPPMethods.box(L + R), DefaultGroovyPPMethods.box(2)).intValue());<br />
And here is the new version:

view plainprint?

1. int m = ArraysMethods.getAt(a, L + R >> 1);  

<br /> int m = ArraysMethods.getAt(a, L + R >> 1);<br />
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:

n	100.000	1.000.000
Java	11	90
Scala	12	90
Groovy	1900	22000
Groovy++ (new version)	19	130

Groovy++ vs. Groovy vs. Java vs. Scala - Performance Update

I've been writing about a performance comparison between Java, Scala and Groovy in this and this post, where I compared the runtimes of these languages for a straight-forward (and far from idiomatic) implementation of the quicksort algorithm. As you might have heard, there's a new kid on the block: Groovy++ a.k.a. static Groovy. I was eager to see, how this would improve Groovy's results.

So, (without any further justification of this comparison) I took the same source code for Java, Scala and Groovy as previously and took this modified version of the Groovy code for Groovy++:

view plainprint?

1. @Typed  
2. package test  
3.   
4. def swap(int[] a, int i, int j) {  
5.     def temp = a[i]  
6.     a[i] = a[j]  
7.     a[j] = temp  
8. }  
9.   
10. def quicksort(int[] a, int L, int R) {  
11.     int m = a[((L+R)/2).intValue()]  
12.     int i=L  
13.     int j=R  
14.     while (i<=j) {  
15.         while (a[i]<m) i++  
16.         while (a[j]>m) j--  
17.         if (i<=j) {  
18.             swap(a, i, j)  
19.             i++  
20.             j--  
21.         }  
22.     }  
23.     if (L<j) quicksort(a,L,j)  
24.     if (R>i) quicksort(a,i,R)  
25. }  
26. def quicksort(int[] a) {  
27.     quicksort(a, 0, a.length-1)  
28. }  
29.   
30. // Sample data  
31. int[] a = new int[100000]  
32. a.eachWithIndex {int x, int i ->  
33.     a[i] = i*3/2+1  
34.     if (i%3==0) a[i] = -a[i]  
35. }  
36.   
37. int t1 = System.currentTimeMillis()  
38. quicksort(a)  
39. int t2 = System.currentTimeMillis()  
40. println t2-t1   

<br />@Typed<br />package test<br /><br />def swap(int[] a, int i, int j) {<br /> def temp = a[i]<br /> a[i] = a[j]<br /> a[j] = temp<br />}<br /><br />def quicksort(int[] a, int L, int R) {<br /> int m = a[((L+R)/2).intValue()]<br /> int i=L<br /> int j=R<br /> while (i<=j) {<br /> while (a[i]<m) i++<br /> while (a[j]>m) j--<br /> if (i<=j) {<br /> swap(a, i, j)<br /> i++<br /> j--<br /> }<br /> }<br /> if (L<j) quicksort(a,L,j)<br /> if (R>i) quicksort(a,i,R)<br />}<br />def quicksort(int[] a) {<br /> quicksort(a, 0, a.length-1)<br />}<br /><br />// Sample data<br />int[] a = new int[100000]<br />a.eachWithIndex {int x, int i -><br /> a[i] = i*3/2+1<br /> if (i%3==0) a[i] = -a[i]<br />}<br /><br />int t1 = System.currentTimeMillis()<br />quicksort(a)<br />int t2 = System.currentTimeMillis()<br />println t2-t1 <br />
So, I basically took the Groovy code, and added the @Typed annotation and some more type information. I ran this on my machine with Java 1.6.0 Update 17, Scala 2.7.7, Groovy 1.7 and Groovy++ which is based on Groovy 1.8.0-SNAPSHOT. Here are the results (in ms) for sorting 100.000 and 1.000.000 integers:

n	100.000	1.000.000
Java	12	95
Scala	12	95
Groovy	3750	41700
Groovy++	515	4900

Obviously, while still Java and Scala are by far the fastest, Groovy++ makes a huge difference. Groovy takes about 312x the time of Java/Scala, Groovy++ just takes 42x.

While there isn't much difference in the source code of Groovy and Groovy++, there is of course a big difference in the generated byte code. I had a look at it with the Java Decompiler. The Groovy byte code contains lots of dynamic dispatch code, while there's not much in the Groovy++ byte code that indicates that it was compiled from Groovy. Here's a short excerpt:

view plainprint?

1. public Object quicksort(int[] a, int L, int R) {  
2.   while (true) {  
3.     int m = ArraysMethods.getAt(a, DefaultGroovyPPMethods.div(DefaultGroovyPPMethods.box(L + R), DefaultGroovyPPMethods.box(2)).intValue());  
4.     int i = L;  
5.     int j = R;  
6.     while (i <= j) {  
7.       for (; ArraysMethods.getAt(a, i) < m; (i++));  
8.       for (; ArraysMethods.getAt(a, j) > m; (j--));  
9.       if (i <= j) {  
10.         swap(a, i, j);  
11.         (i++);  
12.         (j--);  
13.       }  
14.     }  
15.     if (L < j) quicksort(a, L, j);  
16.     if (R <= i) break; R = R; L = i; a = a; this = this; } return null;  
17. }  

  public Object quicksort(int[] a, int L, int R) {
    while (true) {
      int m = ArraysMethods.getAt(a, DefaultGroovyPPMethods.div(DefaultGroovyPPMethods.box(L + R), DefaultGroovyPPMethods.box(2)).intValue());
      int i = L;
      int j = R;
      while (i <= j) {
        for (; ArraysMethods.getAt(a, i) < m; (i++));
        for (; ArraysMethods.getAt(a, j) > m; (j--));
        if (i <= j) {
          swap(a, i, j);
          (i++);
          (j--);
        }
      }
      if (L < j) quicksort(a, L, j);
      if (R <= i) break; R = R; L = i; a = a; this = this; } return null;
  }

This isn't even far from the byte code generated by java. There is just that autoboxing of integers, integer division and the array access with getAt(). Considering the early state of Groovy++ this looks very promising.

Update: There's is a follow-up post that shows how to tune the Groovy++ code to make it run as fast as Java and Scala (Thanks to ait, see comments).