¿Por qué Clojure es mucho más rápido que Scala en una función de adición recursiva?

performance tail-recursion

Question

Un amigo me dio este fragmento de código en Clojure

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

y me preguntó cómo le va contra una implementación de Scala similar.

El código de Scala que he escrito se ve así:

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")

La conclusión es: el código en Clojure se ejecuta en aproximadamente 1,8 segundos en mi máquina y utiliza menos de 5 MB de capacidad, el código en Scala se ejecuta en aproximadamente 12 segundos y 512 MB de capacidad no son suficientes (finaliza el cálculo si configuro el montón a 1GB).

Entonces, me pregunto por qué Clojure es mucho más rápido y más delgado en este caso particular. ¿Tiene una implementación de Scala que tenga un comportamiento similar en términos de velocidad y uso de la memoria?

Por favor, absténgase de hacer comentarios religiosos, mi interés radica en averiguar qué hace que Clojure sea tan rápido en este caso y si hay una implementación más rápida del algoritmo in scala. Gracias.

Answer 1

El rango de Clojure no se memoriza, Scala''s Stream sí. Estructuras de datos totalmente diferentes con resultados totalmente diferentes. Scala tiene una estructura Range sin memoria, pero actualmente es un poco incómodo trabajar de esta manera recursiva simple. Aquí está mi opinión sobre todo.

Usando Clojure 1.0 en una caja anterior, que es lenta, obtengo 3.6 segundos

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

Una traducción literal a Scala requiere que escriba algún código

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
}

Es bueno asegurarse de que sea correcto

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

Ahora necesitamos un Rango sin memoria con una semántica similar a la de 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)
}

De ese "agregar" sigue directamente

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

Y es mucho más rápido que Clojure en la misma caja

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

Utilizando el rango de biblioteca estándar de Scala, puede hacer un doblez. No es tan rápido como la simple recursión primitiva, pero es menos código y aún más rápido que la versión recursiva de Clojure (al menos en mi caja).

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

Contraste con un pliegue sobre una secuencia memorable

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

Answer 2

Perfilado este ejemplo tuyo y parece que la clase Stream (bueno ... alguna función anónima relacionada con ella - olvidó su nombre cuando visualvm se estrelló contra mí) ocupa la mayor parte del montón. Está relacionado con el hecho de que Stream s en Scala sí tiene pérdida de memoria - ver Scala Trac # 692 . Las reparaciones vencen en Scala 2.8. . EDITAR: El comentario de Daniel correctamente señaló que no está relacionado con este error. Es porque " val ints apunta a la cabeza de Stream, el recolector de basura no puede recoger nada" [ Daniel ]. Sin embargo, encontré los comentarios en este informe de error agradables de leer en relación con esta pregunta.

En su función de agregar, está manteniendo una referencia a a.head , por lo tanto, el recolector de elementos no utilizados no puede recopilar la cabecera, lo que lleva a una secuencia que contiene 9999998 elementos al final, que no se pueden editar por GC.

[Un pequeño interludio]

También puedes guardar copias de las colas que sigues pasando, no estoy seguro de cómo se relaciona Stream con eso. Si usara una lista, las colas no se copiarían. Por ejemplo:

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

Aquí, tanto ys como zs ''comparten'' la misma cola, al menos en forma de pila ( ys.tail eq zs.tail , también conocida como igualdad de referencia, es true ).

[Este pequeño interludio fue para aclarar que pasar muchas colas no es algo realmente malo en principio :), no se copian, al menos para las listas]

Una implementación alternativa (que funciona bastante rápido, y creo que es más clara que la funcional pura) es usar un enfoque imperativo:

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

scala> addTo(9999998, 0)

En Scala, está bastante bien utilizar un enfoque imperativo, para el rendimiento y la claridad (al menos para mí, esta versión de add es más clara para su intención). Para aún más concisión, incluso podrías escribir

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

(funciona un poco más lento, pero sigue siendo razonable y no arruina la memoria)

Creo que Clojure podría ser más rápido ya que es completamente funcional, por lo tanto, es posible realizar más optimizaciones que con Scala (que combina funcional, OO e imperativo). Aunque no estoy muy familiarizado con Clojure.

Espero que esto ayude :)

Answer 3

Primero, Scala solo optimiza las llamadas -optimise si lo -optimise con -optimise . Editar : parece que Scala siempre optimizará las recurrencias de cola si puede, incluso sin -optimise .

En segundo lugar, Stream y Range son dos cosas muy diferentes. Un Range tiene un principio y un final, y su proyección tiene solo un contador y el final. A Stream es una lista que se computará a pedido. Como está agregando todos los ints , calculará y, por lo tanto, asignará la Stream completa.

Un código más cercano sería:

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")
}

Ejecución normal:

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

En Scala 2.7 necesitas " elements " en lugar de " iterator ", y no hay tailrec anotación " tailrec ": esa anotación se usa solo para quejarse si una definición no se puede optimizar con recursividad de cola, por lo que necesitarás desnudarla " @tailrec ", así como la " import scala.annotation.tailrec " del código.

Además, algunas consideraciones sobre implementaciones alternativas. Lo más simple:

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

En promedio, con varias ejecuciones aquí, es más lento. También es incorrecto, porque funciona solo con Int. Una correcta

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

Eso es más lento aún, corriendo aquí. Honestamente, no esperaba que funcionara más lento, pero cada interacción llama a la función que se pasa. Una vez que lo consideras, es un buen momento en comparación con la versión recursiva.

Answer 4

Sospecho que se debe a cómo Clojure maneja las optimizaciones de tail-cail. Dado que la JVM no realiza esta optimización de forma nativa (y Clojure y Scala se ejecutan en ella), Clojure optimiza la recursividad final a través de la palabra clave recur . Desde el sitio de Clojure :

En los lenguajes funcionales, el bucle y la iteración se reemplazan / implementan mediante llamadas de funciones recursivas. Muchos de estos lenguajes garantizan que las llamadas de función realizadas en posición de cola no consuman espacio de pila, y por lo tanto, los bucles recursivos utilizan espacio constante. Como Clojure usa las convenciones de llamadas de Java, no puede, y no hace, las mismas garantías de optimización de llamadas de cola. En cambio, proporciona el operador especial de recurrencia, que realiza un bucle recursivo de espacio constante volviendo a vincular y saltando al bucle delimitador o al marco de función más cercano. Aunque no es tan general como la optimización de la cola de llamada, permite la mayoría de los mismos constructos elegantes, y ofrece la ventaja de verificar que las llamadas recurrentes solo pueden ocurrir en una posición de cola.

EDITAR: Scala optimiza las llamadas finales también , siempre que estén en una determinada forma. Sin embargo, como muestra el enlace anterior, Scala solo puede hacer esto para casos muy simples:

De hecho, esta es una característica del compilador de Scala llamada optimización de llamadas de cola. Optimiza la llamada recursiva. Sin embargo, esta característica solo funciona en casos simples como el anterior. Si la recursión es indirecta, por ejemplo, Scala no puede optimizar las llamadas finales, debido al conjunto limitado de instrucciones de JVM.

Sin realmente compilar y descompilar tu código para ver qué instrucciones JVM se producen, sospecho que simplemente no es uno de esos casos simples (como dijo Michael, debido a tener que buscar una a.tail en cada paso recursivo) y por lo tanto Scala simplemente puede '' t optimizarlo.