Микрооптимизация scala-phash

Прочитав статью Li Haoyi про микрооптимизации Scala-кода, решил проверить эффект одной из них самостоятельно. В качестве подопытного кролика выбрал свою библиотеку сравнения изображений scala-phash.

Запускаю юнит-тесты, подключаюсь к процессу через VisualVM и вижу в топе процессорного времени очень интересные функции map и foreach.

Self Time отображает время, которое тратится на исполнение самого метода без учёта тех функций, которые он вызывает изнутри. То есть куча времени уходит именно на итерирование по массивам, а не на действия, которые осуществляются с их элементами.

Об этой проблеме писал и Li Haoyi в своей статье: проходы по массивам при помощи map и foreach работают гораздо менее эффективно, чем простой цикл while. Вероятно, это связано со спецификой исполнения Scala кода на jvm, в частности, боксингом ― заворачиванием примитивного типа в объект (например, int -> java.lang.Integer). foreach принимает обобщённое лямда-выражение, параметр которого компилятору приходится боксить.

Кроме прямых вызовов упомянутых методов, в моём коде есть обход массивов через for. Это тоже плохая идея, потому что при компиляции он развернётся в тот же самый foreach:

// Первая строка при компиляции развернётся во что-то, очень похожее на вторую 
for (i <- Array(1, 2, 3, 4, 5)) { println(i) }
Array(1, 2, 3, 4, 5).foreach(i => println(i))

В то же время while ― это не метод, принимающий лямбду, а самостоятельная языковая конструкция. Поэтому циклы лишены проблем с боксингом.

Если отбросить детали, то моя библиотека выполняет квадратичные алгоритмы, поэлементно перебирающие большие числовые массивы. Поэтому удалось получить хороший прирост производительности, просто переписав обход трёх массивов на while, не затрагивая алгоритмическую сложность программы.

Время на выполнение тестов до переписывания: И после:

Ускорение почти на 40% без каких-либо умственных усилий!

Для верности написал ещё простой бенчмарк с хэшированием изображения 500x500px новой и старой версиями библиотеки:

import org.scalameter._
import scalaphash._

import java.awt.image.BufferedImage
import java.io.File
import javax.imageio.ImageIO

object Hello extends App {
  val img = ImageIO.read(new File("src/main/resources/images/small.jpg"))

  bench("radial", img)(PHash.unsafeRadialHash(_))

  bench("marr", img)(PHash.unsafeMarrHash(_))

  bench("DCT", img)(PHash.unsafeDctHash(_))

  private def bench[Hash](name: String, image: BufferedImage)(f: BufferedImage => Hash): Unit = {
    val time = config(
      Key.exec.benchRuns -> 20
    ) withWarmer {
      new Warmer.Default
    } withMeasurer {
      new Measurer.IgnoringGC
    } measure {
      f(image)
    }
    println(s"$name time: $time")
  }
}

Результаты замеров очень приятные:

1.2.1

radial time: 82.82101674999998 ms
marr time: 595.6078000499999 ms
DCT time: 96.3602538 ms

1.2.0

radial time: 164.72333365000003 ms
marr time: 1253.7434706 ms
DCT time: 292.0225023500001 ms

Несмотря на дешевизну этой оптимизации, она имеет смысл только для очень небольшого подмножества программ. Эффект будет заметен только при итерациях по большим массивам и только в горячем коде. В большинстве случаев бутылочное горлышко расположено далеко не в обходе коллекций.