Scala vs Java performance test

Скала подкупает своей лаконичностью и выразительностью, особенно по части алгоритмов над коллекциями. В стандартной библиотеке скалы можно встретить к тому же списку List - тучу всяких методов. Второй момент, который может шокировать новичка в скале - это разнообразие классов/интерфейсов/примесей (trait, надеюсь правильно перевел) для коллекций. Там и изменяемые коллекции, и не изменяемые, и так называемые билдеры, которые строят коллекцию наиболее эффективным образом. Но данная статья не об этом. Глядя на сие богатство закралось подозрение, что не может быть все так хорошо. Все эти функциональные примочки типа лямбд, неявных преобразователей, частичных функций, не могут обойтись бесплатно и возможно дадут проседание по производительности по сравнению с чистой джавой. Для проверки этой гипотезы накидал небольшой проект.

Подготовка

В качестве IDE для проекта взял бесплатные IDEA Community edition + Scala plugin.

Scala версии 2.10.0.

Java версии 1.7.0_09-b05.

Scala plugin позволяет создать проект для Scala, в котором, что мне понравилось, можно свободно мешать scala c java классами. Скорее всего это фича самой скалы, но мне, как новичку это в диковинку. Код скалы перед исполнением компилируется в java байткод, сохраняется в виде .class файлов  и выполняется на джаве, так что проседания по перфомансу, связанного с интерпретацией кода скалы в рантайме быть не должно.

Структура проекта

Была идея организовать проект таким образом, что-бы минимизировать усилия добавления нового кусочка кода, нуждающегося в проверке производительности. Базовый интерфейс для всех таких кусочков кода ITestCode (java).

package com.greentea.performance.test;

public interface ITestCode {
   String getName();
   void init();
   void run();
   Object getResult();
   void clean();
}

getName() выводит на экран имя теста. init() вызывается один раз для инициализации теста. run() может вызываться сколько угодно раз, и в конце необходимо вызвать clean() - задача которой освободить ресурсы, занимаемые тестовым кусочком кода. getResult() должен возвращать некий результат теста, например коллекцию которая изменялась. Это делается для того чтобы оптимизатор случайно не посчитал что раз результат нигде не используется, то код, его формирующий, можно вырезать. Движок тестирования вызывает этот метод 1 раз перед вызовом clean() для каждого теста, берет хешкод у объекта аккумулирует сумму всех хешкодов в одной переменной, и потом по окончании всех тестов эта сумма выводится на консоль.

Для итеративного запуска кусочка кода был написан класс IteratedTestCode (scala):

package com.greentea.performance.test


/**
 * User: goodg_000
 * Date: 17.02.13
 * Time: 13:13
 */
class IteratedTestCode(testCode : ITestCode, iterationsCount : Int) extends ITestCode {
  def warmUpIterationsCount = 20000
  def getName: String = testCode.getName + " [x" + iterationsCount + "]"

  def init() {
    testCode.init()
  }

  def warmUp() {
    var i = 0
    while (i < warmUpIterationsCount) {
      testCode.run()
      i += 1
    }
  }

  def run() {
    var i = 0
    while (i < iterationsCount) {
      testCode.run()
      i += 1
    }
  }

  def getResult: AnyRef = testCode.getResult

  def clean() {
    testCode.clean()
  }
}

Метод warmUp() используется движком тестирования что-бы прогнать код теста 20000 итераций перед замером времени. Это делается для того чтобы JIT догадался сделать все необходимые оптимизации.

Ну и собственно код запускающий тесты, и подсчитывающий время CodeBenchmark (scala):

package com.greentea.performance.test

import java.util

class CodeBenchmark {
  val tests = new util.ArrayList[ITestCode]()

  def addIteratedTest(testCode : ITestCode, iterationsCount : Int) {
    tests.add(new IteratedTestCode(testCode, iterationsCount))
  }

  def addTest(testCode : ITestCode) {
    tests.add(testCode)
  }

  def runTests() {
    var resultsHashSum = 0L
    val i = tests.iterator()
    while (i.hasNext) {
      val testCode = i.next()
      testCode.init()

      if (testCode.isInstanceOf[IteratedTestCode]) {
        testCode.asInstanceOf[IteratedTestCode].warmUp()
      }

      val start = System.currentTimeMillis()
      testCode.run()
      val end = System.currentTimeMillis()
      resultsHashSum += testCode.getResult.hashCode()
      printf("%70s: %s ms\n", testCode.getName, (end - start))

      testCode.clean()
      System.gc()
    }
    println(resultsHashSum)
  }
}

Тесты

С кодом тестов можно ознакомится на гитхабе.  Я постарался в основном проверить то, чем приходится часто пользоваться мне (не считая group).
Тесты располагаются в соответствующих пэкеджах, сгрупированные по тематике:
iteration - тестирование скорости итерирования по коллекции.
add - тестирование операции добавления в коллекции.
filter - фильтрация элементов коллекции по критерию.
group - группировка элементов коллекции в мапу по ключу, который генерируется из значения.
min - поиск минимального элемента в коллекции.
sum - суммирование элементов коллекции.

Для примера приведу куски кода для поиска минимума.

MinArrayListJava.java:

package com.greentea.performance.test.min;

import com.greentea.performance.test.ITestCode;

import java.util.ArrayList;
import java.util.List;

public class MinArrayListJava implements ITestCode {

   private List<String> list;
   private int elementsCount = 10;
   private String min;

   public MinArrayListJava(int elementsCount) {
      this.elementsCount = elementsCount;
   }

   public String getName() {
      return "Min of " + elementsCount + " elements of array list (Java)";
   }

   public void init() {
      list = new ArrayList<String>();
      for (int i = 0; i < elementsCount; ++i) {
         list.add("" + Math.pow(elementsCount - i, 2));
      }
   }

   public void run() {
      min = null;
      int lengthOfMin = Integer.MAX_VALUE;
      for (String val : list) {
         int len = val.length();
         if (min == null || len < lengthOfMin) {
            min = val;
            lengthOfMin = len;
         }
      }
   }

   public Object getResult() {
      return min;
   }

   public void clean() {
      list = null;
      min = null;
   }
}

MinByLinkedListScala.scala

package com.greentea.performance.test.min

import com.greentea.performance.test.ITestCode

class MinByLinkedListScala(elementsCount: Int) extends ITestCode {

  var list: List[String] = null
  var min: String = null

  def getName: String = "Min of " + elementsCount + " elements of linked list (list.minBy Scala)"

  def init() {
    list = (0 to elementsCount - 1).map(i => "" + Math.pow(elementsCount - i, 2)).toList
  }

  def run() {
    min = list.minBy(v => v.length)
  }

  def getResult: AnyRef = min

  def clean() {
    list = null
    min = null
  }
}

Как видим версия скалы намного короче! Но давайте посмотрим на производительность.

Результаты

(1)

                   Iteration array list of size 1000  (Java) [x200000]: 931 ms
                       Iteration array of size 1000  (Scala) [x200000]: 1040 ms
                  Iteration linked list of size 1000  (Java) [x200000]: 1118 ms
                  Iteration linked list of size 1000 (Scala) [x200000]: 1033 ms

(2)

                                                      Add to end of array list (Java) [x20000000]: 303 ms

                        Add to end of array buffer (Scala) [x20000000]: 234 ms

(3)

                         Add to end of list buffer (Scala) [x2000000]: 517 ms
                           Add to end of linked list (Java) [x2000000]: 155 ms

                         Append to end of linked list (Scala) [x10000]: 2008 ms

(4)

                        Add new Object() to hash set (Java) [x2000000]: 546 ms
                       Add new Object() to hash set (Scala) [x2000000]: 529 ms

(5)

   Select even numbers from array list of length 50 (Java) [x2000000]: 789 ms
   Select even numbers from linked list of length 50 (Java) [x2000000]: 902 ms
 Select even numbers from array of length 50 (Scala) [x2000000]: 1340 ms
         Select even numbers from list of length 50 (Scala) [x2000000]: 1072 ms      

(6)

                   Sum of 10 elements of array list (Java) [x20000000]: 408 ms
                       Sum of 10 elements of array (Scala) [x20000000]: 924 ms
                 Sum of 10 elements of linked list (Scala) [x20000000]: 804 ms
(7)
                   Sum of 10000 elements of array list (Java) [x20000]: 235 ms
                       Sum of 10000 elements of array (Scala) [x20000]: 2442 ms
                 Sum of 10000 elements of linked list (Scala) [x20000]: 1607 ms

(8)

                                                      Min of 100 elements of array list (Java) [x2000000]: 437 ms
      Min of 100 elements of linked list (list.minBy Scala) [x2000000]: 2645 ms
                 Min of 100 elements of linked list (Scala) [x2000000]: 967 ms
(9)
                   Min of 10000 elements of array list (Java) [x20000]: 811 ms
      Min of 10000 elements of linked list (list.minBy Scala) [x20000]: 2997 ms
                 Min of 10000 elements of linked list (Scala) [x20000]: 999 ms

(10)

   roups of 100 elements of array list by key func (Java) [x1000000]: 2975 ms
   Group of 100 elements of linked list by key func (Scala) [x1000000]: 3698 ms
(11)
    Groups of 10000 elements of array list by key func (Java) [x10000]: 2723 ms
   Group of 10000 elements of linked list by key func (Scala) [x10000]: 3378 ms

В скобочках [x20000000] указано количество запусков куска кода (метод run()). Сразу оговорюсь, что при повторном запуске результаты отличаются, но не очень сильно. Так что выводы будем делать глядя на текущие цифры.
Итак, о чем же можно сказать, глядя на эти результаты..

1) Тест на скорость итераций, с вызовом System.currentTimeMillis(); внутри каждой итерации (чтоб компилятор не вырезал код как ничего не делающий). Показывает что скорости итераций по linked list и array list примерно равны между собой в обоих языках. На это можно опереться последующих тестах в том смысле, что будет корректно сравнивать к примеру суммирование элементов array list с суммированием элементов в linked list - т.к. скорости итераций должны быть примерно равны.

2) скаловский mutable.ArrayBuffer работает даже быстрее чем ArrayList! Почему - сказать трудно, но внутри он работает по схожему принципу что и ArrayList.

3) со связными списками хуже - джавовский LinkedList работает быстрее чем ListBuffer. А вот mutable.LinkedList - ом для добавления в конец вообще нельзя пользоваться, т.к. он при этом, если не ошибаюсь, проходит от начала до конца списка.

4) Добавление в hash set - скорость одинакова.

5) Тест связанный с выбором четных чисел из коллекции быстрее отрабатывает в джаве, причем выбор из array list быстрее в 2 раза чем в скале выбор из array.

6) Суммирование 10 элементов массива быстрее в джаве в 2 раза .

7) Суммированием 10000 элементов намного быстрее в джаве! С чем это связано, не очень понятно. Посмотрим код метода sum в скале:

def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)

Копнем глубже:

def foldLeft[B](z: B)(op: (B, A) => B): B = {
    var result = z
    this.seq foreach (x => result = op(result, x))
    result
  }

Черт его знает, есть подозрение что примитивная операция op не инлайнится. Но это лишь мои догадки..

8) Поиск минимума к сожалению, не смотря на всю красоту записи в скале (см выше) в 4-5 раз медленнее аналога на джаве. Интересно и тут разобраться чего так происходит. Посмотрим код скалы метода minBy:

 def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.minBy")

    reduceLeft((x, y) => if (cmp.lteq(f(x), f(y))) x else y)
  }

Посмотрим  глубже на reduceLeft:

  def reduceLeft[B >: A](op: (B, A) => B): B = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.reduceLeft")

    var first = true
    var acc: B = 0.asInstanceOf[B]

    for (x <- self) {
      if (first) {
        acc = x
        first = false
      }
      else acc = op(acc, x)
    }
    acc
  }

Видим, что в reduceLeft передается "лямбда в лямбде", и на каждой итерации эта конструкция дергается. При этом вложенная лямбда f вызывается 2 раза f(x), f(y). Первый вызов на самом деле избыточен, т.к. f(x) уже вычислялось на предыдущей итерации. Java код такой проблемой не страдает так как вычисления ключа сравнения сохраняется в lengthOfMin. И помимо лишнего  вычисления в джава коде намного меньше вызовов функции, что тоже сказывается на производительности. Scala код эквивалентный Java  коду для поиска минимума работает в 3 раза медленнее. В чем же дело? Деактивация jad -ом показывает интересную картину:

    public void run()
    {
        Object _tmp = null;
        ObjectRef min = new ObjectRef(null);
        IntRef minLen = new IntRef(0x7fffffff);
        list().foreach(new Serializable(min, minLen) {

            public final void apply(String v)
            {
                int len = (new StringOps(Predef$.MODULE$.augmentString(v))).size();
                if(len < minLen$1.elem)
                {
                    min$1.elem = v;
                    minLen$1.elem = len;
                }
            }

            public final volatile Object apply(Object v1)
            {
                apply((String)v1);
                return BoxedUnit.UNIT;
            }

            public static final long serialVersionUID = 0L;
            private final ObjectRef min$1;
            private final IntRef minLen$1;

            public 
            {
                this.min$1 = min$1;
                this.minLen$1 = minLen$1;
                super();
            }
        }
);

Настораживает строка int len = (new StringOps(Predef$.MODULE$.augmentString(v))).size();
Попробуем заменить size на length...
Min of 100 elements of linked list (Scala) [x2000000]: 495 ms
Намного лучше!
В декомпилированной версии стало int len = v.length();
Вот так бывает, из-за казалось бы мелочи, производительность режется в 2 раза.

9) Аналогичный тест на поиск минимума для 10000 элементов в джаве оказался медленнее в 2 раза чем для 10 элементов (в пересчете на 1 итерацию). С чем это связано - не понятно.


10-11) Группировка элементов чуть быстрее в джаве.

Вывод?

Насколько мы могли видеть, базовые операции с коллекциями Scala 2.10.0 выполняет не хуже а иногда и лучше джавы. Но когда дело доходит до алгоритмов, то притягательная лаконичность скалы может обернуться жесткими проседаниями по производительности. Кроме того, есть вероятность напороться на код, который выглядит безобидно (метод size()  в String), но разворачивается в какой то невменяемый громоздкий код. 

Проект планирую и дальше пополнять небольшими тестами. Когда будут выходить новые версии скалы постараюсь перетестировать и выложить новые результаты.