Почему моя хвостовая рекурсия Scala быстрее, чем цикл while? - PullRequest
Новая
       6

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

35 голосов
/ 07 февраля 2012

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

Time = 245.110899 millis
(50004367,2003090,47992543)
Time = 465.836894 millis
(50004367,2003090,47992543)

Почему метод while намного медленнее, чем tailrec?На первый взгляд, версия tailrec выглядит слегка неудобной, поскольку она всегда должна выполнять 3 проверки «if» для каждой итерации, тогда как версия while часто выполняет только 1 или 2 теста из-за конструкции else.(Примечание: обратный порядок, в котором я выполняю два метода, не влияет на результат).

Ответы [ 2 ]

36 голосов
/ 07 февраля 2012

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

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

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

Так что в Java 6 ваш цикл while на самом деле быстрее; оба улучшили производительность под 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 (HotSpot) может оптимизировать это лучше, чем ваша первая версия, но я предполагаю, что это потому, что она каждый раз проходит по одному и тому же пути через код (а не разветвляется вдоль if / else if путей), поэтому байт-код может быть встроен более эффективно.

Но помните, что это не так в Java 6. Почему один цикл while выигрывает у другого, это вопрос внутренних функций JVM. К счастью для программиста Scala, версия, созданная на основе идиоматической хвостовой рекурсии, является более быстрой в последней версии JVM.

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

24 голосов
/ 07 февраля 2012

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

Итак, если у вас есть код, похожий на 

if (a < b) x += 1

, где вы можете добавить или вы можете вместо этого, вместо 

x += (a < b)

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

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

, который должна распознавать умная JVM, и x + = (a 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, создавая впечатление, что рекурсия вместо цикла была изменением, а не двумя различными способами выполнения условий.

...