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
<br /> int m = a[((L+R)/2).intValue()]<br />
into
<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:
<br /> int m = ArraysMethods.getAt(a, DefaultGroovyPPMethods.div(DefaultGroovyPPMethods.box(L + R), DefaultGroovyPPMethods.box(2)).intValue());<br />
And here is the new version:
<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++:

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

  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).

GroovyBot - Developing a Groovy Google Wave Robot

Google Wave is a communication and collaboration tool developed by Google, which is currently in preview and available only to a limited number of users. Last week, I was chosen to be one of those users, and as there's also a Java API available to extend the platform, the first thing that came to my mind was to build a Groovy robot.

This post gives a short introduction of how to build a Google Wave robot. The goal is to build a robot that takes user input as a Groovy script, evaluates it and displays the result back in the wave. To avoid any misunderstanding, the robot itself is not written in Groovy but in Java (shame on me ;-) and uses GroovyShell to evaluate Groovy code. For the impatient (with a Google Wave account) who want try the robot, it's address is groovybot@appspot.com. See the resources section for source code.

Introduction to Google Wave
Google Wave is a communication and collaboration platform, where people can participate in conversations. It's kind of like an e-mail conversation but in real-time like a chat, and much more interactive, with much more features. A conversation, consisting of one or more participants, is called a wave. A wave is a container for wavelets, which are threaded conversations, spawned from a wave. Wavelets are a container for messages, called blips. For more details, see the Google Wave documentation.

Google Wave Extensions
There are two types of Google Wave extensions - gadgets and robots. A gadget basically is a component containing some HTML and JavaScript, that can be included in a wave conversation. But as GroovyBot currently does not make use of gadgets (yet), I won't consider gadgets any further in this post. The other type of wave extension is robots, and as the name suggests, GroovyBot is of this type of extension. A robot is a certain kind of web application that can participate in a wave conversation just as a human participant. And just as a human participant, it can be added to a conversation and then react to certain kinds of events in the wave, e.g. when it's added to the wave or somebody submitted a message (a blip). In response, it can then modifiy the content of the conversation, e.g. by appending content or replacing content.

Getting Started
Currently robots have to be deployed to the Google App Engine. Fortunately, it's really easy to get started with Google App Engine. First you'll need to sign up for an accout. Then with the Eclipse plugin for the app engine create an application, just like shown in this post. This will create a simple Servlet web application, which can immediately be deployed on app engine. But we don't want a simple servlet application. Let's see how to build a wave robot.

Building a Robot
First of all, we need the Google Wave Java Client API, which consists of four jar files, and (for this particular robot) the Groovy jar groovy-all-1.6.5.jar. Place these in the war/lib directory and add them to the build path of your Eclipse project. Then we create the robot, which is simply a class extending AbstractRobotServlet. We'll name it GroovyBotServlet:

public class GroovyBotServlet 
        extends AbstractRobotServlet {

   @Override
   public void processEvents(
        RobotMessageBundle bundle) {
     // TODO
   }

}

As said, a robot is basically a wave participant, which can react to certain events happening in the wave conversation. The event handling is done in the processEvents method. All information about the event and the context in which the event ocured, like the wavelet, the blip, the participants and so on, is contained in the RobotMessageBundle parameter. The robot servlet has to be mapped to the URL path /_wave/robot/jsonrpc in the web.xml.

The first thing we'd like to do is to show a simple message in the wave, when the robot is added as a participant. The wave API provides a convenience method called wasSelfAdded to check for this particular event:

public void processEvents(RobotMessageBundle bundle) {

  if (bundle.wasSelfAdded()) {
    final Blip blip = bundle.getWavelet().appendBlip();
    final TextView textView = blip.getDocument();
    textView.append("GroovyBot added!");
  }

}

So, if the robot was just added to the wave, we get the wavelet in which the event occured, append a blip to it and add the message to the blip's document. The result looks like this:


This was easy, and to make the robot run a Groovy script and display the result back in the wave is not much harder.

Executing Groovy Scripts
GroovyBot should not execute all messages submitted to the wave as a Groovy script. Instead, if the user wants the content of a blip to be executed as a script, the blip has to start with the prefix '!groovy' followed by the code, e.g.


The event we want to react to is a BLIP_SUBMITTED event. We have to tell wave that our robot is interested in events of this type by specifying this in the file war/_wave/capabilities.xml:

<?xml version="1.0" encoding="utf-8"?>
<w:robot xmlns:w="http://wave.google.com/extensions/robots/1.0">
<w:capabilities>
 <w:capability name="BLIP_SUBMITTED" content="true" />
</w:capabilities>
<w:version>0.1</w:version>
</w:robot>

Then we modify the processEvents method to handle these events:

public void processEvents(
            final RobotMessageBundle bundle) {

for (final Event e : bundle.getEvents()) {

  if (e.getType() == EventType.BLIP_SUBMITTED) {
    
    // Get input
    final Blip inputBlip = e.getBlip();
    final TextView inputDocument = 
            inputBlip.getDocument();
    final String inputText = inputDocument.getText();

    if (inputText.startsWith("!groovy")) {
        final String script = inputText
                .substring("!groovy".length());

        // Execute script
        final GroovyShell shell = new GroovyShell();
        final StringBuilder result = 
                new StringBuilder("Result: ");
        try {
            result.append(shell
                    .evaluate(script));
        } catch (final Exception ex) {
            result.append(e.toString());
        }

        // Create response
        final Blip blip = bundle.getWavelet()
                .appendBlip();
        blip.getDocument().append(result.toString());
     }
   }
}

This code first checks if there is an event of type BLIP_SUBMITTED. If so, it gets the blips contents and checks for the prefix "!groovy". Then it removes the prefix, executes the remaining content as a Groovy script with GroovyShell and appends a blip with the result. The output will look like this:



Conclusion
That's basically all, to build a simple Groovy robot. The code above shows a simplified version of GroovyBot which is currently deployed, though. It could be improved in many ways, for example System.out could be captured and also shown in the output. Also, the result could be displayed in another way for a better user experience, for example as a child blip, an inline blip or even as a gadget. But I ran into some issues trying this, for example inline blips were not displayed, or child blips could not be removed and re-added. There are some known bugs in the client API, but all in all, I had a really good experience with wave and its client API. There are many things left, I'd like to do, for example syntax highlighting, using a gadget or making some predefined scripts available, e.g. some DSLs. If you've got some ideas, for example what would be a better user experience, you are welcome. You can start trying GroovyBot right now. It's address is groovybot@appspot.com. Why don't you start with this example, taken from the Practically Groovy series:

!groovy
def zip = "80020"
def addr = "http://weather.yahooapis.com/forecastrss?p=${zip}"
def rss = new XmlSlurper().parse(addr)
def results = rss.channel.item.title
results << "\n" + rss.channel.item.condition.@text 
results << "\nTemp: " + rss.channel.item.condition.@temp 
println results

Resources
[1] Google Wave
[2] GroovyBot at GitHub (Source Code)
[3] Google Wave Jave Robots Tutorial
[4] Google App Engine

Java vs. Scala vs. Groovy - Performance Update

It's been quite a while since my post on the micro benchmark comparison between Java, Scala and Groovy. Since the Groovy developers tackled some performance issues with the Groovy 1.6 release, I thought, I'd give it another try. I used Groovy 1.6.3, Scala 2.7.5 and JDK 1.6.0 Update 14. I left the code that I used for the last comparison unchanged. I did not make much use of any specific language features, so it's quite a straightforward quicksort implementation, see the code below.

The Result
Before showing the result, just let me make clear, that I love the Groovy ;-) But seriously, after the anouncement, that the performance was one of the primary goals for the Groovy 1.6 release, I was a bit disappointed. We'll have to keep in mind though, that this is just a (poorly written) micro benchmark, that doesn't mean anything. And after all, it's all about the groovy language features anyway.

Nuff said, here is the result of sorting 100.000 integers:

1. Java: 45ms
2. Scala: 56ms
3. Groovy: 12800ms


And here's the code:

Java

public class QuicksortJava {

 public static void swap(int[] a, int i, int j) {
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
 }

 public static void quicksort(int[] a, int L, int R) {
  int m = a[(L + R) / 2];
  int i = L;
  int j = R;
  while (i <= j) {
   while (a[i] < m)
    i++;
   while (a[j] > m)
    j--;
   if (i <= j) {
    swap(a, i, j);
    i++;
    j--;
   }
  }
  if (L < j)
   quicksort(a, L, j);
  if (R > i)
   quicksort(a, i, R);
 }

 public static void quicksort(int[] a) {
  quicksort(a, 0, a.length - 1);
 }

 public static void main(String[] args) {

  // Sample data
  int[] a = new int[100000];
  for (int i = 0; i < a.length; i++) {
   a[i] = i * 3 / 2 + 1;
   if (i % 3 == 0)
    a[i] = -a[i];
  }

  long t1 = System.currentTimeMillis();
  quicksort(a);
  long t2 = System.currentTimeMillis();
  System.out.println(t2 - t1);

 }

}

Scala

package quicksort

object QuicksortScala {

  def quicksort(xs: Array[Int]) {
    
    def swap(i: Int, j: Int) {
      val t = xs(i); xs(i) = xs(j); xs(j) = t
    }
    
    def sort1(l: Int, r: Int) {
      val pivot = xs((l + r) / 2)
      var i = l; 
      var j = r
      while (i <= j) {
        while (xs(i) < pivot) i += 1
        while (xs(j) > pivot) j -= 1
        if (i <= j) {
          swap(i, j)
          i += 1
          j -= 1
        }
      }
      if (l < j) sort1(l, j)
      if (r > i) sort1(i, r)
    }
    sort1(0, xs.length - 1)
  }
  
  def main(args : Array[String]) {
    var a : Array[Int] = new Array[Int](100000)
    var i : Int = 0
    for (e <- a) {
      a(i) = i*3/2+1;
   if (i%3==0) a(i) = -a(i);
      i = i+1
    }
    val t1 = System.currentTimeMillis();
    quicksort (a)
    val t2 = System.currentTimeMillis();
    println(t2-t1)
  }
}

Groovy

def swap(a, i, j) {
 temp = a[i]
 a[i] = a[j]
 a[j] = temp
}

def quicksort(a, L, R) {
 m = a[((L+R)/2).intValue()]
 i=L
 j=R
 while (i<=j) {
  while (a[i]<m) i++
  while (a[j]>m) j--
  if (i<=j) {
   swap(a, i, j)
   i++
   j--
  }
 }
 if (L<j) quicksort(a,L,j)
 if (R>i) quicksort(a,i,R)
}

def quicksort(a) {
 quicksort(a, 0, a.length-1)
}

// Sample data
a = new int[100000]
a.eachWithIndex {x, i ->
 a[i] = i*3/2+1
 if (i%3==0) a[i] = -a[i]
}

t1 = System.currentTimeMillis()
quicksort(a)
t2 = System.currentTimeMillis()
println t2-t1 

Note: There was a bug in Scala code of the first version of this post, which is now fixed. Scala now goes slightly better.

quicksort source code

andres asked for the source code of the quicksort comparison.

Java
Scala
Groovy

Please give me some feedback

quicksort java scala groovy

today i compared the running times of the quicksort algorithm implemented in java, scala and groovy. i took the scala implementation from 'Scala By Example' [available on scala-lang.org] and based on that i wrote the other two. i ran a test on an array of 1.000.000 integers. the algorithms were not optimized for each particular language [but i compiled the groovy file at least] and i don't really know if these results are quite representative. but anyway, here are the running times:

java: 280 ms
scala: 359 ms
groovy: 535250 ms

far behind

hi, currently i feel so far behind. There's so much motion in the java community, so many new things i'm currently discovering and I'm trying to catch it all up. There are all these new languages that is talked about so much (e.g. Groovy, (J)Ruby, Scala, ...); some people even say that java is at its end. Then there is for example JavaFX that plays an important role at this years' JavaOne or there is the new SpringSource Application Platform or Google's Android.

This is simply too much. Seems like I have to wait and see what is really important.

grails orm (gorm)

grails object relational mapping is so great. it`s based on hibernate and one of its coolest features is dynamic finders. a dynamic finder in grails is a method for querying data that does not exist up front but is created at runtime.

consider a domain model class user which has properties birthday and username. you can then query data calling User.findByUsername(uname) or User.findByUsernameLike(uname) or even User.findByUsernameAndBirthdayLessThan(uname, beforeDate) without implementing or even declaring these methods in any way - they are generated dynamically at runtime and this is mainly possible because of groovy`s dynamic features.

checking out grails

one week ago i started trying out grails and it`s really amazing how `convention over configuration` accelerates web development. a grails application consists of three (or four?) layers: a set of views and controllers (one for each domain model class), a service layer and a persistence layer which is integrated into the domain model (this is quite a new approach, i think).

the project starts creating an empty domain model class which actually grails creates for you from the command line. then you need to fill this class with its properties. grails can then create all other components (view, controller, persistence, tests, ...) for you either using scaffolding (i.e. components are generated at runtime) or by generating the according groovy files. the generated artefacts are created based on useful defaults (the basic crud actions are implemented) and can be customized by the developer later on.

all in all i`m very confident with what i`m able to do with grails after only one week. but i think what helped very much is that i`m a bit familiar with the frameworks used by grails (groovy/java, spring, spring mvc, hibernate). the next days will go on learning grails and have a deeper look into the details of the different layers.

beginning groovy

last week i started to learn groovy. i think i heard about groovy for the first time at the beginning or in the middle of last year and it´s getting more and more popular. at a certain point last week my curiosity had reached maximum, so i gave it a try.

groovy is a dynamic programming language that runs on the JVM and it´s quite easy to learn for java programmers. as it runs on the jvm you can use existing java libraries in groovy as well as you can use groovy scripts in your java applications which at the moment seems the main use case to me. mainly due to its dynamic features groovy offers more flexibility and an increased productivity opposed to java in some cases, which is probably the primary goal of groovy. in other cases you will probably miss some of java´s features (mainly static typing).

my first impression of groovy is that with some experience you can do simple things really fast, for example text/data processing. in this case groovy comes with really helpful features like improved support for regular expressions, closures, builders, native support of lists and maps, ranges and groovy strings.

maybe the next days i will get into details of some the coolest features of groovy, e.g. closures, and when i feel experienced enough i`ll try grails, a groovy web application framework.