Làm thế nào để viết chức năng đệ quy đuôi không bị rò rỉ bằng cách sử dụng Stream.cons trong Scala?

Question

Khi viết một hàm hoạt động trên Stream (s), có các khái niệm khác nhau về đệ quy. Ý nghĩa đơn giản đầu tiên là không đệ quy vào mức độ biên dịch, vì đuôi nếu không được đánh giá ngay lập tức để hàm trả về ngay lập tức, nhưng dòng trở lại là đệ quy:

final def simpleRec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else someB(a.head) #:: simpleRec(a.tail) 

Khái niệm trên của đệ quy không gây ra bất kỳ vấn đề . Điều thứ hai là thực sự đuôi-đệ quy vào mức độ biên dịch:

@tailrec 
final def rec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    // A) degenerated 
    else if (someCond) rec(a.tail)   // B) tail recursion 
    else someB(a.head) #:: rec(a.tail)  // C) degenerated 

Vấn đề ở đây là các trường hợp C) được phát hiện bởi trình biên dịch như một cuộc gọi không tailrec, thậm chí nếu không có cuộc gọi thực tế thực hiện. Điều này có thể tránh được bằng cách tính toán đuôi của luồng vào chức năng trợ giúp:

Trong khi biên dịch, phương pháp này cuối cùng dẫn đến rò rỉ bộ nhớ. Kể từ khi đệ quy đuôi rec cuối cùng được gọi từ hàm recHelp, khung ngăn xếp của hàm recHelp giữ tham chiếu đến đầu hơi nước và không để luồng được thu thập cho đến khi trả về cuộc gọi rec, có thể khá dài (về các bước đệ quy) tùy thuộc vào số lượng cuộc gọi đến B). Lưu ý rằng ngay cả trong trường hợp helperless, nếu trình biên dịch cho phép @ tailrec, rò rỉ bộ nhớ vẫn có thể có mặt vì đuôi luồng lười sẽ có hiệu lực tạo một đối tượng ẩn danh giữ tham chiếu đến đầu luồng.

Answer 1

Sự cố, như bạn đã gợi ý, là trong mã bạn đã dán chức năng lọcHelp giữ đầu (do đó giải pháp của bạn sẽ xóa nó).

Câu trả lời hay nhất là chỉ đơn giản là tránh hành vi đáng ngạc nhiên này, sử dụng Scalaz EphemeralStream và nhìn thấy cả hai không oom và chạy nhanh hơn đáng kể vì nó đẹp hơn rất nhiều so với gc. Không phải lúc nào cũng đơn giản để làm việc với ví dụ: head là một() => A không phải A, không có bộ giải nén v.v., nhưng tất cả đều hướng đến một mục tiêu sử dụng luồng đáng tin cậy.

chức năng filterHelper của bạn thường không nhất thiết phải quan tâm đến nếu nó giữ một tham chiếu xung quanh:

import scalaz.EphemeralStream 

@scala.annotation.tailrec 
def filter[A](s: EphemeralStream[A], f: A => Boolean): EphemeralStream[A] = 
    if (s.isEmpty) 
    s 
    else 
    if (f(s.head())) 
     EphemeralStream.cons(s.head(), filterHelp(s.tail() , f)) 
    else 
     filter(s.tail(), f) 

def filterHelp[A](s: EphemeralStream[A], f: A => Boolean) = 
    filter(s, f) 

def s1 = EphemeralStream.range(1, big) 

tôi muốn đi xa như vậy để nói rằng trừ khi bạn có một lý do thuyết phục để sử dụng Stream (khác thư viện phụ thuộc vv) sau đó chỉ cần dính vào EphemeralStream, có ít ngạc nhiên hơn ở đó.

Answer 2

Cách giải quyết có thể là thực hiện phương pháp recHelp không giữ tham chiếu đến đầu luồng. Điều này có thể đạt được bằng cách đi qua một dòng suối bọc cho nó, và biến đổi các wrapper để xóa các tài liệu tham khảo từ nó:

@tailrec 
final def rec[A](as: Stream[A]): Stream[B] = 
    if (a.isEmpty) Stream.empty    
    else if (someCond) rec(a.tail)   
    else { 
    // don't inline and don't define as def, 
    // or anonymous lazy wrapper object would hold reference 
    val tailRef = new AtomicReference(a.tail) 
    someB(a.head) #:: recHelp(tailRef) 
    } 

@tailrec 
final def recHelp[A](asRef: AtomicReference[Stream[A]]): Stream[B] = 
    // Note: don't put the content of the holder into a local variable 
    rec(asRef.getAndSet(null)) 

Các AtomicReference chỉ là sự tiện lợi, số nguyên tử là không cần thiết trong trường hợp này, bất kỳ đối tượng sở hữu đơn giản sẽ làm gì .

Cũng lưu ý rằng kể từ recHelp được gói trong một dòng Cons đuôi, do đó nó sẽ chỉ được đánh giá một lần và Cons cũng sẽ chăm sóc đồng bộ hóa.