« Why am I using Firefox much more often | Main | Groovy Bubble Sort -- Revised »

Adding Groovy to the Bubble Sort Performance Race

Few weeks ago I published a runtime performance comparison article comparing performance of bubble sort programs under Beanshell, JavaScript (Rhino) and Java. Lateron, based on a program contributed by Jim Adrig, I added Jython and Python programs as well.

Although I had received a few requests to add Groovy in the mix, no one actually came forward with a working program. However, this changed yesterday and I got a groovy bsort program from Graeme Sutherland. I ran it on my box under the same conditions as other programs and am reporting the performance figures in the following updated table:

No. of stringsnum: 1000num: 5000num: 10000
Programgen.sortgen.sortgen.sort
bsh/bsort (BeanShell, interpreted)68815500251540200047801623000
js/bsort1 (intepreted)1404503441105060046330
js/bsort1 (compiled)1404403441094058046020
js/bsort2 (intepreted)44016601360415802516172000
js/bsort2 (compiled)44016251345403902470168000
java/bsort (java, compiled)32476310931094625
jython/bsort (jython-2.1)172328391886068844360
python/bsort (python-2.4.1)20437010209200204037100
python/bsort (jython-2.1)51530015008400280043400
groovy-1.0-jsr-03/bsort (interpreted)30048008001180001345469000
groovy-1.0-jsr-03/bsort (compiled)30047008401170001400465000

As you can see, Groovy performs better than Beanshell but falls behind Jython and JavaScript(Rhino). Interestingly, the compiled version performed only marginally better than the interpreted one. The same was true for JavaScript as well.

As Graeme wasn't confident that his code is optimal for Groovy, I am not updating my article yet. Perhaps Groovy fans can take a look and let me know what they think about it.

Comments (5)

Just had a couple of minutes to spare on the Groovy script, and I noticed the sample script is using lists instead of arrays. By using arrays, the results are roughly 30 to 40% better.

Here is the script I used (hoping the comment won't be truncated or rejected...):

// Generates n random strings and then sorts them using bubble sort.
import java.util.Random;

class bsort {
@Property num = 1000
@Property ssize = 20

char[] chars = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
]

public void sort ( String[] array ) {

for ( i in ( array.size () - 1 )..1 ) {
for ( j in 1..i ) {
def current = array[j]
def last = array[j - 1]

if ( current

I'll be the first to admit that Groovy is slow and there are tons of optimizations that should be done at some point. But I think the real point of Groovy is to be able to use the Java APIs natively from a scripting language so using Groovy to do the sort rather than just calling Collections.sort() seems like it would never be seen in practice.

A more interesting comparison, one that Groovy would probably still lose, would be to measure how long it takes a language to lookup an API call and dispatch since that is mostly what your Groovy code will be doing.

aaa:

although it is a microbenchmark, it is good to see Java is kicking ass with at least 10 times better performance..

Infernoz:

I think the java.util.RandomAccess interface should have the following a methods added and supported by all mutable implementations and that these methods be used by Collections.sort() mehods:

void sort();
void sort(Comparactor c);
void sort(int from, int to);
void sort(int from, int to, Comparactor c);

int binarySearch(Object key);
int binarySearch(Object key,Comparator c);
int binarySearch(Object key, int from, int to);
int binarySearch(Object key, int from, int to, Comparactor c);


IMHO Collections.sort() is very inefficient for java.util.RandomAccess and rather limnited too, it neadlessly requires n*(2+log(n)) steps instead of n*log(n), if the sort was done directly on the array inside the class! This was easy to do with a Vector subclass, but annoyingly impossible for ArrayList because the properties are all stupidly private instead of protected!

Me thinks Josh Bloch and Neal Gafter lost the plot and a great opertunity for optimisimg sorting and binary searching random access collections lists.

About

This page contains a single entry from the blog posted on October 12, 2005 11:30 PM.

The previous post in this blog was Why am I using Firefox much more often.

The next post in this blog is Groovy Bubble Sort -- Revised.

Many more can be found on the main index page or by looking through the archives.

Powered by
Movable Type 3.33