Strange behavior with a "tail rec" optimization

[Lachenal tanguy]

Hello,

I've tried to benchmark a quicksort programm writen in Java and Scala 
and i get some strange result (At least for me).
But the problem seems not related to Scala but more to JIT or my 
benchmark are wrong...

Here is the quicksort programm (All in java of course :))

public class QuickSortJava {
     public static void sort(int[] xs) {
         sort1(0, xs.length - 1, xs);
     }

     private static void swap(int i, int j, int[] xs) {
         int t = xs[i];
         xs[i] = xs[j];
         xs[j] = t;
     }

     private static void sort1(int l, int r, int[] xs) {
         int pivot = xs[(l + r) / 2];
         int i = l;
         int j = r;
         while (i <= j) {
             while (xs[i] < pivot)
                 i += 1;
             while (xs[j] > pivot)
                 j -= 1;
             if (i <= j) {
                 swap(i, j, xs);
                 i += 1;
                 j -= 1;
             }
         }
         if (l < j)
             sort1(l, j, xs);
         if (j < r)
             sort1(i, r, xs);
     }
}

Now the quicksort programm that i get with the scala compiler in java 
version :

public class QuickSortScala {
     public static void sort(int[] xs) {
         sort1(0, xs.length - 1, xs);
     }

     private static void swap(int i, int j, int[] xs) {
         int t = xs[i];
         xs[i] = xs[j];
         xs[j] = t;
     }

     private static void sort1(int l, int r, int[] xs) {
         while (true) {
             int pivot = xs[(l + r) / 2];
             int i = l;
             int j = r;
             while (i <= j) {
                 while (xs[i] < pivot)
                     i += 1;
                 while (xs[j] > pivot)
                     j -= 1;
                 if (i <= j) {
                     swap(i, j, xs);
                     i += 1;
                     j -= 1;
                 }
             }
             if (l < j)
                 sort1(l, j, xs);
             if (j >= r)
                 break;
             l = i;
         }
     }
}

Notice that the only difference is that the last 'sort1' call is 
transformed into a while loop.
Now the test programm :

public class MQuickSort {
     public static void main(String[] args) {
         int arraySize = 1 * 1000 * 1000;
         int nbLoop = 20;

         int[] xs = new int[arraySize];

         // Warm up
         for (int l = 0; l < nbLoop; l++) {
             initArray(xs);
             QuickSortJava.sort(xs);

             initArray(xs);
             QuickSortScala.sort(xs);
         }

         double delta2 = 0;
         for (int l = 0; l < nbLoop; l++) {
             initArray(xs);
             double t1 = System.nanoTime();
             QuickSortScala.sort(xs);
             double t2 = System.nanoTime();
             delta2 += (t2 - t1) / 1000.0 / 1000.0;
         }
         System.err.println("Delta for scala " + (delta2 / nbLoop));

         double delta1 = 0;
         for (int l = 0; l < nbLoop; l++) {
             initArray(xs);
             double t1 = System.nanoTime();
             QuickSortJava.sort(xs);
             double t2 = System.nanoTime();
             delta1 += (t2 - t1) / 1000.0 / 1000.0;
         }
         System.err.println("Delta for java " + (delta1 / nbLoop));
     }

     public static void initArray(int[] xs) {
         for (int i = 0; i < xs.length; i++) {
             xs[i] = xs.length - i;
         }
     }
}

And finally the result :
Delta for scala 43.98459049999998
Delta for java 32.0383011

So the version with the "tail rec" optimization performs significatively 
slower than the traditional one.
I tried this with JDK 1.6 update 21 and 27 and the JDK 1.7 and i get the 
same result.

I was expecting that the two versions will perform nearly the same.
So I don't understand why they are such a difference in performance.

So my questions are :
+ Is my test programm wrong ?
+ Why the while loop performs so badly in this case ?

Thanks for your response and for reading this long post :)