Почему моя хвостовая рекурсия Scala быстрее, чем цикл while?
Вот два решения для упражнений 4.9 в Cay Horstmann Scala для Impatient: "Напишите функцию lteqgt (значения: Array [Int], v: Int), которая возвращает тройку, содержащую подсчеты значений меньше v, равный v и больше v." Один использует хвостовую рекурсию, другой - цикл while. Я думал, что оба будут скомпилированы для аналогичного байт-кода, но цикл while медленнее, чем хвостовая рекурсия, почти в два раза. Это говорит о том, что мой метод плохо написан.
import scala.annotation.tailrec
import scala.util.Random
object PerformanceTest {
def main(args: Array[String]): Unit = {
val bigArray:Array[Int] = fillArray(new Array[Int](100000000))
println(time(lteqgt(bigArray, 25)))
println(time(lteqgt2(bigArray, 25)))
}
def time[T](block : => T):T = {
val start = System.nanoTime : Double
val result = block
val end = System.nanoTime : Double
println("Time = " + (end - start) / 1000000.0 + " millis")
result
}
@tailrec def fillArray(a:Array[Int], pos:Int=0):Array[Int] = {
if (pos == a.length)
a
else {
a(pos) = Random.nextInt(50)
fillArray(a, pos+1)
}
}
@tailrec def lteqgt(values: Array[Int], v:Int, lt:Int=0, eq:Int=0, gt:Int=0, pos:Int=0):(Int, Int, Int) = {
if (pos == values.length)
(lt, eq, gt)
else
lteqgt(values, v, lt + (if (values(pos) < v) 1 else 0), eq + (if (values(pos) == v) 1 else 0), gt + (if (values(pos) > v) 1 else 0), pos+1)
}
def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
var lt = 0
var eq = 0
var gt = 0
var pos = 0
val limit = values.length
while (pos < limit) {
if (values(pos) > v)
gt += 1
else if (values(pos) < v)
lt += 1
else
eq += 1
pos += 1
}
(lt, eq, gt)
}
}
Отрегулируйте размер bigArray в соответствии с размером вашей кучи. Вот несколько примеров:
Time = 245.110899 millis
(50004367,2003090,47992543)
Time = 465.836894 millis
(50004367,2003090,47992543)
Почему метод while намного медленнее, чем tailrec? Наивно версия tailrec выглядит немного невыгодной, так как она всегда должна выполнять 3 "if" проверки для каждой итерации, тогда как версия while часто выполняет только 1 или 2 теста из-за конструкции else. (NB, изменяя порядок, который я выполняю, оба метода не влияют на результат).
Ответы
Ответ 1
Результаты тестов (после уменьшения размера массива до 20000000)
В Java 1.6.22 я получаю 151 and 122 ms для хвостовой рекурсии и while-loop соответственно.
В Java 1.7.0 я получаю 55 and 101 ms
Итак, в Java 6 ваш while-loop на самом деле быстрее; оба улучшены в производительности в Java 7, но хвостовая рекурсивная версия обогнала цикл.
Объяснение
Разница в производительности связана с тем, что в вашем цикле вы условно добавляете 1 к итоговым значениям, тогда как для рекурсии вы всегда добавляете 1 или 0. Таким образом, они не эквивалентны. Эквивалентный цикл while для вашего рекурсивного метода:
def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
var lt = 0
var eq = 0
var gt = 0
var pos = 0
val limit = values.length
while (pos < limit) {
gt += (if (values(pos) > v) 1 else 0)
lt += (if (values(pos) < v) 1 else 0)
eq += (if (values(pos) == v) 1 else 0)
pos += 1
}
(lt, eq, gt)
}
и это дает точно такое же время выполнения, как и рекурсивный метод (независимо от версии Java).
Обсуждение
Я не эксперт по поводу того, почему Java 7 VM (HotSpot) может оптимизировать это лучше, чем ваша первая версия, но я бы предположил, что он каждый раз использует один и тот же путь через код (вместо того, чтобы разветвляться вдоль if/else if), поэтому байт-код может быть встроен более эффективно.
Но помните, что это не так в Java 6. Почему один while-loop превосходит другой вопрос о внутренних компонентах JVM. К счастью для программиста Scala, версия, выпущенная из идиоматической хвостовой рекурсии, является более быстрой в последней версии JVM.
Разница также может возникать на уровне процессора. См. этот вопрос, в котором объясняется, как код замедляется, если он содержит непредсказуемое ветвление.
Ответ 2
Две конструкции не идентичны. В частности, в первом случае вам не нужны какие-либо переходы (на x86 вы можете использовать cmp, setle и add, вместо того, чтобы использовать cmp и jb и (если вы не прыгаете) добавить. Не прыгать быстрее чем прыгать практически во все современные архитектуры.
Итак, если у вас есть код, который выглядит как
if (a < b) x += 1
где вы можете добавить, или вы можете прыгать вместо этого, vs.
x += (a < b)
(что имеет смысл только в C/С++, где 1 = true и 0 = false), последний имеет тенденцию быть быстрее, поскольку его можно превратить в более компактный ассемблерный код. В Scala/Java вы не можете этого сделать, но вы можете сделать
x += if (a < b) 1 else 0
который должен распознать интеллектуальный JVM, такой же, как x + = (a < b), который имеет переход от машинного кода без скачка, который обычно быстрее, чем прыжок. Еще более разумная JVM распознает, что
if (a < b) x += 1
то же самое снова (потому что добавление нуля ничего не делает).
Компиляторы C/С++ обычно выполняют такие оптимизации. Невозможность применить любую из этих оптимизаций не была отмечена в пользу компилятора JIT; по-видимому, он может быть равен 1,7, но только частично (то есть он не признает, что добавление нуля такое же, как условное добавление одного, но оно, по крайней мере, преобразует x += if (a<b) 1 else 0 в быстрый машинный код).
Теперь ничто из этого не имеет ничего общего с хвостовой рекурсией или циклами как таковыми. С рекурсией хвоста более естественно писать форму if (a < b) 1 else 0, но вы можете это сделать; и с помощью циклов while вы также можете сделать это. Так получилось, что вы выбрали одну форму для хвостовой рекурсии, а другую для цикла while, что делает ее похожей на рекурсию и на цикл. Это изменение вместо двух разных способов сделать условные обозначения.
