Почему Clojure намного быстрее, чем Scala для рекурсивной функции добавления?

Question

Друг дал мне этот фрагмент кода в Clojure

(defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
(time (sum (range 1 9999999) 0))

и спросил меня, как обстоят дела с аналогичной реализацией Scala.

Код Scala, который я написал, выглядит следующим образом:

def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))
val ints = from(1).take(9999998)

def add(a: Stream[Int], b: Long): Long = {
    if (a.isEmpty) b else add(a.tail, b + a.head)
}

val t1 = System.currentTimeMillis()
println(add(ints, 0))
val t2 = System.currentTimeMillis()
println((t2 - t1).asInstanceOf[Float] + " msecs")

В итоге: код в Clojure выполняется на моей машине примерно за 1,8 секунды и использует менее 5 МБ кучи, код в Scala выполняется примерно за 12 секунд, а 512 МБ кучи недостаточно (он завершает вычисления, если Я установил кучу на 1 ГБ).

Так что мне интересно, почему Clojure намного быстрее и стройнее в данном конкретном случае? У вас есть реализация Scala, которая имеет похожее поведение с точки зрения скорости и использования памяти?

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

Answer 1

Во-первых, Scala оптимизирует только хвостовые вызовы, если вы вызываете его с помощью -optimise. Редактировать : Кажется, что Scala всегда будет оптимизировать рекурсии хвостового вызова, если это возможно, даже без -optimise.

Во-вторых, Stream и Range - две совершенно разные вещи. У Range есть начало и конец, а у его проекции есть только счетчик и конец. Stream - это список, который будет вычислен по требованию. Поскольку вы добавляете целое ints, вы вычисляете и, следовательно, выделяете целое Stream.

Более близкий код будет:

import scala.annotation.tailrec

def add(r: Range) = {
  @tailrec 
  def f(i: Iterator[Int], acc: Long): Long = 
    if (i.hasNext) f(i, acc + i.next) else acc

  f(r iterator, 0)
}

def time(f: => Unit) {
  val t1 = System.currentTimeMillis()
  f
  val t2 = System.currentTimeMillis()
  println((t2 - t1).asInstanceOf[Float]+" msecs")
}

Нормальный прогон:

scala> time(println(add(1 to 9999999)))
49999995000000
563.0 msecs

В Scala 2.7 вам нужно "elements" вместо "iterator", и нет аннотации "tailrec" - эта аннотация используется просто для того, чтобы пожаловаться, если определение не может быть оптимизировано с помощью хвостовой рекурсии - так что вам нужно убрать "@tailrec" и "import scala.annotation.tailrec" из кода.

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

scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs

В среднем при многократных пробегах здесь медленнее. Это также неверно, потому что он работает только с Int. Правильный:

scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs

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

Answer 2

Диапазон Clojure не запоминается, а поток Scala. Абсолютно разные структуры данных с совершенно разными результатами. Scala имеет не запоминающуюся структуру Range, но в настоящее время неудобно работать с этим простым рекурсивным способом. Вот мой взгляд на все это.

Используя Clojure 1.0 на старом боксе, который работает медленно, я получаю 3,6 секунды

user=> (defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
#'user/sum
user=> (time (sum (range 1 9999999) 0))
"Elapsed time: 3651.751139 msecs"
49999985000001

Буквальный перевод на Scala требует от меня написания кода

def time[T](x : => T) =  {
  val start = System.nanoTime : Double
  val result = x
  val duration = (System.nanoTime : Double) - start
  println("Elapsed time " + duration / 1000000.0 + " msecs")
  result
}

Хорошо убедиться, что это правильно

scala> time (Thread sleep 1000)
Elapsed time 1000.277967 msecs

Теперь нам нужен немеизированный Range с семантикой, аналогичной Clojure

.

case class MyRange(start : Int, end : Int) {
  def isEmpty = start >= end
  def first = if (!isEmpty) start else error("empty range")
  def rest = new MyRange(start + 1, end)
}

Из этого «добавления» следует непосредственно

def add(a: MyRange, b: Long): Long = {
    if (a.isEmpty) b else add(a.rest, b + a.first)
}

И это в разы быстрее, чем у Clojure на той же коробке

scala> time(add(MyRange(1, 9999999), 0))
Elapsed time 252.526784 msecs
res1: Long = 49999985000001

Используя стандартную библиотеку Scala Range, вы можете сделать фолд. Это не так быстро, как простая примитивная рекурсия, но она меньше кода и все же быстрее, чем рекурсивная версия Clojure (по крайней мере, на моем компьютере).

scala> time((1 until 9999999 foldLeft 0L)(_ + _))
Elapsed time 1995.566127 msecs
res2: Long = 49999985000001

Контраст со складкой над запоминанным потоком

time((Stream from 1 take 9999998 foldLeft 0L)(_ + _)) 
Elapsed time 3879.991318 msecs
res3: Long = 49999985000001

Answer 3

Профилировал этот ваш пример, и кажется, что класс Stream (ну ... какая-то анонимная функция, связанная с ним - забыл свое имя, так как visualvm обрушился на меня) занимает большую часть кучи. Это связано с тем, что Stream s в Scala имеют утечку памяти - см. Scala Trac # 692 . Исправления в Scala 2.8. . Комментарий EDIT: Daniel справедливо указывает на то, что он не связан с этой ошибкой. Это потому, что «val ints указывает на заголовок потока, сборщик мусора не может ничего собрать» [ Даниэль ]. Тем не менее, я нашел, что комментарии в этом сообщении об ошибке приятно читать в связи с этим вопросом.

В вашей функции добавления вы держите ссылку на a.head, поэтому сборщик мусора не может собрать заголовок, что приводит к потоку, который содержит 9999998 элементов в конце, который не может быть GC-ed.

[Маленькая интерлюдия]

Вы также можете хранить копии хвостов, которые продолжаете передавать, я не уверен, как Stream с этим справляются. Если бы вы использовали список, то хвосты не были бы скопированы. Например:

val xs =  List(1,2,3)
val ys = 1 :: xs
val zs = 2 :: xs

Здесь и ys, и zs 'разделяют' один и тот же хвост, по крайней мере, в куче (ys.tail eq zs.tail, то есть равенство эталонного равенства true).

[Эта небольшая интерлюдия состояла в том, чтобы показать, что прохождение большого количества хвостов в принципе не так уж и плохо :), они не копируются, по крайней мере, для списков]

Альтернативная реализация (которая работает довольно быстро, и я думаю, что она более понятна, чем чисто функциональная) - это использовать императивный подход:

def addTo(n: Int, init: Int): Long = {
  var sum = init.toLong
  for(i <- 1 to n) sum += i
  sum
}

scala> addTo(9999998, 0)

В Scala вполне нормально использовать императивный подход для производительности и ясности (по крайней мере, мне эта версия add более понятна для ее намерений). Для еще большей краткости вы можете написать

(1 to 9999998).reduceLeft(_ + _)

(работает немного медленнее, но все же разумно и не взрывает память)

Я считаю, что Clojure может быть быстрее, поскольку он полностью функционален, поэтому возможна большая оптимизация, чем в Scala (которая сочетает в себе функциональность, OO и императив). Хотя я не очень знаком с Clojure.

Надеюсь, это поможет:)

Answer 4

Я подозреваю, что это связано с тем, как Clojure выполняет оптимизацию хвостовой части. Поскольку JVM изначально не выполняет эту оптимизацию (и на ней работают и Clojure, и Scala), Clojure оптимизирует хвостовую рекурсию через ключевое слово recur. С сайта Clojure :

В функциональных языках циклы и итерация заменена / реализована через рекурсивные вызовы функций. Много таких языки гарантируют эту функцию звонки, сделанные в хвостовой позиции, не потреблять пространство стека, и, таким образом, рекурсивные циклы используют постоянные пространство. Поскольку Clojure использует Java вызывая соглашения, он не может, и нет, сделать тот же хвост гарантии оптимизации. Вместо этого обеспечивает повторный специальный оператор, который делает постоянное пространство рекурсивным цикл повторного связывания и прыжка к ближайший охватывающий цикл или функция Рамка. Хотя не так широко, как Оптимизация остаточного вызова позволяет из тех же элегантных конструкций, и предлагает преимущество проверки того, что призывы к повторению могут происходить только в положение хвоста.

EDIT: Scala также оптимизирует хвостовые вызовы , если они находятся в определенной форме. Однако, как показывает предыдущая ссылка, Scala может сделать это только для очень простых случаев:

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

Без фактической компиляции и декомпиляции вашего кода, чтобы увидеть, какие инструкции JVM произведены, я подозреваю, что это просто не один из тех простых случаев (как сказал Майкл, из-за необходимости извлекать a.tail на каждом рекурсивном шаге) и, следовательно, Scala просто не могу оптимизировать его.