Re: Arrays: Disappointed about ridiculous slow scala code compared to Java

There's no reflection calls in the code you posted (I compiled it here). A reflection call surely will make things slow, if it happens inside a loop. The only place left for it that would make a difference for performance is inside Comparator. Could you post that code (Java and Scala), please?

Other than that, Juma is correct in his observations with regards to parameterized arrays.

On Wed, Nov 4, 2009 at 8:29 AM, Burkhard Ludwig <ludwig.burkhard@...> wrote:

Good morning.

Yesterday evening I wondered why some code of mine is so slow. Then I made an experiment.

The bottom line is that the very same (simple) array based algorithm is ridiculous slow in scala vs. java and it got worse in 2.8.

The relation is as follows java : scala-2.7 : scala-2.8 = 1 : 2.6 : 22,3.

The 2.8-penalty can be reduced in scala 2-8 with GenericArray[Int] instead of Array[Int] to a relation  java vs. scala = 1 : 1.3.

So the question is: Is that expected? And is there an advice other than: Code your array stuff in plain Java ?

I find it especially annoying, that the simple out-of-the-box solution using Array[T] is so painfully slow.

 

As an experiment I used a dumb little shell sort algorithm which I coded in java and scala. This execises array lookup and assignments. 

The java and scala versions are appended below to give you an impression. (I save you from the complete test mock-up.)

Timing measurements can be cristicised technically to death, and I did't try to set up a benchmark, but when you arrive at a factor of 22, then the details ar not important.

Thank you for listening,

Burkhard

PS: A peek with javap -c showed something like the lines below in in the innermost loop of the plain 2.8-code, which

      is totally absent in the plain java code and the generic array code has something like calls to apply and update.

      So I fear that all this drag is by design, and that might well "tag" scala 2.8 as "fancy but so slooow". 

      I remembered the commercials: "Scala is almost as fast as java". Well thisis true unless you use fine new stuff

      w/o recognizing.  I hope I am in error.

   64: invokestatic #302; //Method java/lang/reflect/Array.get:(Ljava/lang/Object;I)Ljava/lang/Object;

  ...

   74: invokestatic #306; //Method java/lang/reflect/Array.set:(Ljava/lang/Object;ILjava/lang/Object;)V

PPS.: If anybody is interested, I can post the test mockups (which differ for 2.7 and 2.8)

Scala versions used:

 Scala version 2.7.4.final (Java HotSpot(TM) Client VM, Java 1.5.0_20). 

 scala version 2.8.0.r18925-b20091006020914 (Java HotSpot(TM) Client VM, Java 1.5.0_20)

Run time comparisions

The numbers are milliseconds for 100000 calls each. (gathered with System.currentTimeMillis)

The data are for an empty measurement, an empty loop over the data, a simple reverse-code and shell- and insert_sort.

both implemented in java and scala and for 2.8 also for GenericArrays.

1) 

Welcome to Scala version 2.7.4.final (Java HotSpot(TM) Client VM, Java 1.5.0_20).

Type in expressions to have them evaluated.

Type :help for more information.

scala> tst.Test_27.run(100000)

empty measurement: 0

empty loop: 8

reverse: 113

shell: 1482

java shell: 538

insert: 1608

java insert: 544

2)

Welcome to Scala version 2.8.0.r18925-b20091006020914 (Java HotSpot(TM) Client VM, Java 1.5.0_20).

Type in expressions to have them evaluated.

Type :help for more information.

scala> tst.Test_28.run(100000)

empty measurement: 0

empty loop: 7

reverse: 1080

shell: 13784

java shell: 620

generic shell: 828

insert: 15288

java insert: 630

generic insert: 865

Code examples

Java:

class Java<T> {

  

  static <T> void shellSort(T[] a, int first, int last, Comparator<? super T> c) {

    int h = (last - first)/3 +1;

    while (h > 0) {

      insert_sort(h, a, first, last, c);

      h = h == 1 ? 0 : (h/3 + 1);

    }

  }

  static <T> void insert_sort(int h, T[] a, int first, int last, Comparator<? super T> c) {

    int i = first+h;

    while (i < last) {

      T pivot = a[i];

      int j = i;

      while (j >= h && c.compare(pivot, a[j-h]) < 0) {

        a[j] = a[j-h];

        j -= h;

      }

      a[j] = pivot;

      i += h;

    }

  }

}

Scala

final object Test_28 {

  def shellSort[T](a: Array[T], first: Int, last: Int)(c: Comparator[T]) {

    var h = (last - first)/3 +1

    while (h > 0) {

      insert_sort(h, a, first, last)(c) 

      h = if (h == 1) 0 else h/3 + 1

    }

  }

  def insert_sort[T](h: Int, a: Array[T], first: Int, last: Int)(c: Comparator[T]) {

    var i = first+h

    while (i < last) {

      val pivot = a(i)

      var j = i

      while (j >= h && c.compare(pivot, a(j-h)) < 0) {

        a(j) = a(j-h)

        j -= h

      }

      a(j) = pivot

      i += h

    }

  }

}

--
Daniel C. Sobral

Veni, vidi, veterni.