Following Nick's post I came up to check the numbers and investigate a possible improvement using Scala 2.8 @specialized annotation.
Final numbers are at the end of the post.
I added few changes:
First I thought it would be better if both Scala and Java would sort the same size of array ;-) In Nick's example Java sorted 10,000 elements and Scala sorted 100,000.
The other was to do few iterations int he same JVM run to let JIT kick in. So now the Scala code looks like this:
package quicksort
import java.lang.Long.MAX_VALUE
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 (j < r) sort1(i, r)
}
sort1(0, xs.length - 1)
}
def main(args : Array[String]) {
var time = MAX_VALUE
for(i <- 0 to 100) (time = Math.min(time, doSort))
println("Scala time = " + time)
}
def doSort() = {
var a : Array[Int] = new Array[Int](10000000)
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();
t2 - t1
}
}
And here is the Java code:
package quicksort;
public class QuicksortJava {
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public 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 void quicksort(int[] a) {
quicksort(a, 0, a.length - 1);
}
public static void main(String[] args) {
QuicksortJava sorter = new QuicksortJava();
long time = Long.MAX_VALUE;
for(int i = 0; i < 100; i++)
time = Math.min(time, sorter.doSort());
System.out.println("java time = " + time);
}
private long doSort(){
// Sample data
int[] a = new int[10000000];
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();
return t2 - t1;
}
}
Decompiling the Scala code shows that there is no benefit of using the @specialized annotation since the Scala compiler compiles all the ints to primitives. Here is the Scala class decompiled code:
package quicksort;
import java.rmi.RemoteException;
import scala.*;
import scala.runtime.*;
public final class QuicksortScala$ implements ScalaObject{
public QuicksortScala$(){}
private final void sort1$1(int l, int r, int ai[]) {
do{
int pivot = ai[(l + r) / 2];
int i = l;
int j = r;
do{
if(i > j) break;
for(; ai[i] < pivot; i++);
for(; ai[j] > pivot; j--);
if(i <= j) {
swap$1(i, j, ai);
i++;
j--;
}
} while(true);
if(l < j) sort1$1(l, j, ai);
if(j < r)l = i;
else return;
} while(true);
}
private final void swap$1(int i, int j, int ai[]){
int t = ai[i];
ai[i] = ai[j];
ai[j] = t;
}
public long doSort(){
ObjectRef a$1 = new ObjectRef(new int[0x989680]);
IntRef i$1 = new IntRef(0);
(new BoxedIntArray((int[])a$1.elem)).foreach(new anonfun.doSort._cls1(a$1, i$1));
long t1 = System.currentTimeMillis();
quicksort((int[])a$1.elem);
long t2 = System.currentTimeMillis();
return t2 - t1;
}
public void main(String args[]){
LongRef time$1 = new LongRef(0xffffffffL);
Predef$.MODULE$.intWrapper(0).to(100).foreach(new anonfun.main._cls1(time$1));
Predef$.MODULE$.println((new StringBuilder()).append("Scala time = ").append(BoxesRunTime.boxToLong(time$1.elem)).toString());
}
public void quicksort(int xs$1[]){
sort1$1(0, xs$1.length - 1, xs$1);
}
public int $tag() throws RemoteException {
return scala.ScalaObject.class.$tag(this);
}
public static final QuicksortScala$ MODULE$ = this;
static { new QuicksortScala$(); }
}
I tried to compile and run the code in Scala 2.8 anyway and the results where exactly the same as with running it under Scala 2.7.5.
The numbers:
Scala: 1355ms
Java: 1265ms==> Java was 7% faster then Scala (Closer gap then the 33% in the previous benchmark).
UPDATEIsmael found a bug in the Scala Code, I updated Nick as well. The line
if (j < r) sort1(i, r)
should have been
if (i < r) sort1(i, r)
Changing the line made Java and Scala be equal in performance.
==> The Scala code above is no slower or faster then Java (as should be in this specific case).
