Tại sao mã này hết bộ nhớ trong java, nhưng không phải trong c?

Question

Trong cả hai java hay c tôi có thể viết một hàm như

fun(){ 
    fun(); 
} 

(bỏ qua các chi tiết cú pháp)

Trong java tôi nhận được ngoại lệ OutOfMemory nhưng trong C (và có thể một số ngôn ngữ khác) có vẻ như để chạy mãi mãi , như thể đó là một vòng lặp vô hạn. Tại sao tôi không gặp lỗi OutOfMemory ở đây?

Answer 1

Vì chức năng của bạn là ví dụ về tail recursion, rất có thể, trình biên dịch C tối ưu hóa đệ quy để lặp lại, khiến cho vòng lặp vô hạn mà không bị lỗi.

Answer 2

Trong C, điều này có thể được tối ưu hóa như một cuộc gọi đệ quy đuôi. Vì vậy, các cuộc gọi đến fun() không thực sự gọi chính nó; nó chỉ khởi động lại chức năng (như một goto). Nói cách khác, trình biên dịch xử lý nó như thể nó đã được viết như thế này:

void fun() { 
start: 
    goto start; 
} 

Vì vậy, ngăn xếp sẽ không phát triển.

Answer 3

Lý do tại sao trình biên dịch C có khả năng coi đây là một cuộc gọi kéo theo đuôi và do đó tránh tạo một ngăn xếp để thực hiện hàm. Vì không có ngăn xếp được xây dựng cho các cuộc gọi nó quay từ đệ quy vào một thực hiện vòng lặp vô hạn đơn giản. Bạn có thể buộc nó xây dựng một ngăn xếp bằng cách làm cho nó đầu đệ quy

int fun() { 1 + fun(); } 

Answer 4

Bạn sẽ bị chấm dứt chương trình bất thường sau một thời gian. Mã của bạn chứa một đệ quy không xác định và mỗi cuộc gọi đến vui vẻ() đặt các byte bổ sung vào ngăn xếp. Tùy thuộc vào kích thước bộ nhớ và giới hạn của bạn, ứng dụng sẽ chấm dứt sau ít nhất một số cuộc gọi 500 triệu. Việc này có thể mất chút thời gian, nhưng bạn sẽ bị chấm dứt đặc biệt.

Máy ảo Java giới hạn độ sâu đệ quy đến một mức nào đó, do đó nó sẽ sớm chấm dứt.

Answer 5

Nếu triển khai ngôn ngữ lập trình có tail call optimization, thì nó sẽ biên dịch đệ quy đó thành vòng lặp. Máy ảo Java hiện tại không có tối ưu hóa cuộc gọi đuôi, vì vậy nó sẽ kết thúc bằng java.lang.StackOverflowError. Có lẽ một thời gian trong tương lai máy ảo Java sẽ có tối ưu hóa cuộc gọi đuôi, bởi vì các ngôn ngữ lập trình chức năng chạy trên JVM (Scala, Clojure, vv) sẽ được hưởng lợi từ nó (ngay bây giờ ít nhất là trình biên dịch Scala tối ưu hóa cuộc gọi đuôi cho direct recursion, nhưng AFAIK không cho đệ quy gián tiếp).

Answer 6

Trình biên dịch c của bạn có thể đang sử dụng tính năng đệ quy đuôi. Mỗi khi bạn nhập vào một chức năng mới, máy tính sẽ thêm một mục vào ngăn xếp. Mục này cho biết CPU sẽ chuyển về đâu sau khi thực hiện xong thủ tục. Bây giờ trong trường hợp được nêu ở trên, kể từ khi gọi đến fun() bên trong fun() là lời gọi cuối cùng trong hàm, trình biên dịch c có thể tối ưu hóa việc đẩy ngăn xếp và thay vào đó và tạo ra một tailcall. Bạn thực sự có thể sử dụng quyền này để tạo vòng lặp:

int foo(int from, int to) 
{ 
    if (from == to) return from; 
    dosomething(); 
    from ++; 
    foo(from, to); 
} 

Nhiều ngôn ngữ (ví dụ Erlang) không có vòng lặp nào và thay vào đó sử dụng phương pháp trên để tạo vòng lặp.

Java không hỗ trợ đệ quy đuôi.

Answer 7

Như những người khác đã chỉ ra đây là một cuộc gọi đuôi tối ưu hóa đệ quy được thực hiện bởi trình biên dịch C.Như mọi khi, nó giúp xem xét một ví dụ cụ thể. Nếu không có bất kỳ tối ưu hóa kích hoạt gcc (v3.4.6) sản xuất mã x86, lắp ráp sau: -

fun: 
    pushl %ebp 
    movl %esp, %ebp 
    call fun 
    leave 
    ret 
    .size fun, .-fun 

Thông báo cuộc gọi đệ quy để vui vẻ(). Nếu điều này thực hiện nó cuối cùng sẽ tràn ngăn xếp của nó và sụp đổ, nhưng tại -O2 gcc sản xuất: -

fun: 
     pushl %ebp 
     movl %esp, %ebp 
.L2: 
     jmp  .L2 
     .size fun, .-fun 

Lưu ý vòng lặp vô tận mà không có hướng dẫn trả lại? Điều này sẽ đơn giản thực hiện mãi mãi.

Answer 8

Người trả lời khác là chính xác rằng có một số phép thuật biên dịch chuyển đổi đệ quy đuôi thành lặp lại, mặc dù nó phụ thuộc vào cài đặt tối ưu hóa của trình biên dịch. Trong gcc ví dụ, nếu chúng ta biên dịch với gcc -S -O1 someFile.c (cho mã của bạn), chúng tôi nhận được lắp ráp tạo sau:

fun: 
.LFB2: 
     pushq %rbp 
.LCFI0: 
     movq %rsp, %rbp 
.LCFI1: 
     movl $0, %eax 
     call fun 
     leave 
     ret 
.LFE2: 
     .size fun, .-fun 

Vì vậy, bạn có thể thấy, nó vẫn sử dụng cuộc gọi/rời/hướng dẫn ret để thực hiện một cuộc gọi chức năng thực tế sẽ giết quá trình. Khi bạn bắt đầu tối ưu hóa hơn nữa với gcc -S -O2 someFile.c chúng tôi bắt đầu nhận được sự kỳ diệu:

fun: 
.LFB24: 
     .p2align 4,,10 
     .p2align 3 
.L2: 
     jmp  .L2 
.LFE24:  
     .size fun, .-fun 
     .p2align 4,,15 

Nó phụ thuộc vào trình biên dịch và các cài đặt trình biên dịch của bạn, vì vậy nó giúp làm bạn với họ.