Скрытая стоимость исполнения в Scala?
Я наткнулся на этот старый вопрос и провел следующий эксперимент со Scala 2.10.3.
Я переписал версию Scala, чтобы использовать явную хвостовую рекурсию:
import scala.annotation.tailrec
object ScalaMain {
private val t = 20
private def run() {
var i = 10
while(!isEvenlyDivisible(2, i, t))
i += 2
println(i)
}
@tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
if (i > b) true
else (a % i == 0) && isEvenlyDivisible(i+1, a, b)
}
def main(args: Array[String]) {
val t1 = System.currentTimeMillis()
var i = 0
while (i < 20) {
run()
i += 1
}
val t2 = System.currentTimeMillis()
println("time: " + (t2 - t1))
}
}
и сравнил его со следующей версией Java. Я сознательно сделал функции нестатичными для справедливого сравнения со Scala:
public class JavaMain {
private final int t = 20;
private void run() {
int i = 10;
while (!isEvenlyDivisible(2, i, t))
i += 2;
System.out.println(i);
}
private boolean isEvenlyDivisible(int i, int a, int b) {
if (i > b) return true;
else return (a % i == 0) && isEvenlyDivisible(i+1, a, b);
}
public static void main(String[] args) {
JavaMain o = new JavaMain();
long t1 = System.currentTimeMillis();
for (int i = 0; i < 20; ++i)
o.run();
long t2 = System.currentTimeMillis();
System.out.println("time: " + (t2 - t1));
}
}
Вот результаты на моем компьютере:
> java JavaMain
....
time: 9651
> scala ScalaMain
....
time: 20592
Это Scala 2.10.3 на (Java HotSpot(TM) 64-разрядный сервер VM, Java 1.7.0_51).
Мой вопрос: какова скрытая стоимость с версией Scala?
Большое спасибо.
4 ответа
Что ж, бенчмаркинг OP не идеален. К счастью, JMH уже позаботился о многих вещах и имеет привязки как для Java, так и для Scala, необходимо смягчить тонны эффектов, включая разогрев, удаление мертвого кода, разветвление и т. Д. Пожалуйста, следуйте процедурам на странице JMH, чтобы получить тестовый проект, затем вы можете перенести тестовые тесты ниже.
Это пример теста Java:
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Fork(3)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
public class JavaBench {
@Param({"1", "5", "10", "15", "20"})
int t;
private int run() {
int i = 10;
while(!isEvenlyDivisible(2, i, t))
i += 2;
return i;
}
private boolean isEvenlyDivisible(int i, int a, int b) {
if (i > b)
return true;
else
return (a % i == 0) && isEvenlyDivisible(i + 1, a, b);
}
@GenerateMicroBenchmark
public int test() {
return run();
}
}
... и это пример теста Scala:
@BenchmarkMode(Array(Mode.AverageTime))
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Fork(3)
@Warmup(iterations = 5)
@Measurement(iterations = 5)
class ScalaBench {
@Param(Array("1", "5", "10", "15", "20"))
var t: Int = _
private def run(): Int = {
var i = 10
while(!isEvenlyDivisible(2, i, t))
i += 2
i
}
@tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
if (i > b) true
else (a % i == 0) && isEvenlyDivisible(i + 1, a, b)
}
@GenerateMicroBenchmark
def test(): Int = {
run()
}
}
Если вы запустите их на JDK 8 GA, Linux x86_64, вы получите:
Benchmark (t) Mode Samples Mean Mean error Units
o.s.ScalaBench.test 1 avgt 15 0.005 0.000 us/op
o.s.ScalaBench.test 5 avgt 15 0.489 0.001 us/op
o.s.ScalaBench.test 10 avgt 15 23.672 0.087 us/op
o.s.ScalaBench.test 15 avgt 15 3406.492 9.239 us/op
o.s.ScalaBench.test 20 avgt 15 2483221.694 5973.236 us/op
Benchmark (t) Mode Samples Mean Mean error Units
o.s.JavaBench.test 1 avgt 15 0.002 0.000 us/op
o.s.JavaBench.test 5 avgt 15 0.254 0.007 us/op
o.s.JavaBench.test 10 avgt 15 12.578 0.098 us/op
o.s.JavaBench.test 15 avgt 15 1628.694 11.282 us/op
o.s.JavaBench.test 20 avgt 15 1066113.157 11274.385 us/op
Обратите внимание, мы жонглируем t чтобы увидеть, является ли эффект локальным для конкретного значения t, Это не так, эффект является систематическим, и Java-версия в два раза быстрее.
PrintAssembly позволит пролить свет на это. Это самый горячий блок в тесте Scala:
0x00007fe759199d42: test %r8d,%r8d
0x00007fe759199d45: je 0x00007fe759199d76 ;*irem
; - org.sample.ScalaBench::isEvenlyDivisible@11 (line 52)
; - org.sample.ScalaBench::run@10 (line 45)
0x00007fe759199d47: mov %ecx,%eax
0x00007fe759199d49: cmp $0x80000000,%eax
0x00007fe759199d4e: jne 0x00007fe759199d58
0x00007fe759199d50: xor %edx,%edx
0x00007fe759199d52: cmp $0xffffffffffffffff,%r8d
0x00007fe759199d56: je 0x00007fe759199d5c
0x00007fe759199d58: cltd
0x00007fe759199d59: idiv %r8d
... и это аналогичный блок в Java:
0x00007f4a811848cf: movslq %ebp,%r10
0x00007f4a811848d2: mov %ebp,%r9d
0x00007f4a811848d5: sar $0x1f,%r9d
0x00007f4a811848d9: imul $0x55555556,%r10,%r10
0x00007f4a811848e0: sar $0x20,%r10
0x00007f4a811848e4: mov %r10d,%r11d
0x00007f4a811848e7: sub %r9d,%r11d ;*irem
; - org.sample.JavaBench::isEvenlyDivisible@9 (line 63)
; - org.sample.JavaBench::isEvenlyDivisible@19 (line 63)
; - org.sample.JavaBench::run@10 (line 54)
Обратите внимание, что в Java-версии компилятор использовал трюк для перевода вычисления целочисленного остатка в умножение и сдвиг вправо (см. Восхищение Хакера, гл. 10, раздел 19). Это возможно, когда компилятор обнаруживает, что мы вычисляем остаток от константы, что предполагает, что версия Java попала в эту приятную оптимизацию, а версия Scala - нет. Вы можете покопаться в разборке байт-кода, чтобы выяснить причину ошибки в скаляре, но смысл этого упражнения в том, что удивительные незначительные различия в генерации кода значительно увеличиваются в результате тестирования.
PS Так много для @tailrec...
ОБНОВЛЕНИЕ: более подробное объяснение эффекта: http://shipilev.net/blog/2014/java-scala-divided-we-fail/
Я изменил val
private val t = 20
до постоянного определения
private final val t = 20
и получил значительное повышение производительности, теперь кажется, что обе версии работают почти одинаково [в моей системе, см. обновление и комментарии].
Я не смотрел в байт-код, но если вы используете val t = 20 вы можете увидеть, используя javap что есть метод (и эта версия так же медленно, как та, с private val).
Поэтому я предполагаю, что даже private val включает в себя вызов метода, и это не сопоставимо напрямую с final на Яве.
Обновить
На моей системе я получил эти результаты
Java версия: время: 14725
Версия Scala: время: 13228
Использование OpenJDK 1.7 в 32-битной Linux.
По моему опыту, Oracle JDK в 64-битной системе действительно работает лучше, так что это, вероятно, объясняет, что другие измерения дают еще лучшие результаты в пользу версии Scala.
Что касается версии Scala, работающей лучше, я предполагаю, что оптимизация хвостовой рекурсии здесь имеет эффект (см. Ответ Фила, если версия Java переписана с использованием цикла вместо рекурсии, она снова работает одинаково).
Я посмотрел на этот вопрос и отредактировал версию Scala, чтобы t внутри run:
object ScalaMain {
private def run() {
val t = 20
var i = 10
while(!isEvenlyDivisible(2, i, t))
i += 2
println(i)
}
@tailrec private def isEvenlyDivisible(i: Int, a: Int, b: Int): Boolean = {
if (i > b) true
else (a % i == 0) && isEvenlyDivisible(i+1, a, b)
}
def main(args: Array[String]) {
val t1 = System.currentTimeMillis()
var i = 0
while (i < 20) {
run()
i += 1
}
val t2 = System.currentTimeMillis()
println("time: " + (t2 - t1))
}
}
Новая версия Scala теперь работает в два раза быстрее, чем оригинальная Java:
> fsc ScalaMain.scala
> scala ScalaMain
....
time: 6373
> fsc -optimize ScalaMain.scala
....
time: 4703
Я понял это потому, что у Java нет хвостовых вызовов. Оптимизированный Java с циклом вместо рекурсии выполняется так же быстро:
public class JavaMain {
private static final int t = 20;
private void run() {
int i = 10;
while (!isEvenlyDivisible(i, t))
i += 2;
System.out.println(i);
}
private boolean isEvenlyDivisible(int a, int b) {
for (int i = 2; i <= b; ++i) {
if (a % i != 0)
return false;
}
return true;
}
public static void main(String[] args) {
JavaMain o = new JavaMain();
long t1 = System.currentTimeMillis();
for (int i = 0; i < 20; ++i)
o.run();
long t2 = System.currentTimeMillis();
System.out.println("time: " + (t2 - t1));
}
}
Теперь моя путаница полностью решена:
> java JavaMain
....
time: 4795
В заключение, оригинальная версия Scala была медленной, потому что я не объявлял t быть final (прямо или косвенно, как указывает ответ Бериллиума). И оригинальная версия Java была медленной из-за отсутствия хвостовых вызовов.
Чтобы сделать версию Java полностью эквивалентной вашему коду Scala, вам нужно изменить ее следующим образом.
private int t = 20;
private int t() {
return this.t;
}
private void run() {
int i = 10;
while (!isEvenlyDivisible(2, i, t()))
i += 2;
System.out.println(i);
}
Это медленнее, потому что JVM не может оптимизировать вызовы методов.