Vòng lặp có thời gian thực hiện bằng không

Question

Có thể có vòng lặp có thời gian thực hiện bằng không không? Tôi nghĩ rằng ngay cả một vòng lặp trống cũng cần phải có thời gian thực hiện vì có một chi phí liên quan đến nó.

Answer 1

Có - nếu trình biên dịch xác định rằng vòng lặp là mã chết (sẽ không bao giờ thực hiện) thì nó sẽ không tạo mã cho nó. Vòng lặp đó sẽ có 0 thời gian thực hiện, mặc dù nói đúng nó không tồn tại ở mức mã máy.

Answer 2

Có, theo quy tắc as-if trình biên dịch chỉ bắt buộc phải mô phỏng hành vi quan sát của mã, vì vậy nếu bạn có vòng lặp không có bất kỳ hành vi quan sát nào thì nó có thể được tối ưu hóa hoàn toàn và do đó sẽ có hiệu quả không có thời gian thực hiện.

Ví dụ

Ví dụ đoạn mã sau:

int main() 
{ 
    int j = 0 ; 
    for(int i = 0; i < 10000; ++i) 
    { 
    ++j ; 
    } 
} 

biên soạn với gcc 4.9 sử dụng -O3 cờ về cơ bản kết thúc giảm như sau (see it live):

main: 
    xorl %eax, %eax # 
    ret 

Khá nhiều tất cả các tối ưu hóa được phép theo quy tắc as-if, ngoại lệ duy nhất tôi biết là copy elison được phép thực hiện hành vi có thể quan sát.

Một số ví dụ khác sẽ bao gồm dead code elimination có thể xóa mã mà trình biên dịch có thể chứng minh sẽ không bao giờ được thực thi. Ví dụ, mặc dù vòng lặp sau đây không thực sự chứa một tác dụng phụ có thể được tối ưu hóa ra vì chúng ta có thể chứng minh điều đó sẽ không bao giờ được thực thi (see it live):

#include <stdio.h> 

int main() 
{ 
    int j = 0 ; 
    if(false) // The loop will never execute 
    { 
    for(int i = 0; i < 10000; ++i) 
    { 
     printf("%d\n", j) ; 
     ++j ; 
    } 
    } 
} 

Vòng lặp sẽ tối ưu hóa đi giống như trước thí dụ. Một ví dụ thú vị hơn sẽ là trường hợp một tính toán trong một vòng lặp có thể được suy luận vào một hằng số do đó tránh được sự cần thiết của một vòng lặp (không chắc chắn những gì tối ưu hóa loại này thuộc), ví dụ:

int j = 0 ; 
for(int i = 0; i < 10000; ++i) 
{ 
    ++j ; 
} 
printf("%d\n", j) ; 

có thể được tối ưu hóa để đi (see it live):

movl $10000, %esi #, 
movl $.LC0, %edi #, 
xorl %eax, %eax # 
call printf # 

Chúng ta có thể thấy không có vòng lặp liên quan.

đâu như-nếu Rule được đề cập trong tiêu chuẩn

Các như-nếu quy tắc được bao phủ trong dự thảo C99 tiêu chuẩn phần 5.1.2.3Chương trình thực hiện mà nói:

Trong máy trừu tượng, tất cả các biểu thức được đánh giá theo quy định của ngữ nghĩa.Một thực hiện thực tế không cần đánh giá một phần của biểu thức nếu nó có thể suy ra rằng giá trị của nó không được sử dụng và không có tác dụng phụ nào được tạo ra (bao gồm bất kỳ lỗi nào gây ra bằng cách gọi hàm hoặc truy cập đối tượng dễ bay hơi).

as-if rule cũng áp dụng cho C++, gcc cũng sẽ tạo ra kết quả tương tự trong chế độ C++. C++ dự thảo tiêu chuẩn bao gồm này trong phần 1.9 Chương trình thực hiện:

Các mô tả ngữ nghĩa trong tiêu chuẩn này định nghĩa một tham số máy trừu tượng không xác định . Số điện thoại quốc tế tiêu chuẩn này không yêu cầu cấu trúc phù hợp với việc triển khai . Đặc biệt, họ không cần sao chép hoặc mô phỏng cấu trúc của máy trừu tượng. Thay vào đó, phù hợp với việc triển khai được yêu cầu phải thi đua (chỉ) các hành vi quan sát của máy trừu tượng như được giải thích below.5

Answer 3

Cũng như optimisations trình biên dịch, một số CPU kiến ​​trúc, đặc biệt là DSP, có zero overhead looping , theo đó một vòng lặp với số lần lặp cố định được tối ưu hóa hiệu quả bởi phần cứng, xem ví dụ http://www.dsprelated.com/showmessage/20681/1.php

Answer 4

Trình biên dịch không bắt buộc phải đánh giá biểu thức hoặc một phần của biểu thức, không có tác dụng phụ và kết quả bị loại bỏ.

Harbison và Steele, C: A Reference Manual