Dlaczego Clojure jest znacznie szybszy niż Scala w rekurencyjnej funkcji dodawania?

Question

Znajomy dał mi ten fragment kodu w Clojure

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

i zapytał mnie, jak to taryfy przed podobnym realizacji Scala.

Kod Scala I zostały napisane wygląda następująco:

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

Konkluzja jest: kodu w Clojure działa w około 1,8 sekundy na moim komputerze i używa mniej niż 5 MB sterty, kod w Scala działa w około 12 sekund, a 512 MB sterty nie wystarcza (kończy obliczenia, jeśli ustawię stertę na 1GB).

Więc zastanawiam się, dlaczego Clojure jest o wiele szybszy i szczuplejszy w tym konkretnym przypadku? Czy masz implementację Scala, która ma podobne zachowanie pod względem szybkości i wykorzystania pamięci?

Proszę powstrzymać się od uwag religijnych, moje zainteresowanie polega przede wszystkim na tym, aby dowiedzieć się przede wszystkim, co powoduje, że clojure jest tak szybki w tym przypadku i czy istnieje szybsza implementacja algo w scala. Dzięki.

Answer 1

Najpierw Scala optymalizuje tylko ogon wywołuje jeśli powołać go -optimise. Edycja: Wygląda na to, że Scala zawsze zoptymalizuje rekursje wywołań ogłaszanych, nawet jeśli nie, nawet bez -optimise.

Po drugie, Stream i Range to dwie różne rzeczy. A Range ma początek i koniec, a jego rzut ma tylko licznik i koniec. A Stream to lista, która zostanie obliczona na żądanie. Ponieważ dodajesz cały numer ints, będziesz obliczać, a zatem przydzielać całość Stream.

Bliższa kod byłoby:

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

Normalny bieg:

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

Na Scala 2.7 trzeba "elements" zamiast "iterator" i nie ma "tailrec" adnotacji - ta adnotacja jest używana tylko do narzekania, jeśli definicji nie można zoptymalizować za pomocą rekurencji ogona - musisz więc usunąć z kodu kod "@tailrec" i "import scala.annotation.tailrec".

Kilka uwag dotyczących alternatywnych implementacji. Najprostszy:

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

W przypadku wielu przebiegów tutaj jest on wolniejszy. Jest również niepoprawny, ponieważ działa tylko z Int. Prawidłowy:

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

To jeszcze wolniej, działa tutaj. Szczerze mówiąc, nie spodziewałbym się, że będzie wolniej, ale każda interakcja wymaga przekazania funkcji. Kiedy już to rozważysz, jest to całkiem dobry czas w porównaniu z wersją rekursywną.

Answer 2

Podejrzewam, że wynika to z tego, w jaki sposób Clojure obsługuje optymalizacje ogona. Ponieważ JVM nie wykonuje natywnie tej optymalizacji (i zarówno Clojure, jak i Scala działają na niej), Clojure optymalizuje rekursję ogona za pomocą słowa kluczowego recur. Z Clojure site:

W językach funkcjonalnych pętli i iteracja zastępuje/realizowane poprzez rekurencyjnych wywołań funkcji. Wiele takich języków gwarantuje, że wywołania funkcji w pozycji końcowej nie zajmują miejsca w stosie, a zatem pętle rekurencyjne wykorzystują stałą przestrzeń . Ponieważ Clojure używa konwencji wywoływania Java , nie może, a tego nie robi, zapewnia tę samą gwarancję optymalizacji pod numerem . Zamiast tego, zapewnia powtarzalny operator specjalny, , który wykonuje pętlę o stałej przestrzeni rekurencyjnej przez ponowne wiązanie i przeskok do najbliższej otaczającej pętli lub funkcji ramki. Choć nie tak ogólnie jak ogona zadzwonić optymalizacji, pozwala to najbardziej tych samych eleganckich konstrukcji i ma tę zaletę, że sprawdzanie połączeń do nawrotów może zdarzyć się tylko w pozycji ogonowej.

EDYCJA: Scala optimizes tail calls also, o ile są w określonej formie. Jednak, jak pokazuje poprzedni link, Scala może to zrobić tylko w bardzo prostych przypadkach:

W rzeczywistości jest to funkcja kompilatora Scala zwana optymalizacją wywołania ogona. To optymalizuje z dala wywołanie rekurencyjne. Ta funkcja działa tylko w prostych przypadkach, jak wyżej, . Jeśli rekursja jest pośrednia, na przykład Scala nie może zoptymalizować wywołań końcowych, z powodu ograniczonego zestawu instrukcji JVM.

Bez faktycznie kompilacji i decompiling kod, aby zobaczyć, co JVM instrukcje są produkowane, podejrzewam, że po prostu nie jest jedna z tych prostych przypadkach (jak Michael ujął, z powodu konieczności pobierania a.tail na każdym rekurencyjnym kroku), a tym samym Scala po prostu nie może tego zoptymalizować.

Answer 3

Profilowałam Twój przykład i wydaje mi się, że klasa Stream (no cóż ... jakaś anonimowa funkcja z nim związana - zapomniała o swojej nazwie, gdy na mnie spadł visualvm) zajmuje większość sterty. Jest to związane z faktem, że Stream s w Scala do wycieku pamięci - patrz Scala TraC#692. Poprawki są wymagane w Scali 2.8. . EDYCJA:Daniel - słusznie zauważyłem, że nie jest on związany z tym błędem. Dzieje się tak, ponieważ "val ints wskazuje na głowicę Stream, garbage collector nic nie zbiera" [Daniel]. Uważam, że komentarze w tym raporcie błędów są miłe do przeczytania w związku z tym pytaniem.

W swojej funkcji dodawania odwołujesz się do a.head, w związku z czym śmieciarz nie może zebrać głowy, prowadząc do strumienia zawierającego 9999998 elementów na końcu, którego nie można edytować GC.

[A mały przerywnik]

Można również przechowywać kopie ogonów zachować przechodząc jestem nie pewny jak Stream s sobie z tym poradzić. Jeśli chcesz użyć listy, ogony będą kopiowane w postaci , a nie. Np

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

Tutaj zarówno ys i zs „część” samo ogon, co najmniej sterty zegara (ys.tail eq zs.tail aka odniesienie wydajności równości true).

[Ten mały przerywnik było uczynienie tego stopnia, że ​​przechodząc wiele ogony nie jest naprawdę źle :) w zasadzie nie są one kopiowane, przynajmniej dla list]

Alternatywna realizacja (która biegnie dość szybko, i myślę, że jest to bardziej oczywiste niż czysta jednej funkcjonalnej) jest użycie imperatyw podejście:

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

scala> addTo(9999998, 0) 

W Scala jest całkiem OK, aby użyć podejście imperatywne, pod kątem wydajności i przejrzystości (przynajmniej ja, ta wersja add jest bardziej zrozumiała dla jej intencji). Dla jeszcze większej zwięzłości, można nawet napisać

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

(przebiega nieco wolniej, ale nadal rozsądne i nie dmuchać pamięć up)

wierzę, że Clojure może być szybciej, ponieważ jest to w pełni funkcjonalny , dlatego możliwa jest większa optymalizacja niż w Scali (która łączy funkcjonalność, OO i imperatyw). Jednak nie jestem zaznajomiony z Clojure.

Nadzieja to pomaga :)

Answer 4

Zasięg Clojure nie zapamiętuje, działa Strumień Scali. Zupełnie inne struktury danych z zupełnie innymi wynikami. Scala ma niezmienną strukturę Range, ale jest to rodzaj awkarda do pracy z tym prostym rekurencyjnym sposobem. Oto moje podejście do wszystkiego.

Korzystanie Clojure 1.0 na starszych skrzynki, która jest wolna, mam 3,6 sekundy

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 

Dosłowne tłumaczenie do Scala wymaga mnie napisać trochę kodu

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 
} 

Dobrze jest upewnić się, to się zgadza

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

Teraz potrzebujemy niezmordowanego Zasięgu z podobną semantyczną s do Clojure za

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

Od że "dodatek" wynika bezpośrednio

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

i to czasy znacznie szybciej niż Clojure jest na tym samym polu

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

użyciu standardowych Zakres biblioteki Scala, można złożyć. Nie jest tak szybki, jak prosty prymitywny rekurencji, ale jego mniej kodu i nadal szybciej niż wersja rekurencyjna Clojure (przynajmniej na moim polu).

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

Kontrast z fałd nad memoized Stream

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