Tại sao Clojure nhanh hơn Scala một hàm đệ quy?

Question

Một người bạn đã cho tôi đoạn mã này trong Clojure

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

và hỏi tôi làm thế nào nó giá vé đối với việc thực hiện Scala tương tự.

vẻ Mã Scala Tôi đã viết như thế này:

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

Điểm mấu chốt là: mã trong Clojure chạy trong khoảng 1,8 giây trên máy tính của tôi và sử dụng ít hơn 5MB của heap, mã trong Scala chạy trong khoảng 12 giây và 512MB đống không đủ (nó kết thúc tính toán nếu tôi đặt heap thành 1GB).

Vì vậy, tôi tự hỏi tại sao Clojure nhanh hơn và mỏng hơn nhiều trong trường hợp cụ thể này? Bạn có thực hiện Scala có hành vi tương tự về tốc độ và mức sử dụng bộ nhớ không?

Xin vui lòng không nhận xét tôn giáo, quan tâm của tôi nằm trong việc tìm ra chủ yếu những gì làm cho clojure quá nhanh trong trường hợp này và nếu có một thực hiện nhanh hơn của algo trong scala. Cảm ơn.

Answer 1

Thứ nhất, Scala chỉ tối ưu hóa đuôi gọi nếu bạn gọi nó với -optimise. Chỉnh sửa: Có vẻ như Scala sẽ luôn tối ưu hóa việc thu thập cuộc gọi đuôi nếu có thể, ngay cả khi không có -optimise.

Thứ hai, Stream và Range là hai điều rất khác nhau. Một Range có một sự bắt đầu và kết thúc, và chiếu của nó chỉ có một truy cập và kết thúc. A Stream là danh sách sẽ được tính theo yêu cầu. Vì bạn đang thêm toàn bộ ints, bạn sẽ tính toán, và do đó, phân bổ, toàn bộ Stream.

Mã gần sẽ là:

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

Bình thường chạy:

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

On Scala 2,7 bạn cần "elements" thay vì "iterator", và không có "tailrec" chú thích - chú thích được sử dụng chỉ để khiếu nại nếu một định nghĩa không thể được tối ưu hóa với đệ quy đuôi - vì vậy bạn sẽ cần phải cắt "@tailrec" cũng như "import scala.annotation.tailrec" từ mã.

Ngoài ra, một số cân nhắc về triển khai thay thế. Đơn giản nhất:

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

Trung bình, với nhiều lần chạy ở đây, nó chậm hơn. Nó cũng không chính xác, bởi vì nó hoạt động chỉ với Int. Mã đúng:

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

Vẫn chạy chậm hơn tại đây. Tôi thành thật sẽ không có dự kiến ​​nó chạy chậm hơn, nhưng mỗi cuộc gọi interation đến chức năng được thông qua. Một khi bạn xem xét điều đó, đó là một thời gian khá tốt so với phiên bản đệ quy.

Answer 2

Tôi nghi ngờ đó là cách Clojure xử lý tối ưu hóa đuôi cail. Vì JVM không thực sự thực hiện tối ưu hóa này (và cả Clojure và Scala chạy trên nó), Clojure tối ưu hóa việc đệ quy đuôi thông qua từ khóa recur. Từ Clojure site:

Trong các ngôn ngữ chức năng lặp và lặp được thay thế/thực hiện thông qua gọi hàm đệ quy. Nhiều ngôn ngữ như vậy đảm bảo rằng chức năng cuộc gọi được thực hiện ở vị trí đuôi không tiêu thụ không gian ngăn xếp, và do đó vòng đệ quy sử dụng không đổi không gian. Vì Clojure sử dụng Java các quy ước gọi điện, nó không thể, và không, thực hiện cùng một cuộc gọi đuôi đảm bảo tối ưu hóa. Thay vào đó, nó cung cấp toán tử đặc biệt recur, lặp lại không gian liên tục lặp lại bằng cách bật lại và nhảy tới vòng lặp kèm theo hoặc hàm gần nhất. Mặc dù không chung chung là tối ưu hóa cuộc gọi đuôi, nó cho phép hầu hết các cấu hình thanh lịch và và cung cấp lợi thế kiểm tra rằng các cuộc gọi lặp lại chỉ có thể xảy ra ở vị trí đuôi .

CHỈNH SỬA: Scala optimizes tail calls also, miễn là chúng ở một dạng nhất định. Tuy nhiên, như liên kết trước đây cho thấy, Scala chỉ có thể thực hiện việc này cho các trường hợp rất đơn giản:

Thực tế, đây là tính năng của trình biên dịch Scala được gọi là tối ưu hóa cuộc gọi đuôi. Nó tối ưu hóa cuộc gọi đệ quy. Tính năng này chỉ hoạt động trong các trường hợp đơn giản như trên, . Nếu đệ quy là gián tiếp, ví dụ, Scala không thể tối ưu hóa các cuộc gọi đuôi, vì tập lệnh JVM giới hạn.

Nếu không thực sự biên soạn và dịch ngược mã của bạn để xem những gì hướng dẫn JVM được sản xuất, tôi nghi ngờ nó chỉ là không nằm trong số những trường hợp đơn giản (như Michael đặt nó, do phải lấy a.tail trên mỗi bước đệ quy) và do đó Scala không thể tối ưu hóa nó.

Answer 3

Đã lập cấu hình ví dụ này của bạn và có vẻ như lớp Stream (cũng ... một số chức năng ẩn danh liên quan đến nó - quên tên của nó là hình ảnh bị rơi vào tôi) chiếm phần lớn vùng heap. Nó liên quan đến thực tế là Stream s trong Scala làm rò rỉ bộ nhớ - xem Scala TraC#692. Bản sửa lỗi là do Scala 2.8. . EDIT:Daniel bình luận của đúng chỉ ra rằng nó không liên quan đến lỗi này. Đó là vì "val ints điểm đến đầu Luồng, trình thu gom rác không thể thu thập bất kỳ thứ gì" [Daniel]. Tôi tìm thấy các ý kiến ​​trong báo cáo lỗi này tốt đẹp để đọc mặc dù, liên quan đến câu hỏi này.

Trong chức năng thêm, bạn đang giữ tham chiếu đến a.head, do đó trình thu gom rác không thể thu thập đầu, dẫn đến luồng chứa 9999998 phần tử cuối cùng, không thể là GC-ed.

[A Interlude ít]

Bạn cũng có thể giữ bản sao của đuôi bạn giữ đi, tôi không chắc chắn cách Stream s thỏa thuận với điều đó. Nếu bạn sử dụng danh sách, các đuôi sẽ không phải được sao chép. Ví dụ:

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

Ở đây, cả hai ys và zs 'chia sẻ' đuôi giống nhau, ít nhất là đống khôn ngoan (ys.tail eq zs.tail, aka tham khảo sản lượng bình đẳng true).

[Interlude nhỏ này là để làm cho thời điểm đó đi qua rất nhiều đuôi không phải là một điều thực sự tồi tệ về nguyên tắc :), họ không được sao chép, ít nhất là cho các danh sách]

An thực hiện thay thế (mà chạy khá nhanh, và tôi nghĩ rằng đó là rõ ràng hơn một chức năng thuần túy) là sử dụng một cách tiếp cận bắt buộc:

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

scala> addTo(9999998, 0) 

Trong Scala nó là khá OK để sử dụng một cách tiếp cận bắt buộc, cho hiệu suất và độ rõ nét (ít nhất là tới tôi, phiên bản này của add rõ ràng hơn với ý định của nó). Đối với conciseness thậm chí nhiều hơn, thậm chí bạn có thể viết

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

(chạy chậm hơn một chút, nhưng vẫn hợp lý và không thổi nhớ lên)

Tôi tin rằng Clojure có thể nhanh hơn vì nó là đầy đủ chức năng , do đó tối ưu hóa nhiều hơn có thể so với Scala (mà pha trộn chức năng, OO và bắt buộc). Tôi không quen lắm với Clojure.

Hope this helps :)

Answer 4

Phạm vi của Clojure không ghi nhớ, Luồng của Scala thực hiện. Cấu trúc dữ liệu hoàn toàn khác nhau với kết quả hoàn toàn khác nhau. Scala không có cấu trúc Phạm vi không ghi nhớ, nhưng hiện tại nó rất khó để làm việc với cách đệ quy đơn giản này. Đây là của tôi về toàn bộ điều.

Sử dụng Clojure 1.0 trên một hộp lớn hơn, đó là chậm, tôi nhận được 3,6 giây

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 

dịch theo nghĩa đen để Scala đòi hỏi tôi phải viết một số mã

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 
} 

Đó là tốt để đảm bảo đó là đúng

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

Bây giờ chúng ta cần một phạm vi không đồng nhất với ngữ nghĩa tương tự s để Clojure của

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

Từ đó "add" sau trực tiếp

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

Và nó lần nhanh hơn nhiều so Clojure về cùng một hộp

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

Sử dụng Phạm vi thư viện chuẩn của Scala, bạn có thể làm một lần. Nó không nhanh như đệ quy nguyên thủy đơn giản, nhưng ít mã của nó và vẫn nhanh hơn phiên bản đệ quy Clojure (ít nhất là trên hộp của tôi).

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

Contrast với một lần so với một Stream memoized

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