Clojure가 재귀 적 추가 기능에서 Scala보다 훨씬 빠른 이유는 무엇입니까?

Question

친구가

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

Clojure의

나에게이 코드를주고 그것을 유사한 스칼라 구현에 대한 요금을 어떻게하는지 나에게 물었다. 이 같은

스칼라 코드 내가 작성한 외모 :

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메가바이트 이하 사용 약 12 초 만에 실행되며 512MB의 힙만 있으면 충분하지 않습니다 (힙을 1GB로 설정하면 계산이 완료됩니다).

그래서이 특별한 경우에 왜 Clojure가 훨씬 빠르고 슬림하게되어 있는지 궁금합니다. 속도와 메모리 사용면에서 비슷한 동작을하는 스칼라 구현이 있습니까?

종교적 비평을 삼가 해주십시오. 제 관심 사항은 무엇보다도이 경우 clojure를 매우 빨리 만드는 것이고, 스칼라에서 알 고의 구현이 더 빠르다는 것입니다. 감사.

Answer 1

첫째, 스칼라은 당신이 -optimise로 호출하면 꼬리 호출을 최적화합니다. 편집 : 가능하다면 스칼라는 꼬리 호출 재귀를 최적화 할 것입니다. -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") 
} 

정상 실행 :

대신 " iterator"의 " elements"해야하고, 더 " tailrec"주석이 없습니다 스칼라 2.7에

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

- 이 주석은 꼬리 재귀를 사용하여 정의를 최적화 할 수없는 경우 불평하기 위해 사용됩니다. 따라서 코드에서 "@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가 tail-cail 최적화를 처리하는 방법 때문일 것으로 생각됩니다. JVM은 기본적으로이 최적화를 수행하지 않으므로 Clojure는 recur 키워드를 사용하여 테일 재귀를 최적화합니다. Clojure site에서 : 함수형 언어에서

루핑 및 반복은 재귀 함수 호출을 통해 구현/대체됩니다. 많은 그러한 언어는 꼬리 위치에서 호출이 스택 공간을 소비하지 않으므로 스택 공간을 보장하므로 반복 루프는 상수 공간을 사용합니다. Clojure는 Java 호출 규칙을 사용하므로 은 동일한 테일 호출 최적화를 보장하지 못합니다. 대신 은 재귀 특수 연산자 을 제공합니다.이 연산자는 상수 공간 재귀 을 반복하고 에 가장 근접한 루프 또는 함수 프레임으로 점프하여 루프를 반복합니다. 꼬리 호출 최적화와 같은 일반적인 것은 아니지만 같은 우아한 구문을 허용하고 은 호출이 recur에 꼬리 위치에서만 발생할 수 있는지 확인하는 이점을 제공합니다.

편집 : Scala optimizes tail calls also (특정 양식에있는 경우). 그러나 이전 링크에서 볼 수 있듯이 Scala는 매우 간단한 경우에만 이렇게 할 수 있습니다.

실제로 이것은 꼬리 호출 최적화라는 스칼라 컴파일러의 기능입니다. 은 재귀 호출을 최적화합니다. 이 기능은 위에서와 같이 간단한 경우에만 작동합니다 ( ). 재귀가 간접적 인 경우, 예를 들어 스칼라는 제한된 JVM 명령어 세트 때문에 꼬리 호출을 최적화 할 수 없습니다. 실제로 생성되는 것을 JVM 지침보고 컴파일 및 디 컴파일 코드없이

, 나는 (마이클 넣어으로 인해 각 재귀 단계에 a.tail를 가져 데,) 그냥 그 간단한 경우이 아닌 하나의 의심 때문에 스칼라는 그것을 최적화 할 수 없다.

Answer 3

이 예제에 대한 프로파일을 작성한 결과, 클래스 Stream (잘 ... 일부 익명 함수 - visualvm이 나를 추락 한 것처럼 깜박임)이 대부분의 힙을 차지합니다. 스칼라의 Stream에 누설 메모리가 있다는 사실과 관련이 있습니다 ( Scala TraC#692 참조). Scala 2.8에서 수정되었습니다. . 편집 :Daniel의 코멘트는이 버그와 관련이 없다고 올바르게 지적했다. "val ints이 스트림 헤드를 가리키고 있으며 가비지 수집기가 아무 것도 수집 할 수 없기 때문에"[Daniel]입니다. 이 질문과 관련하여이 버그 보고서의 주석을 읽는 것이 좋다고 생각했습니다.

추가 기능에서 a.head에 대한 참조를 보유하고 있으므로 가비지 수집기가 헤드를 수집 할 수 없으므로 GC 편집 할 수없는 끝에 9999998 개의 요소가있는 스트림이됩니다.

당신은 또한 당신이 통과 계속 꼬리의 사본을 보관 할 수있다 [A 약간의 간주곡]

, 내가 아니에요 확인하는 방법 그와 Stream의 거래. 목록을 사용하려는 경우 꼬리는 이 아니고이 복사됩니다. 예를 들면 다음과 같습니다

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

, 모두 ys 및 zs '공유'같은 꼬리, 적어도 힙 현명한 ( ys.tail eq zs.tail, 일명 평등 수익률 true 참조).

가 실행되는 (

대안 구현 [이 작은 막간는 꼬리를 많이 통과하는 것은 원칙적으로 정말 나쁜 일이 :), 그들은 적어도 목록에 대한, 복사되지 않습니다하지 않은 점을 만드는 것이 었습니다] 매우 빠르고, 나는 그것이 순수한 기능보다 더 명확하다고 생각)을 필수 접근 방식을 사용하는 것입니다 : 스칼라에서는 성능과 선명도 (적어도에 들어, 필수 방법을 사용하는 것은 매우 OK입니다

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

scala> addTo(9999998, 0) 

나, add의이 버전은 그 의도에 더 분명하다). 그것은 완전히 기능으로 더욱 간결를 들어, 당신도

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

가 (조금 느리게,하지만 여전히 합리적인 실행하고 메모리를 폭파하지 않습니다) 내가 Clojure에 빨리 될 수 있다고 생각

쓸 수 따라서 Scala (기능적, OO 및 필수)가 혼합 된 것보다 더 많은 최적화가 가능합니다. 나는 Clojure에 익숙하지 않다.

희망이 도움이 :)

는

Answer 4

Clojure의 범위는 메모하지 않으며, Scala 's Stream 않습니다. 전혀 다른 결과를 가진 전혀 다른 데이터 구조. 스칼라는 Non Memoizing 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 

스칼라에 대한 직역이 몇 가지 코드를 작성하는 나를 필요로 얻을

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 범위를 필요 것을 "추가"에서 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) 
} 

직접 다음과 스칼라의 표준 라이브러리의 범위를 사용하여 동일한 상자

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

에 Clojure에서의 그것보다 배 더 빠르게 배로 굴러 라. 단순한 원시 재귀만큼 빠르지는 않지만 코드가 적고 Clojure 재귀 버전보다 빠릅니다 (적어도 내 상자에서).

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

memoized 스트림

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