Почему моя релаксация Scala быстрее, чем цикл while?

Question

Вот два решения для упражнений 4.9 в Scala Cay Horstmann для Impatient: «Напишите функцию lteqgt (значения: Array [Int], v: Int), которая возвращает тройку, содержащую подсчеты значений меньше v, равную v , и больше, чем v. " Один использует хвостовую рекурсию, другой - цикл while. Я думал, что оба будут скомпилированы для аналогичного байт-кода, но цикл while медленнее, чем хвостовая рекурсия, почти в 2 раза. Это говорит о том, что мой метод плохо написан.

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, изменяющий порядок, который я выполняю двумя способами, не влияет на результат).

Answer 1

Результаты испытаний (после уменьшения размера массива до 20000000)

Под Java 1.6.22 я получаю 151 and 122 ms для хвостовой рекурсии и пока контур соответственно.

Под Java 1.7.0 я получаю 55 and 101 ms

Так под Java 6 ваше время петли на самом деле быстрее; оба улучшены в производительности в Java 7, но хвостовая рекурсивная версия обогнала цикл.

Объяснение

разница в производительности из-за того, что в цикле, вы условно добавить 1 к итогам, в то время как для рекурсии вы всегда добавить либо 1 или 0. Таким образом, они не эквивалентны. Эквивалент в то время как петля для вашего рекурсивного метода:

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.

Разница также может возникать на уровне процессора. См. this question, в котором объясняется, как код замедляется, если он содержит непредсказуемое ветвление.

Answer 2

Эти две конструкции не идентичны. В частности, в первом случае вам не нужны какие-либо переходы (на x86 вы можете использовать cmp, setle и add, вместо того, чтобы использовать cmp и jb и (если вы не прыгаете) добавить.Не прыгать быстрее, чем прыгать практически в каждой современной архитектуре.

Итак, если у вас есть код, который выглядит как

if (a < b) x += 1 

где может добавить или может прыжок вместо этого, по сравнению с

x += (a < b) 

(который имеет смысл только в C/C++, где 1 = true и 0 = false), последний имеет тенденцию быть быстрее, поскольку его можно превратить в более компактный ассемблерный код. В Scala/Java, вы не можете сделать это, но вы можете сделать

x += if (a < b) 1 else 0 

которого умный JVM должен признать, такие же, как х + = (а < б), которая имеет скачок, свободный машинный перевод кода, который обычно быстрее, чем прыжки. Даже умнее JVM признают, что

if (a < b) x += 1 

это же еще раз (потому что добавление нуля ничего не делает).

Компиляторы C/C++ обычно выполняют такие оптимизации. Невозможность применить любую из этих оптимизаций не была отмечена в пользу компилятора JIT; по-видимому, он может быть равен 1,7, но только частично (то есть он не признает, что добавление нуля такое же, как условное добавление одного, но оно, по крайней мере, конвертирует x += if (a<b) 1 else 0 в быстрый машинный код).

Теперь ничто из этого не имеет ничего общего с рекурсией хвоста или в виде петель как таковой. С рекурсией хвоста более естественно написать форму if (a < b) 1 else 0, но вы можете сделать это; и с помощью циклов while вы также можете сделать это. Так получилось, что вы выбрали одну форму для хвостовой рекурсии, а другую для цикла while, заставив ее выглядеть как рекурсия против цикла, было изменение вместо двух разных способов выполнения условных обозначений.