Подтвердить что ты не робот

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

Друг дал мне этот фрагмент кода в 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. Спасибо.

4b9b3361

ОТВЕТЫ

Ответ 1

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

Во-вторых, Stream и Range - две разные вещи. A Range имеет начало и конец, а его проекция имеет только счетчик и конец. A 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

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

Ответ 2

Clojure диапазон не memoize, Scala Stream. Совершенно разные структуры данных с совершенно разными результатами. Scala имеет не memoizing структуру Range, но в настоящее время это своего рода awkard для работы с этим простым рекурсивным способом. Здесь я беру на себя все это.

Используя 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

Теперь нам нужен unmemoized 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)
}

Из этого "add" следует непосредственно

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, вы можете сделать сгиб. Это не так быстро, как простая примитивная рекурсия, но ее меньший код и еще быстрее, чем рекурсивная версия Clojure (по крайней мере, на моем ящике).

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

Контрастность со сгибом поверх memoized Stream

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

Ответ 3

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

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

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

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

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

Ответ 4

Профилируйте этот пример, и кажется, что класс Stream (ну... какая-то анонимная функция, связанная с ним - забыли свое имя, как авария на меня врезалась) занимает большую часть кучи. Это связано с тем, что Stream в Scala делает утечку памяти - см. Scala TraС# 692. Исправления должны выполняться в Scala 2.8.. EDIT: Daniel комментарий правильно указал, что он не связан с этой ошибкой. Это потому, что "val ints указывает на заголовок потока, сборщик мусора не может ничего собирать" [Daniel]. Я нашел комментарии в этом отчете об ошибках приятно читать, хотя по этому вопросу.

В вашей функции добавления вы держите ссылку на 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.

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