Mengoptimalkan "sementara (1);" dalam C ++ 0x

Diperbarui, lihat di bawah!

Saya telah mendengar dan membaca bahwa C ++ 0x memungkinkan kompiler untuk mencetak "Halo" untuk cuplikan berikut

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

Tampaknya ada hubungannya dengan utas dan kemampuan pengoptimalan. Sepertinya bagi saya ini bisa mengejutkan banyak orang.

Apakah seseorang memiliki penjelasan yang baik tentang mengapa ini perlu untuk memungkinkan? Untuk referensi, konsep C ++ 0x terbaru mengatakan di6.5/5

Sebuah loop itu, di luar pernyataan-for-init dalam kasus pernyataan for,

• tidak membuat panggilan ke fungsi I / O perpustakaan, dan
• tidak mengakses atau memodifikasi objek yang mudah menguap, dan
• tidak melakukan operasi sinkronisasi (1.10) atau operasi atom (Ayat 29)

dapat diasumsikan oleh implementasi untuk mengakhiri. [Catatan: Ini dimaksudkan untuk memungkinkan transformasi compiler, seperti penghapusan loop kosong, bahkan ketika penghentian tidak dapat dibuktikan. - catatan akhir]

Edit:

Artikel berwawasan ini mengatakan tentang teks Standar itu

Sayangnya, kata-kata "perilaku tidak terdefinisi" tidak digunakan. Namun, kapan saja standar mengatakan "kompiler dapat mengasumsikan P," tersirat bahwa sebuah program yang memiliki properti bukan-P memiliki semantik yang tidak ditentukan.

Apakah itu benar, dan apakah kompiler diperbolehkan untuk mencetak "Sampai jumpa" untuk program di atas?

Ada utas yang lebih mendalam di sini , yaitu tentang perubahan analog ke C, dimulai oleh Guy melakukan artikel terkait di atas. Di antara fakta berguna lainnya, mereka menghadirkan solusi yang tampaknya juga berlaku untuk C ++ 0x ( Pembaruan : Ini tidak akan berfungsi lagi dengan n3225 - lihat di bawah!)

endless:
  goto endless;

Tampaknya kompiler tidak diizinkan untuk mengoptimalkannya, karena itu bukan loop, tetapi lompatan. Seorang pria lain merangkum perubahan yang diusulkan dalam C ++ 0x dan C201X

Dengan menulis loop, programmer menyatakan baik bahwa loop melakukan sesuatu dengan perilaku yang terlihat (Melakukan I / O, mengakses objek yang mudah menguap, atau melakukan suatu sinkronisasi atau operasi atom), atau yang akhirnya berakhir. Jika saya melanggar asumsi itu dengan menulis infinite loop tanpa efek samping, saya berbohong kepada kompiler, dan perilaku program saya tidak terdefinisi. (Jika saya beruntung, kompiler mungkin memperingatkan saya tentang hal itu.) Bahasa tidak memberikan (tidak lagi menyediakan?) Cara untuk mengekspresikan loop tanpa batas tanpa perilaku yang terlihat.

Perbarui pada 3.1.2011 dengan n3225: Komite memindahkan teks ke 1.10 / 24 dan berkata

Implementasi dapat berasumsi bahwa utas pada akhirnya akan melakukan salah satu dari yang berikut:

• mengakhiri,
• melakukan panggilan ke fungsi I / O perpustakaan,
• mengakses atau memodifikasi objek yang mudah menguap, atau
• melakukan operasi sinkronisasi atau operasi atom.

The gotoTrik akan tidak bekerja lagi!

Apakah seseorang memiliki penjelasan yang baik tentang mengapa ini perlu untuk memungkinkan?

Ya, Hans Boehm memberikan alasan untuk ini di N1528: Mengapa perilaku tidak terdefinisi untuk loop tak terbatas? , meskipun ini adalah dokumen WG14 dasar pemikirannya berlaku untuk C ++ juga dan dokumen tersebut mengacu pada WG14 dan WG21:

Seperti yang ditunjukkan N1509 dengan benar, konsep saat ini pada dasarnya memberikan perilaku yang tidak terdefinisi ke loop tak terbatas di 6.8.5p6. Masalah utama untuk melakukannya adalah memungkinkan kode bergerak melintasi loop yang berpotensi tidak berakhir. Sebagai contoh, anggap kita memiliki loop berikut, di mana count dan count2 adalah variabel global (atau alamatnya diambil), dan p adalah variabel lokal, yang alamatnya belum diambil:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

Bisakah kedua loop ini digabungkan dan diganti oleh loop berikut?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

Tanpa dispensasi khusus dalam 6.8.5p6 untuk loop tak terbatas, ini akan dianulir: Jika loop pertama tidak berakhir karena q menunjuk ke daftar melingkar, aslinya tidak pernah menulis ke count2. Dengan demikian dapat dijalankan secara paralel dengan utas lain yang mengakses atau memperbarui count2. Ini tidak lagi aman dengan versi yang ditransformasikan yang tidak mengakses count2 meskipun infinite loop. Dengan demikian transformasi berpotensi memperkenalkan perlombaan data.

Dalam kasus seperti ini, sangat tidak mungkin bahwa kompiler akan dapat membuktikan terminasi loop; harus mengerti bahwa q menunjuk ke daftar asiklik, yang saya percaya berada di luar kemampuan kebanyakan kompiler arus utama, dan seringkali tidak mungkin tanpa informasi program secara keseluruhan.

Pembatasan yang diberlakukan oleh loop non-terminasi adalah batasan pada optimasi loop terminasi yang tidak dapat dibuktikan oleh kompiler, serta pada optimisasi loop yang sebenarnya tidak berakhir. Yang pertama jauh lebih umum daripada yang terakhir, dan seringkali lebih menarik untuk dioptimalkan.

Ada juga jelas untuk-loop dengan variabel loop integer di mana akan sulit bagi kompiler untuk membuktikan penghentian, dan dengan demikian akan sulit bagi kompiler untuk merestrukturisasi loop tanpa 6.8.5p6. Bahkan sesuatu seperti

for (i = 1; i != 15; i += 2)

atau

for (i = 1; i <= 10; i += j)

tampaknya tidak trivial untuk menangani. (Dalam kasus sebelumnya, beberapa teori bilangan dasar diperlukan untuk membuktikan penghentian, dalam kasus terakhir, kita perlu mengetahui sesuatu tentang nilai-nilai yang mungkin dari j untuk melakukannya. Pembungkusan untuk bilangan bulat tidak bertanda dapat mempersulit beberapa alasan ini lebih lanjut. )

Masalah ini tampaknya berlaku untuk hampir semua transformasi restrukturisasi loop, termasuk paralelisasi kompiler dan transformasi cache-optimasi, yang keduanya cenderung semakin penting, dan sudah sering penting untuk kode numerik. Hal ini nampaknya akan berubah menjadi biaya yang substansial untuk kepentingan dapat menulis loop tak terbatas dengan cara yang paling alami, terutama karena kebanyakan dari kita jarang menulis loop yang tidak terbatas sengaja.

Satu perbedaan utama dengan C adalah bahwa C11 memberikan pengecualian untuk mengendalikan ekspresi yang merupakan ekspresi konstan yang berbeda dari C ++ dan membuat contoh spesifik Anda didefinisikan dengan baik dalam C11.

Bagi saya, pembenaran yang relevan adalah:

Ini dimaksudkan untuk memungkinkan transformasi compiler, seperti penghapusan loop kosong, bahkan ketika penghentian tidak dapat dibuktikan.

Agaknya, ini karena membuktikan penghentian secara mekanis sulit , dan ketidakmampuan untuk membuktikan penghentian menghambat kompiler yang jika tidak dapat membuat transformasi yang bermanfaat, seperti memindahkan operasi yang tidak tergantung dari sebelum loop ke setelah atau sebaliknya, melakukan operasi pasca-loop dalam satu utas sementara loop dijalankan di yang lain, dan seterusnya. Tanpa transformasi ini, satu loop mungkin memblokir semua utas lainnya sementara mereka menunggu satu utas untuk menyelesaikan loop tersebut. (Saya menggunakan "utas" secara longgar untuk berarti segala bentuk pemrosesan paralel, termasuk aliran instruksi VLIW yang terpisah.)

EDIT: Contoh bisu:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

Di sini, akan lebih cepat bagi satu utas untuk melakukan complex_io_operationsementara yang lain melakukan semua perhitungan rumit dalam loop. Tetapi tanpa klausa yang Anda kutip, kompiler harus membuktikan dua hal sebelum dapat melakukan optimasi: 1) itu complex_io_operation()tidak bergantung pada hasil dari loop, dan 2) bahwa loop akan berakhir . Membuktikan 1) cukup mudah, membuktikan 2) adalah masalah penghentian. Dengan klausa, itu mungkin mengasumsikan loop berakhir dan mendapatkan kemenangan paralelisasi.

Saya juga membayangkan bahwa perancang menganggap bahwa kasus-kasus di mana loop tak terbatas terjadi dalam kode produksi sangat jarang dan biasanya hal-hal seperti loop yang digerakkan oleh peristiwa yang mengakses I / O dalam beberapa cara. Akibatnya, mereka pesimis kasus langka (loop tak terbatas) untuk mengoptimalkan kasus yang lebih umum (tidak terbatas, tetapi sulit untuk membuktikan secara mekanik tidak terbatas, loop).

Namun, itu berarti bahwa loop tak terbatas yang digunakan dalam contoh pembelajaran akan menderita sebagai hasilnya, dan akan meningkatkan gotcha dalam kode pemula. Saya tidak bisa mengatakan ini sepenuhnya hal yang baik.

EDIT: sehubungan dengan artikel berwawasan yang Anda tautkan sekarang, saya akan mengatakan bahwa "kompiler dapat menganggap X tentang program" secara logis setara dengan "jika program tidak memenuhi X, perilaku tidak ditentukan". Kita dapat menunjukkan ini sebagai berikut: misalkan ada program yang tidak memenuhi properti X. Di mana perilaku program ini didefinisikan? Standar hanya mendefinisikan perilaku dengan asumsi properti X benar. Meskipun Standar tidak secara eksplisit menyatakan perilaku yang tidak terdefinisi, itu telah menyatakan itu tidak terdefinisi oleh kelalaian.

Pertimbangkan argumen yang serupa: "kompilator dapat mengasumsikan variabel x hanya ditugaskan paling banyak sekali antara titik-titik urutan" setara dengan "menetapkan ke x lebih dari sekali antara titik-titik urutan tidak ditentukan".

Saya pikir interpretasi yang benar adalah yang berasal dari suntingan Anda: loop tak terbatas kosong adalah perilaku yang tidak terdefinisi.

Saya tidak akan mengatakan itu perilaku yang sangat intuitif, tetapi interpretasi ini lebih masuk akal daripada yang alternatif, bahwa kompiler secara sewenang-wenang diizinkan untuk mengabaikan loop tanpa batas tanpa memanggil UB.

Jika infinite loop adalah UB, itu hanya berarti bahwa program non-terminating tidak dianggap bermakna: menurut C ++ 0x, mereka tidak memiliki semantik.

Itu memang masuk akal juga. Mereka adalah kasus khusus, di mana sejumlah efek samping tidak lagi terjadi (misalnya, tidak ada yang kembali main), dan sejumlah optimisasi kompiler terhambat karena harus menjaga loop tak terbatas. Sebagai contoh, memindahkan komputasi melintasi loop sangat sah jika loop tidak memiliki efek samping, karena pada akhirnya, perhitungan akan dilakukan dalam hal apa pun. Tetapi jika loop tidak pernah berakhir, kita tidak dapat dengan aman mengatur ulang kode di atasnya, karena kita mungkin hanya mengubah operasi mana yang sebenarnya dieksekusi sebelum program hang. Kecuali kita memperlakukan program gantung sebagai UB, itu.

Saya pikir ini sesuai dengan jenis pertanyaan ini , yang mereferensikan utas lainnya . Optimasi sesekali dapat menghapus loop kosong.

Masalah yang relevan adalah bahwa kompiler diizinkan untuk menyusun ulang kode yang efek sampingnya tidak bertentangan. Urutan eksekusi yang mengejutkan dapat terjadi bahkan jika kompiler menghasilkan kode mesin non-terminating untuk infinite loop.

Saya percaya ini adalah pendekatan yang tepat. Spec bahasa mendefinisikan cara untuk menegakkan urutan eksekusi. Jika Anda ingin loop tak terbatas yang tidak dapat disusun ulang sekitar, tulis ini:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

Saya pikir masalah ini mungkin dapat dinyatakan, sebagai "Jika sepotong kode nanti tidak tergantung pada potongan kode sebelumnya, dan potongan kode sebelumnya tidak memiliki efek samping pada bagian lain dari sistem, output kompiler dapat mengeksekusi potongan kode sebelum, setelah, atau dicampur dengan, eksekusi yang pertama, bahkan jika yang pertama berisi loop, tanpa memperhatikan kapan atau apakah kode yang lama benar-benar selesai . Sebagai contoh, kompiler dapat menulis ulang:

membatalkan testfermat (int n)
{
  int a = 1, b = 1, c = 1;
  while (pow (a, n) + pow (b, n)! = pow (c, n))
  {
    jika (b> a) a ++; lain jika (c> b) {a = 1; b ++}; lain {a = 1; b = 1; c ++};
  }
  printf ("Hasilnya adalah");
  printf ("% d /% d /% d", a, b, c);
}

sebagai

membatalkan testfermat (int n)
{
  if (fork_is_first_thread ())
  {
    int a = 1, b = 1, c = 1;
    while (pow (a, n) + pow (b, n)! = pow (c, n))
    {
      jika (b> a) a ++; lain jika (c> b) {a = 1; b ++}; lain {a = 1; b = 1; c ++};
    }
    signal_other_thread_and_die ();
  }
  lain // Utas kedua
  {
    printf ("Hasilnya adalah");
    wait_for_other_thread ();
  }
  printf ("% d /% d /% d", a, b, c);
}

Umumnya tidak masuk akal, meskipun saya mungkin khawatir bahwa:

  total int = 0;
  untuk (i = 0; num_reps> i; i ++)
  {
    update_progress_bar (i);
    total + = do_something_slow_with_no_side_effects (i);
  }
  show_result (total);

akan menjadi

  total int = 0;
  if (fork_is_first_thread ())
  {
    untuk (i = 0; num_reps> i; i ++)
      total + = do_something_slow_with_no_side_effects (i);
    signal_other_thread_and_die ();
  }
  lain
  {
    untuk (i = 0; num_reps> i; i ++)
      update_progress_bar (i);
    wait_for_other_thread ();
  }
  show_result (total);

Dengan memiliki satu CPU yang menangani perhitungan dan yang lainnya menangani pembaruan progress bar, penulisan ulang akan meningkatkan efisiensi. Sayangnya, itu akan membuat pembaruan bilah kemajuan agak kurang bermanfaat daripada seharusnya.

Itu tidak dapat memutuskan untuk kompiler untuk kasus-kasus non-sepele jika itu adalah loop yang tak terbatas sama sekali.

Dalam kasus yang berbeda, dapat terjadi bahwa pengoptimal Anda akan mencapai kelas kompleksitas yang lebih baik untuk kode Anda (misalnya itu O (n ^ 2) dan Anda mendapatkan O (n) atau O (1) setelah optimasi).

Jadi, untuk memasukkan aturan seperti itu yang melarang penghapusan infinite loop ke dalam standar C ++ akan membuat banyak optimisasi menjadi tidak mungkin. Dan kebanyakan orang tidak menginginkan ini. Saya pikir ini cukup menjawab pertanyaan Anda.

Hal lain: Saya tidak pernah melihat contoh yang valid di mana Anda memerlukan loop tak terbatas yang tidak melakukan apa-apa.

Salah satu contoh yang saya dengar tentang peretasan jelek yang benar-benar harus diselesaikan sebaliknya: Ini tentang sistem tertanam di mana satu-satunya cara untuk memicu reset adalah untuk membekukan perangkat sehingga pengawas me-restart secara otomatis.

Jika Anda tahu ada contoh yang valid / bagus di mana Anda memerlukan loop tak terbatas yang tidak melakukan apa-apa, tolong beri tahu saya.

Saya pikir itu layak menunjukkan bahwa loop yang akan menjadi tak terbatas kecuali untuk kenyataan bahwa mereka berinteraksi dengan utas lainnya melalui variabel yang tidak mudah menguap, tidak tersinkronisasi sekarang dapat menghasilkan perilaku yang salah dengan kompiler baru.

Dengan kata lain, jadikan global Anda volatile - dan juga argumen yang dilewatkan ke loop seperti itu melalui pointer / referensi.