Trình biên dịch có tối ưu hóa thoát khỏi vòng lặp bên trong không?

Question

Mã Tôi có trông như thế này (tất cả sử dụng của xong hiển thị):

bool done = false; 
for(int i = 0; i < big; i++) 
{ 
    ... 
    for(int j = 0; j < wow; j++) 
    { 
    ... 
    if(foo(i,j)) 
    { 
     done = true; 
     break; 
    } 
    ... 
    } 
    if(done) break; 
    ... 
} 

sẽ bất kỳ trình biên dịch chuyển nó sang này:

for(int i = 0; i < big; i++) 
{ 
    ... 
    for(int j = 0; j < wow; j++) 
    { 
    ... 
    if(foo(i,j)) 
     goto __done; // same as a labeled break if we had it 
    ... 
    } 
    ... 
} 
__done:; 

Lưu ý: Trong khi tôi chủ yếu quan tâm nếu số if(done)break; bị bỏ qua và bị xóa dưới dạng mã chết, tôi cũng quan tâm đến việc nó và done sẽ bị xóa hoàn toàn.

Answer 1

Rõ ràng điều này phụ thuộc vào trình biên dịch. Điều tốt nhất để làm khi bạn không chắc chắn là để xem đầu ra lắp ráp của trình biên dịch (tất cả các trình biên dịch phổ biến có một chuyển đổi cho điều này). Ngay cả khi bạn không quen với việc lắp ráp, bạn có thể ít nhất so sánh phiên bản gỡ lỗi với phiên bản được tối ưu hóa.

Điều đó đang được nói, đây là một trong số ít trường hợp mà goto KHÔNG phải là ý tưởng tồi. Hãy sử dụng nó để thoát ra khỏi vòng trong.

Sửa

Chỉ cần thử như sau trong VS2010 và nó thực sự tối ưu hóa bên ngoài có điều kiện:

bool done = false; 
for(int i = 0; i < 10; i++) 
{ 
    for(int j = 0; j < 10; j++) 
    { 
     if(i == 7 && j == 3) 
     { 
      done = true; 
      break; 
     } 
    } 
    if(done) break; 
} 
return 0; 

Answer 2

GNU trình biên dịch không chỉ đó, bắt đầu với mức độ tối ưu hóa -O1 (Tôi đang sử dụng gcc 4.5.1 trên x86_64)

call _Z3fooii // al = foo(i,j) 
testb %al, %al 
jne .L14 
... 

nơi .L14 là nhãn được đặt chính xác nơi bạn đặt __done:

Câu hỏi hay hơn có thể là: trình biên dịch hiện đại nào không thực hiện tối ưu hóa này?

Answer 3

Tôi đã thử GCC 4.2.1 như sau:

// Prevent optimizing out calls to foo and loop unrolling: 
extern int big, wow; 
bool foo(int,int); 

void 
bar() 
{ 
    int done = false; 
    for(int i = 0; i < big; i++) 
    { 
     for(int j = 0; j < wow; j++) 
     { 
      if(foo(i,j)) 
      { 
       done = true; 
       break; 
      } 
     } 
     if(done) 
      break; 
    } 
} 

... và nó rơi qua thẳng đến postamble với -O3:

33: e8 fc ff ff ff   call 34 <bar()+0x34> ; call to foo* 
    38: 84 c0     test %al,%al 
    3a: 74 e5     je  21 <bar()+0x21> ; next loop iteration 
    3c: 83 c4 10    add $0x10,%esp 
    3f: 5b      pop %ebx 
    40: 5e      pop %esi 
    41: 5d      pop %ebp 
    42: c3      ret 

*** Đây là từ một tệp đối tượng chưa được liên kết, call 34 thực sự gọi tới foo.

Answer 4

Tôi không cố gắng để được snarky, nhưng ... không quan trọng? Nói chung, tôi nghĩ tốt nhất là để các trình biên dịch cho công việc của họ, và công việc đó là tạo ra "tốt nhất" (lưu ý rằng "tốt nhất" có thể thay đổi tùy theo nhu cầu của bạn) được biên dịch mã cho mã nguồn của bạn. Bất kỳ sự cân nhắc hiệu suất nào trong mã của bạn phải được xác định với một kiến ​​thức làm việc sâu sắc và hiệu quả về độ phức tạp của thuật toán.

Nếu bạn chỉ tò mò, hãy bỏ qua nhận xét này. Nhưng nếu ý định của bạn là bằng cách nào đó tối ưu hóa mã của bạn, thì tôi nghĩ có nhiều con đường tốt hơn.