Có thể constexpr chức năng đánh giá làm đuôi đệ quy tối ưu hóa

Question

Tôi tự hỏi liệu cho các vòng dài chúng ta có thể tận dụng lợi thế của đệ quy đuôi cho constexpr trong C + + 11?

Answer 1

Theo các quy tắc trong [implimits], việc triển khai được phép đặt giới hạn độ sâu đệ quy trên các tính toán constexpr. Hai trình biên dịch có đầy đủ các triển khai constexpr (gcc và clang) đều áp dụng giới hạn như vậy, sử dụng mặc định 512 cuộc gọi đệ quy theo đề xuất của tiêu chuẩn. Đối với cả hai trình biên dịch này, cũng như bất kỳ triển khai nào khác theo đề xuất của tiêu chuẩn, tối ưu hóa đệ quy đuôi về cơ bản sẽ không thể phát hiện được (trừ khi trình biên dịch bị lỗi trước khi đạt đến giới hạn đệ quy của nó).

Thay vào đó, triển khai có thể chọn chỉ tính số cuộc gọi mà không thể áp dụng tối ưu hóa đệ quy đuôi trong giới hạn độ sâu đệ quy của nó hoặc không cung cấp giới hạn như vậy. Tuy nhiên, việc thực hiện như vậy có thể sẽ gây hại cho người dùng, vì nó có khả năng xảy ra sự cố (do tràn ngăn xếp) hoặc không chấm dứt trên các đánh giá constexpr mà recurse sâu hoặc vô hạn.

Đối với những gì xảy ra khi đạt đến giới hạn chiều sâu đệ quy, ví dụ của Pubby nêu lên một điểm thú vị. [expr.const]p2 chỉ định rằng

yêu cầu hàm constexpr hoặc hàm tạo constexpr vượt quá giới hạn đệ quy thực hiện (xem Phụ lục B);

không phải là biểu thức liên tục. Do đó, nếu giới hạn đệ quy đạt được trong một ngữ cảnh yêu cầu một biểu thức không đổi, chương trình sẽ bị hỏng. Nếu một hàm constexpr được gọi trong ngữ cảnh không đòi hỏi một biểu thức liên tục, thì việc thực hiện thường không cần thiết để cố gắng đánh giá nó ở thời gian dịch, nhưng nếu nó chọn, và giới hạn đệ quy được đạt tới, nó được yêu cầu thay vào đó thực hiện cuộc gọi lúc chạy.Trên một hoàn thành, chương trình thử nghiệm compilable:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) { 
    return n ? f(n-1,s+n) : s; 
} 
constexpr unsigned long long k = f(0xffffffff); 

GCC nói:

depthlimit.cpp:4:46: in constexpr expansion of ‘f(4294967295ull, 0ull)’ 
depthlimit.cpp:2:23: in constexpr expansion of ‘f((n + -1ull), (s + n))’ 
depthlimit.cpp:2:23: in constexpr expansion of ‘f((n + -1ull), (s + n))’ 
[... over 500 more copies of the previous message cut ...] 
depthlimit.cpp:2:23: in constexpr expansion of ‘f((n + -1ull), (s + n))’ 
depthlimit.cpp:4:46: error: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum) 

và kêu vang nói:

depthlimit.cpp:4:30: error: constexpr variable 'k' must be initialized by a constant expression 
constexpr unsigned long long k = f(0xffffffff); 
          ^ ~~~~~~~~~~~~~ 
depthlimit.cpp:2:14: note: constexpr evaluation exceeded maximum depth of 512 calls 
    return n ? f(n-1,s+n) : s; 
      ^
depthlimit.cpp:2:14: note: in call to 'f(4294966784, 2194728157440)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966785, 2190433190655)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966786, 2186138223869)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966787, 2181843257082)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966788, 2177548290294)' 
depthlimit.cpp:2:14: note: (skipping 502 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all) 
depthlimit.cpp:2:14: note: in call to 'f(4294967291, 17179869174)' 
depthlimit.cpp:2:14: note: in call to 'f(4294967292, 12884901882)' 
depthlimit.cpp:2:14: note: in call to 'f(4294967293, 8589934589)' 
depthlimit.cpp:2:14: note: in call to 'f(4294967294, 4294967295)' 
depthlimit.cpp:4:34: note: in call to 'f(4294967295, 0)' 
constexpr unsigned long long k = f(0xffffffff); 
           ^

Nếu chúng ta thay đổi mã để đánh giá không nhất thiết phải xảy ra tại thời điểm dịch:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) { 
    return n ? f(n-1,s+n) : s; 
} 
int main(int, char *[]) { 
    return f(0xffffffff); 
} 

sau đó cả hai trình biên dịch chấp nhận nó và tạo mã tính toán kết quả lúc chạy. Khi xây dựng với -O0, mã này không thành công do tràn ngăn xếp. Khi xây dựng với -O2, trình tối ưu hóa của trình biên dịch chuyển đổi mã để sử dụng đệ quy đuôi và các hàm mã đúng (nhưng lưu ý rằng đệ quy đuôi này không liên quan đến việc đánh giá constexpr).

Answer 2

Tôi đã thấy GCC thực hiện tối ưu hóa này. Dưới đây là ví dụ:

constexpr unsigned long long fun1(unsigned long long n, unsigned long long sum = 0) { 
    return (n != 0) ? fun1(n-1,sum+n) : sum; 
} 
fun1(0xFFFFFFFF); 

Hoạt động trên -O2, bị treo khác.

Đáng ngạc nhiên, nó cũng được tối ưu hóa này:

constexpr unsigned long long fun2(unsigned long long n) { 
    return (n != 0) ? n + fun2(n-1) : 0; 
} 

Tôi đã kiểm tra tháo gỡ của các hình thức không conspexpr và tôi có thể xác nhận rằng nó đang được tối ưu hóa thành một vòng lặp.

Nhưng không này:

constexpr unsigned long long fun3(unsigned long long n) { 
    return (n != 0) ? n + fun3(n-1) + fun3(n-1) : 0; 
} 

Vì vậy, trong kết luận, GCC sẽ tối ưu hóa thành một vòng lặp cùng nó cho các chức năng phi consexpr. Sử dụng ít nhất -O2 trở lên.

Answer 3

Tôi không hiểu tại sao nó không thể thực hiện được, tuy nhiên đó là chất lượng chi tiết triển khai.

Nó đã được truyền thống để sử dụng memoization cho các mẫu ví dụ, do đó trình biên dịch không còn nghẹt thở trên:

template <size_t N> 
struct Fib { static size_t const value = Fib <N-1>::value + Fib<N-2>::value; }; 

template <> 
struct Fib<1> { static size_t const value = 1; } 

template <> 
struct Fib<0> { static size_t const value = 0; } 

nhưng thay vì memoize giá trị đã tính toán để giảm sự phức tạp của việc đánh giá của mình cho O (N) .

Đệ quy đệ quy (và đệ quy đuôi) là tối ưu hóa và giống như hầu hết các tối ưu hóa không phải tuân theo Tiêu chuẩn, vì vậy không có lý do gì sẽ không thể thực hiện được. Cho dù một trình biên dịch cụ thể sử dụng nó hay không, tuy nhiên, là khó dự đoán.

Tiêu chuẩn nói trong 5,19 [expr.const]:

2/A có điều kiện thể hiện là một biểu thức hằng lõi trừ khi nó liên quan đến một trong các cách sau như một subexpression có khả năng đánh giá (3.2) [ ...]:

• yêu cầu hàm constexpr hoặc hàm tạo constexpr vượt quá giới hạn đệ quy được xác định (xem Phụ lục B);

Và đọc Phụ lục B:

2/Các giới hạn có thể hạn chế số lượng bao gồm những mô tả dưới đây hoặc những người khác. Số ngoặc đơn sau mỗi số lượng được khuyến nghị là số lượng tối thiểu cho số lượng đó. Tuy nhiên, những đại lượng này chỉ là hướng dẫn và không xác định sự tuân thủ.

• Đệ quy hàm constexpr đệ quy [512].

Đệ quy đuôi không được ấn định.

Answer 4

Tôi không chắc mình hiểu những gì bạn đang yêu cầu.Nếu nó liên quan đến việc trình biên dịch sẽ chuyển đổi đệ quy đuôi thành một vòng lặp, nó không xác định, cho dù chức năng là một constexpr hay không. Nếu là một hàm đệ quy có thể là constexpr, thì tôi không nghĩ rằng việc đệ quy đuôi có liên quan. Nếu tôi đọc các tiêu chuẩn chính xác:

constexpr unsigned ack(unsigned m, unsigned n) 
{ 
    return m == 0 
     ? n + 1 
     : n == 0 
     ? ack(m - 1, 1) 
     : ack(m - 1, ack(m, n - 1)); 
} 

là một constexpr hợp lệ (mặc dù tôi hy vọng các trình biên dịch sẽ phàn nàn về một thiếu nguồn lực cho tất cả nhưng nhỏ nhất n và m, ít nhất nếu hàm được sử dụng trong một ngữ cảnh yêu cầu một biểu thức liên tục).

Answer 5

"Cuộc gọi đuôi" có thể là một từ khóa sai bắt đầu. Các hàm constexpr gần hơn với các hàm toán học. Đối với các hàm toán học, hai hàm sau giống hệt nhau:

constexpr unsigned long long fun1(unsigned long long n) { 
    if (n == 0) return 0 ; 
    return n + fun1(n-1); 
} 
constexpr unsigned long long fun2(unsigned long long n) { 
    if (n != 0) return n + fun2(n-1); 
    return 0; 
} 

từ quan điểm lập trình thủ tục, chúng chắc chắn là không. Chỉ lần đầu tiên sẽ xuất hiện để cho vay chính nó để tối ưu hóa cuộc gọi đuôi.