Có thể tối ưu hóa cuộc gọi đuôi và RAII cùng tồn tại?

Question

Tôi không thể nghĩ ra một ngôn ngữ RAII thực sự cũng có tối ưu hóa cuộc gọi đuôi trong thông số kỹ thuật, nhưng tôi biết nhiều triển khai C++ có thể làm điều đó như một tối ưu hóa cụ thể cho việc triển khai thực hiện.

Điều này đặt ra một câu hỏi cho những triển khai thực hiện: cho rằng destructors được gọi ở cuối phạm vi biến tự động và không theo thói quen thu gom rác riêng biệt, không vi phạm ràng buộc của TCO. là lệnh cuối cùng ở cuối hàm?

Ví dụ: -

#include <iostream> 

class test_object { 
public: 
    test_object() { std::cout << "Constructing...\n"; } 
    ~test_object() { std::cout << "Destructing...\n"; } 
}; 

void test_function(int count); 

int main() 
{ 
    test_function(999); 
} 

void test_function(int count) 
{ 
    if (!count) return; 
    test_object obj; 
    test_function(count - 1); 
} 

"Xây dựng ..." sẽ được viết 999 lần và sau đó "huỷ ..." khác 999 lần. Cuối cùng, 999 test_object trường hợp sẽ được tự động cấp phát trước khi thư giãn. Nhưng giả sử một thực hiện đã có TCO, sẽ 1000 khung stack tồn tại hoặc chỉ 1?

Trình hủy sau khi cuộc gọi đệ quy có va chạm với các yêu cầu triển khai Tact defacto không?

Answer 1

Được thực hiện theo mệnh giá, có vẻ như RAII hoạt động với TCO. Tuy nhiên, hãy nhớ rằng có một số cách mà trình biên dịch có thể "thoát khỏi nó", vì vậy để nói. Trường hợp đầu tiên và rõ ràng nhất là nếu destructor là tầm thường, có nghĩa là nó là destructor mặc định (compiler-generated) và tất cả các đối tượng phụ có các destructors tầm thường, thì destructor có hiệu quả không tồn tại (luôn luôn tối ưu hóa). Trong trường hợp đó, TCO có thể được thực hiện như bình thường.

Sau đó, trình phá hủy có thể được gạch chân (mã của nó được lấy và đặt trực tiếp vào hàm như trái ngược với được gọi là hàm). Trong trường hợp đó, nó sẽ chỉ có một số mã "clean-up" sau câu lệnh return. Trình biên dịch được phép sắp xếp lại các hoạt động nếu nó có thể xác định rằng kết quả cuối cùng là giống nhau (quy tắc "as-if"), và nó sẽ làm như vậy (nói chung) nếu việc sắp xếp lại dẫn đến mã tốt hơn, và tôi cho rằng TCO là một trong những cân nhắc đang được hầu hết các trình biên dịch áp dụng (ví dụ, nếu nó có thể sắp xếp lại những thứ sao cho mã trở nên thích hợp cho TCO, thì nó sẽ làm điều đó).

Và đối với phần còn lại của các trường hợp, nơi trình biên dịch không thể "đủ thông minh" để tự thực hiện, thì nó trở thành trách nhiệm của người lập trình. Sự hiện diện của cuộc gọi destructor tự động này làm cho nó khó hơn một chút đối với lập trình viên để xem mã TCO-inhibiting clean-up sau cuộc gọi đuôi, nhưng nó không tạo ra bất kỳ sự khác biệt nào về khả năng của lập trình viên để làm cho chức năng một ứng cử viên cho TCO.Ví dụ:

void nonRAII_recursion(int a) { 
    int* arr = new int[a]; 
    // do some stuff with array "arr" 
    delete[] arr; 
    nonRAII_recursion(--a); // tail-call 
}; 

Bây giờ, một ngây thơ RAII_recursion thực hiện có thể là:

void RAII_recursion(int a) { 
    std::vector<int> arr(a); 
    // do some stuff with vector "arr" 
    RAII_recursion(--a); // tail-call 
}; // arr gets destroyed here, not good for TCO. 

Nhưng một lập trình viên khôn ngoan vẫn có thể thấy rằng điều này sẽ không hoạt động (trừ trường hợp destructor vector được sắp xếp theo hàng đó là khả năng trong trường hợp này) và có thể khắc phục tình huống dễ dàng:

void RAII_recursion(int a) { 
    { 
    std::vector<int> arr(a); 
    // do some stuff with vector "arr" 
    }; // arr gets destroyed here 
    RAII_recursion(--a); // tail-call 
}; 

Và tôi khá chắc chắn bạn có thể chứng minh rằng về cơ bản không có trường hợp nào lừa không thể được sử dụng để đảm bảo rằng TCO có thể được áp dụng. Vì vậy, RAII chỉ làm cho nó một chút khó khăn hơn để xem nếu TCO có thể được áp dụng. Nhưng tôi nghĩ rằng các lập trình viên đủ khôn ngoan để thiết kế các cuộc gọi đệ quy có khả năng TCO cũng đủ khôn ngoan để thấy những cuộc gọi hủy hoại "ẩn" cần phải xảy ra trước cuộc gọi đuôi.

THÊM LƯU Ý: Nhìn vào nó theo cách này, trình phá hủy ẩn đi một số mã dọn sạch tự động. Nếu bạn cần mã dọn dẹp (tức là, destructor không tầm thường), bạn sẽ cần nó cho dù bạn sử dụng RAII hay không (ví dụ: mảng kiểu C hoặc bất kỳ thứ gì). Và sau đó, nếu bạn muốn TCO có thể, nó phải có khả năng làm sạch trước khi thực hiện cuộc gọi đuôi (có hoặc không có RAII), và nó có thể, sau đó có thể buộc các đối tượng RAII bị phá hủy trước khi cuộc gọi đuôi (ví dụ, bằng cách đặt chúng bên trong một phạm vi bổ sung).

Answer 2

Nếu trình biên dịch thực hiện TCO thì thứ tự mà trong đó destructors được gọi là thay đổi liên quan đến khi nó không làm TCO.

Nếu trình biên dịch có thể chứng minh rằng sắp xếp lại này không quan trọng (ví dụ: nếu destructor là tầm thường) thì theo quy tắc as-if nó có thể thực hiện TCO. Tuy nhiên, trong ví dụ của bạn trình biên dịch không thể chứng minh điều đó và sẽ không làm TCO.