Apakah kompiler menghasilkan kode yang lebih baik untuk perulangan do-while dibandingkan jenis perulangan lainnya?

Ada komentar di pustaka kompresi zlib (yang digunakan dalam proyek Chromium di antara banyak lainnya) yang menyiratkan bahwa loop do-while di C menghasilkan kode "lebih baik" pada sebagian besar kompiler. Berikut adalah potongan kode yang muncul.

do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         scan < strend);
/* The funny "do {}" generates better code on most compilers */

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

Adakah bukti bahwa sebagian besar (atau ada) kompiler akan menghasilkan kode yang lebih baik (misalnya lebih efisien)?

Pembaruan: Mark Adler , salah satu penulis asli, memberikan sedikit konteks di komentar.

Pertama-tama:

Sebuah do-whileloop tidak sama dengan awhile -loop atau for-loop.

• whiledan forloop mungkin tidak menjalankan badan loop sama sekali.
• SEBUAH do-while lingkaran selalu berjalan tubuh loop setidaknya sekali - itu melompat kondisi pemeriksaan awal.

Jadi itulah perbedaan logisnya. Meskipun demikian, tidak semua orang benar-benar mematuhi ini. Biasanya for whileor forloop digunakan bahkan jika dijamin akan selalu melakukan loop setidaknya sekali. (Terutama dalam bahasa dengan foreach loop.)

Jadi untuk menghindari membandingkan apel dan jeruk, saya akan melanjutkan dengan asumsi bahwa loop akan selalu berjalan setidaknya sekali. Selanjutnya, saya tidak akan menyebutkanfor loop lagi karena mereka pada dasarnya adalah whileloop dengan sedikit gula sintaks untuk penghitung loop.

Jadi saya akan menjawab pertanyaan:

Jika sebuah whileloop dijamin untuk melakukan loop setidaknya sekali, apakah ada keuntungan performa dari penggunaan ado-while loop sebagai gantinya.

SEBUAH do-while melewatkan pemeriksaan kondisi pertama. Jadi ada satu cabang yang kurang dan satu kondisi yang kurang untuk dievaluasi.

Jika kondisinya mahal untuk diperiksa, dan Anda tahu bahwa Anda dijamin akan melakukan loop setidaknya sekali, maka a do-while loop bisa lebih cepat.

Dan meskipun ini dianggap sebagai pengoptimalan mikro, ini adalah salah satu yang tidak selalu dapat dilakukan oleh kompilator: Secara khusus ketika kompilator tidak dapat membuktikan bahwa perulangan akan selalu masuk setidaknya sekali.

Dengan kata lain, loop sementara:

while (condition){
    body
}

Secara efektif sama dengan ini:

if (condition){
    do{
        body
    }while (condition);
}

Jika Anda tahu bahwa Anda akan selalu mengulang setidaknya sekali, pernyataan if itu asing.

Demikian juga di tingkat perakitan, ini kira-kira bagaimana loop yang berbeda dikompilasi ke:

do-while loop:

start:
    body
    test
    conditional jump to start

while-loop:

    test
    conditional jump to end
start:
    body
    test
    conditional jump to start
end:

Perhatikan bahwa kondisi tersebut telah diduplikasi. Pendekatan alternatifnya adalah:

    unconditional jump to end
start:
    body
end:
    test
    conditional jump to start

... yang menukar kode duplikat untuk lompatan tambahan.

Bagaimanapun, ini masih lebih buruk daripada do-whileloop normal .

Konon, penyusun dapat melakukan apa yang mereka inginkan. Dan jika mereka dapat membuktikan bahwa loop selalu masuk sekali, maka itu berhasil untuk Anda.

Tetapi hal-hal agak aneh untuk contoh tertentu dalam pertanyaan karena memiliki badan loop kosong. Karena tidak ada tubuh, tidak ada perbedaan logis antara whiledando-while .

FWIW, saya menguji ini di Visual Studio 2012:

• Dengan badan kosong, itu sebenarnya menghasilkan kode yang sama untuk whiledan do-while. Jadi bagian itu kemungkinan merupakan sisa dari masa lalu ketika kompiler tidak sehebat itu.

• Tetapi dengan isi yang tidak kosong, VS2012 berhasil menghindari duplikasi kode kondisi, tetapi masih menghasilkan lompatan bersyarat tambahan.

Jadi ironis bahwa meskipun contoh dalam pertanyaan menyoroti mengapa do-whileperulangan bisa lebih cepat dalam kasus umum, contoh itu sendiri tampaknya tidak memberikan manfaat apa pun pada kompiler modern.

Mempertimbangkan berapa umur komentar itu, kita hanya bisa menebak mengapa itu penting. Sangat mungkin bahwa penyusun pada saat itu tidak dapat mengenali bahwa tubuh itu kosong. (Atau jika mereka melakukannya, mereka tidak menggunakan informasi tersebut.)

Adakah bukti bahwa sebagian besar (atau ada) kompiler akan menghasilkan kode yang lebih baik (misalnya lebih efisien)?

Tidak banyak, kecuali jika Anda melihat perakitan aktual yang dihasilkan dari kompiler spesifik aktual pada platform tertentu dengan beberapa pengaturan pengoptimalan tertentu.

Ini mungkin perlu dikhawatirkan beberapa dekade yang lalu (ketika ZLib telah ditulis), tetapi tentu saja tidak saat ini, kecuali Anda menemukan, dengan profil nyata, bahwa ini menghilangkan kemacetan dari kode Anda.

Singkatnya (tl; dr):

Saya menafsirkan komentar dalam kode OP sedikit berbeda, saya pikir "kode yang lebih baik" yang mereka klaim telah diamati adalah karena memindahkan pekerjaan sebenarnya ke dalam "kondisi" loop. Namun saya sepenuhnya setuju bahwa itu sangat spesifik kompiler dan bahwa perbandingan yang mereka buat, sementara dapat menghasilkan kode yang sedikit berbeda, sebagian besar tidak ada gunanya dan mungkin usang, seperti yang saya tunjukkan di bawah.

Rincian:

Sulit untuk mengatakan apa yang penulis asli maksudkan dengan komentarnya tentang ini do {} whilemenghasilkan kode yang lebih baik, tetapi saya ingin berspekulasi ke arah lain daripada apa yang diangkat di sini - kami percaya bahwa perbedaan antara do {} whiledan while {}loop cukup tipis (satu cabang kurang sebagai Mystical berkata), tetapi ada sesuatu yang lebih "lucu" dalam kode ini dan itu menempatkan semua pekerjaan di dalam kondisi gila ini, dan membiarkan bagian internal tetap kosong ( do {}).

Saya sudah mencoba kode berikut di gcc 4.8.1 (-O3), dan ini memberikan perbedaan yang menarik -

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

Setelah menyusun -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

Jadi loop pertama melakukan 7 instruksi sedangkan yang kedua melakukan 6, meskipun mereka seharusnya melakukan pekerjaan yang sama. Sekarang, saya tidak dapat benar-benar mengetahui apakah ada beberapa kecerdasan kompilator di balik ini, mungkin tidak dan itu hanya kebetulan tetapi saya belum memeriksa bagaimana itu berinteraksi dengan opsi kompiler lain yang mungkin digunakan proyek ini.

Sebaliknya, pada clang 3.3 (-O3), kedua loop menghasilkan kode 5 instruksi ini:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

Yang hanya menunjukkan bahwa kompiler sangat berbeda, dan maju dengan kecepatan yang jauh lebih cepat daripada yang mungkin diantisipasi beberapa programmer beberapa tahun yang lalu. Itu juga berarti bahwa komentar ini sangat tidak berarti dan mungkin ada karena tidak ada yang pernah memeriksa apakah itu masih masuk akal.

Intinya - jika Anda ingin mengoptimalkan ke kode terbaik (dan Anda tahu bagaimana seharusnya terlihat), lakukan langsung dalam perakitan dan potong "perantara" (kompilator) dari persamaan, tetapi pertimbangkan bahwa yang lebih baru kompiler dan HW yang lebih baru mungkin membuat pengoptimalan ini menjadi usang. Dalam kebanyakan kasus, jauh lebih baik membiarkan kompilator melakukan level pekerjaan itu untuk Anda, dan fokus pada pengoptimalan hal-hal besar.

Hal lain yang harus dibuat - jumlah instruksi (dengan asumsi ini adalah apa yang kode OP asli setelahnya), tidak berarti pengukuran yang baik untuk efisiensi kode. Tidak semua instruksi dibuat sama, dan beberapa di antaranya (gerakan reg-to-reg sederhana misalnya) benar-benar murah karena dioptimalkan oleh CPU. Pengoptimalan lain mungkin benar-benar merusak pengoptimalan internal CPU, jadi pada akhirnya hanya penghitungan pembandingan yang tepat.

Sebuah whileloop sering dikompilasi sebagai do-whileloop dengan cabang awal ke kondisi tersebut, yaitu

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

sedangkan kompilasi do-whileloop sama tanpa cabang awal. Anda dapat melihat dari hal itu bahwa while()secara inheren kurang efisien dengan biaya cabang awal, yang bagaimanapun hanya dibayar sekali. [Bandingkan dengan cara penerapan yang naifwhile, yang membutuhkan baik cabang bersyarat dan cabang tak bersyarat per iterasi.]

Karena itu, mereka bukanlah alternatif yang sebanding. Sangat menyakitkan untuk mengubah whileloop menjadi do-whileloop dan sebaliknya. Mereka melakukan hal yang berbeda. Dan dalam hal ini beberapa pemanggilan metode akan benar-benar mendominasi apapun yang dilakukan compiler whilesebagai lawando-while.

Komentar ini bukan tentang pilihan pernyataan kontrol (lakukan vs. sementara), ini tentang loop yang membuka gulungan !!!

Seperti yang Anda lihat, ini adalah fungsi perbandingan string (elemen string mungkin sepanjang 2 byte), yang bisa ditulis dengan perbandingan tunggal daripada empat dalam shortcut-dan ekspresi.

Implementasi yang terakhir ini pasti lebih cepat, karena ia melakukan satu pemeriksaan kondisi ujung string setelah setiap empat perbandingan elemen, sedangkan pengkodean standar akan melibatkan satu pemeriksaan per perbandingan. Dengan kata lain, 5 pengujian per 4 elemen vs. 8 pengujian per 4 elemen.

Bagaimanapun, ini hanya akan berfungsi jika panjang string adalah kelipatan empat atau memiliki elemen sentinel (sehingga dua string dijamin berbeda melewati strendbatas). Sangat berisiko!

Diskusi tentang sementara vs melakukan efisiensi sama sekali tidak ada gunanya dalam kasus ini, karena tidak ada tubuh.

while (Condition)
{
}

dan

do
{
}
while (Condition);

benar-benar setara.