Pankaj Kumar's Weblog

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 array[j] = last
array[j - 1] = current
}
}
}
}

void populate ( String[] array, int num ) {

Random ran = new Random ()
int l = chars.size ()

for ( i in 0.. {
StringBuffer s = new StringBuffer ()

for ( j in 0.. int r = ran.nextInt ( l )
s.append ( chars [r] )
}

array[i] = s.toString()
}
}

static void main ( args ) {
def sort = new bsort ()
String[] array = new String[sort.num]

println ( "Populating the array with ${sort.num} Strings, each of ${sort.ssize} characters..." )

def st = System.currentTimeMillis ()
sort.populate ( array, sort.num )
def et = System.currentTimeMillis ()

println ( " ... done. Elapsed time: ${et - st} millis." )

// println ( "Original array:" )
// array.each { println ( it ) }

println ()
println ( "Sorting the array ..." );

st = System.currentTimeMillis ()
sort.sort ( array )
et = System.currentTimeMillis ()

println ( " ... done. Elapsed time: ${et - st} millis." )

// println ( "Sorted array:" )
// array.each { println ( it ) }
}
}

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.

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

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.