Menerapkan urutan pernyataan di C ++

Misalkan saya memiliki sejumlah pernyataan yang ingin saya jalankan dalam urutan tetap. Saya ingin menggunakan g ++ dengan pengoptimalan level 2, sehingga beberapa pernyataan dapat diatur ulang. Alat apa yang dimiliki seseorang untuk menegakkan urutan pernyataan tertentu?

Perhatikan contoh berikut.

using Clock = std::chrono::high_resolution_clock;

auto t1 = Clock::now(); // Statement 1
foo();                  // Statement 2
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

Dalam contoh ini, penting bahwa pernyataan 1-3 dieksekusi dalam urutan tertentu. Namun, tidak dapatkah kompilator menganggap pernyataan 2 tidak bergantung pada 1 dan 3 dan menjalankan kode sebagai berikut?

using Clock=std::chrono::high_resolution_clock;

foo();                  // Statement 2
auto t1 = Clock::now(); // Statement 1
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

Saya ingin mencoba memberikan jawaban yang lebih komprehensif setelah ini didiskusikan dengan komite standar C ++. Selain menjadi anggota komite C ++, saya juga seorang pengembang di LLVM dan kompiler Clang.

Pada dasarnya, tidak ada cara untuk menggunakan penghalang atau beberapa operasi dalam urutan untuk mencapai transformasi ini. Masalah mendasar adalah bahwa semantik operasional dari sesuatu seperti penjumlahan integer benar - benar diketahui implementasinya. Ia dapat mensimulasikan mereka, mengetahui bahwa mereka tidak dapat diamati oleh program yang benar, dan selalu bebas untuk memindahkannya.

Kami dapat mencoba mencegah ini, tetapi hasilnya akan sangat negatif dan pada akhirnya akan gagal.

Pertama, satu-satunya cara untuk mencegah hal ini pada compiler adalah dengan memberitahukan bahwa semua operasi dasar ini dapat diamati. Masalahnya adalah hal ini kemudian akan menghalangi sebagian besar pengoptimalan compiler. Di dalam kompiler, pada dasarnya kita tidak memiliki mekanisme yang baik untuk memodelkan bahwa pengaturan waktunya dapat diamati tetapi tidak ada yang lain. Kami bahkan tidak memiliki model yang baik tentang operasi apa yang membutuhkan waktu . Sebagai contoh, apakah mengonversi integer 32-bit unsigned menjadi integer 64-bit unsigned membutuhkan waktu? Dibutuhkan waktu nol pada x86-64, tetapi pada arsitektur lain dibutuhkan waktu bukan nol. Tidak ada jawaban yang benar secara umum di sini.

Tetapi bahkan jika kami berhasil melewati beberapa langkah heroik dalam mencegah compiler menyusun ulang operasi ini, tidak ada jaminan ini akan cukup. Pertimbangkan cara yang valid dan sesuai untuk menjalankan program C ++ Anda pada mesin x86: DynamoRIO. Ini adalah sistem yang secara dinamis mengevaluasi kode mesin program. Satu hal yang dapat dilakukannya adalah pengoptimalan online, dan bahkan mampu secara spekulatif mengeksekusi seluruh rangkaian instruksi aritmatika dasar di luar waktu. Dan perilaku ini tidak unik untuk evaluator dinamis, CPU x86 yang sebenarnya juga akan berspekulasi (jumlah yang jauh lebih kecil) instruksi dan menyusunnya kembali secara dinamis.

Realisasi esensial adalah fakta bahwa aritmatika tidak dapat diamati (bahkan pada tingkat waktu) adalah sesuatu yang menembus lapisan komputer. Hal ini berlaku untuk kompiler, runtime, dan seringkali bahkan untuk perangkat keras. Memaksanya agar dapat diamati akan secara dramatis membatasi kompiler, tetapi juga akan secara dramatis membatasi perangkat keras.

Tetapi semua ini seharusnya tidak membuat Anda kehilangan harapan. Jika Anda ingin mengatur waktu pelaksanaan operasi matematika dasar, kami telah mempelajari teknik yang bekerja dengan andal. Biasanya ini digunakan saat melakukan pembandingan mikro . Saya memberikan ceramah tentang ini di CppCon2015: https://youtu.be/nXaxk27zwlk

Teknik yang ditampilkan di sana juga disediakan oleh berbagai pustaka patokan mikro seperti Google: https://github.com/google/benchmark#preventing-optimization

Kunci dari teknik ini adalah fokus pada data. Anda membuat masukan ke penghitungan buram ke pengoptimal dan hasil penghitungan buram ke pengoptimal. Setelah Anda selesai melakukannya, Anda dapat mengatur waktunya dengan andal. Mari kita lihat versi realistik dari contoh dalam pertanyaan awal, tetapi dengan definisi footerlihat sepenuhnya untuk implementasi. Saya juga telah mengekstrak versi (non-portabel) dari DoNotOptimizepustaka Google Benchmark yang dapat Anda temukan di sini: https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h#L208

#include <chrono>

template <class T>
__attribute__((always_inline)) inline void DoNotOptimize(const T &value) {
  asm volatile("" : "+m"(const_cast<T &>(value)));
}

// The compiler has full knowledge of the implementation.
static int foo(int x) { return x * 2; }

auto time_foo() {
  using Clock = std::chrono::high_resolution_clock;

  auto input = 42;

  auto t1 = Clock::now();         // Statement 1
  DoNotOptimize(input);
  auto output = foo(input);       // Statement 2
  DoNotOptimize(output);
  auto t2 = Clock::now();         // Statement 3

  return t2 - t1;
}

Di sini kami memastikan bahwa data masukan dan data keluaran ditandai sebagai tidak dapat dioptimalkan selama penghitungan foo, dan hanya di sekitar penanda tersebut pengaturan waktu dihitung. Karena Anda menggunakan data untuk menjepit penghitungan, dijamin untuk tetap berada di antara dua pengaturan waktu, namun penghitungan itu sendiri diizinkan untuk dioptimalkan. Rakitan x86-64 yang dihasilkan yang dihasilkan oleh build Clang / LLVM terbaru adalah:

% ./bin/clang++ -std=c++14 -c -S -o - so.cpp -O3
        .text
        .file   "so.cpp"
        .globl  _Z8time_foov
        .p2align        4, 0x90
        .type   _Z8time_foov,@function
_Z8time_foov:                           # @_Z8time_foov
        .cfi_startproc
# BB#0:                                 # %entry
        pushq   %rbx
.Ltmp0:
        .cfi_def_cfa_offset 16
        subq    $16, %rsp
.Ltmp1:
        .cfi_def_cfa_offset 32
.Ltmp2:
        .cfi_offset %rbx, -16
        movl    $42, 8(%rsp)
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, %rbx
        #APP
        #NO_APP
        movl    8(%rsp), %eax
        addl    %eax, %eax              # This is "foo"!
        movl    %eax, 12(%rsp)
        #APP
        #NO_APP
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        subq    %rbx, %rax
        addq    $16, %rsp
        popq    %rbx
        retq
.Lfunc_end0:
        .size   _Z8time_foov, .Lfunc_end0-_Z8time_foov
        .cfi_endproc


        .ident  "clang version 3.9.0 (trunk 273389) (llvm/trunk 273380)"
        .section        ".note.GNU-stack","",@progbits

Di sini Anda dapat melihat compiler mengoptimalkan panggilan ke foo(input)satu instruksi addl %eax, %eax, tetapi tanpa memindahkannya ke luar timing atau menghilangkannya sepenuhnya meskipun input konstan.

Semoga ini bisa membantu, dan komite standar C ++ sedang melihat kemungkinan standarisasi API yang mirip dengan di DoNotOptimizesini.

Ringkasan:

Tampaknya tidak ada cara yang dijamin untuk mencegah pengubahan urutan, tetapi selama pengoptimalan waktu tautan / program penuh tidak diaktifkan, menempatkan fungsi yang dipanggil di unit kompilasi terpisah tampaknya merupakan taruhan yang cukup bagus . (Setidaknya dengan GCC, meskipun logika akan menyarankan bahwa hal ini mungkin terjadi pada kompiler lain juga.) Ini datang dengan biaya dari pemanggilan fungsi - kode inline menurut definisi dalam unit kompilasi yang sama dan terbuka untuk penyusunan ulang.

Jawaban asli:

GCC menyusun ulang panggilan di bawah -O2 optimization:

#include <chrono>
static int foo(int x)    // 'static' or not here doesn't affect ordering.
{
    return x*2;
}
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

GCC 5.3.0:

g++ -S --std=c++11 -O0 fred.cpp :

_ZL3fooi:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %ecx, 16(%rbp)
        movl    16(%rbp), %eax
        addl    %eax, %eax
        popq    %rbp
        ret
_Z4fredi:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $64, %rsp
        movl    %ecx, 16(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -16(%rbp)
        movl    16(%rbp), %ecx
        call    _ZL3fooi
        movl    %eax, -4(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -32(%rbp)
        movl    -4(%rbp), %eax
        addq    $64, %rsp
        popq    %rbp
        ret

Tapi:

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        call    _ZNSt6chrono3_V212system_clock3nowEv
        leal    (%rbx,%rbx), %eax
        addq    $32, %rsp
        popq    %rbx
        ret

Sekarang, dengan foo () sebagai fungsi eksternal:

#include <chrono>
int foo(int x);
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %ecx
        call    _Z3fooi
        movl    %eax, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %eax
        addq    $32, %rsp
        popq    %rbx
        ret

TAPI, jika ini ditautkan dengan -flto (pengoptimalan waktu tautan):

0000000100401710 <main>:
   100401710:   53                      push   %rbx
   100401711:   48 83 ec 20             sub    $0x20,%rsp
   100401715:   89 cb                   mov    %ecx,%ebx
   100401717:   e8 e4 ff ff ff          callq  100401700 <__main>
   10040171c:   e8 bf f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401721:   e8 ba f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401726:   8d 04 1b                lea    (%rbx,%rbx,1),%eax
   100401729:   48 83 c4 20             add    $0x20,%rsp
   10040172d:   5b                      pop    %rbx
   10040172e:   c3                      retq

Penyusunan ulang dapat dilakukan oleh kompiler, atau oleh prosesor.

Sebagian besar penyusun menawarkan metode khusus platform untuk mencegah pengurutan ulang instruksi baca-tulis. Di gcc, ini

asm volatile("" ::: "memory");

( Informasi lebih lanjut di sini )

Perhatikan bahwa ini hanya secara tidak langsung mencegah operasi penataan ulang, selama operasi tersebut bergantung pada baca / tulis.

Dalam praktiknya saya belum melihat sistem di mana panggilan sistem Clock::now()memiliki efek yang sama seperti penghalang tersebut. Anda dapat memeriksa perakitan yang dihasilkan untuk memastikan.

Namun, tidak jarang fungsi yang diuji dievaluasi selama waktu kompilasi. Untuk menjalankan eksekusi "realistis", Anda mungkin perlu mendapatkan masukan foo()dari I / O atau volatilepembacaan.

Pilihan lain adalah menonaktifkan sebaris untuk foo()- sekali lagi, ini khusus untuk kompilator dan biasanya tidak portabel, tetapi akan memiliki efek yang sama.

Di gcc, ini akan menjadi __attribute__ ((noinline))

@Ruslan mengemukakan masalah mendasar: Seberapa realistis pengukuran ini?

Waktu eksekusi dipengaruhi oleh banyak faktor: satu adalah perangkat keras aktual tempat kita menjalankan, yang lainnya adalah akses bersamaan ke sumber daya bersama seperti cache, memori, disk dan inti CPU.

Jadi yang biasanya kami lakukan untuk mendapatkan pengaturan waktu yang sebanding : pastikan mereka dapat direproduksi dengan margin kesalahan rendah. Ini membuatnya agak artifisial.

Performa eksekusi "cache panas" vs. "cache dingin" dapat dengan mudah dibedakan berdasarkan urutan besarnya - tetapi pada kenyataannya, ini akan menjadi sesuatu di antara keduanya ("suam-suam kuku"?)

Bahasa C ++ mendefinisikan apa yang bisa diamati dalam beberapa cara.

Jika foo()tidak ada yang bisa diamati, maka itu bisa dihilangkan sepenuhnya. Jika foo()hanya melakukan komputasi yang menyimpan nilai dalam status "lokal" (baik itu pada stack atau dalam objek di suatu tempat), dan compiler dapat membuktikan bahwa tidak ada pointer yang diturunkan dengan aman yang dapat masuk ke dalam Clock::now()kode, maka tidak ada konsekuensi yang dapat diamati untuk memindahkan Clock::now()panggilan.

Jika foo()berinteraksi dengan file atau layar, dan compiler tidak dapat membuktikan bahwa Clock::now()tidak tidak berinteraksi dengan file atau layar, maka penataan kembali tidak dapat dilakukan, karena interaksi dengan file atau tampilan adalah perilaku yang dapat diamati.

Meskipun Anda dapat menggunakan peretasan khusus kompiler untuk memaksa kode agar tidak berpindah-pindah (seperti perakitan inline), pendekatan lain adalah mencoba mengakali kompiler Anda.

Buat perpustakaan yang dimuat secara dinamis. Muat sebelum kode yang dimaksud.

Perpustakaan itu memperlihatkan satu hal:

namespace details {
  void execute( void(*)(void*), void *);
}

dan membungkusnya seperti ini:

template<class F>
void execute( F f ) {
  struct bundle_t {
    F f;
  } bundle = {std::forward<F>(f)};

  auto tmp_f = [](void* ptr)->void {
    auto* pb = static_cast<bundle_t*>(ptr);
    (pb->f)();
  };
  details::execute( tmp_f, &bundle );
}

yang mengemas lambda nullary dan menggunakan pustaka dinamis untuk menjalankannya dalam konteks yang tidak dapat dipahami oleh compiler.

Di dalam perpustakaan dinamis, kami melakukan:

void details::execute( void(*f)(void*), void *p) {
  f(p);
}

yang cukup sederhana.

Sekarang untuk menyusun ulang panggilan ke execute, itu harus memahami pustaka dinamis, yang tidak bisa dilakukan saat menyusun kode pengujian Anda.

Itu masih dapat menghilangkan foo()s tanpa efek samping, tetapi Anda menang beberapa, Anda kehilangan beberapa.

Tidak, itu tidak bisa. Menurut standar C ++ [intro.execution]:

14 Setiap penghitungan nilai dan efek samping yang terkait dengan ekspresi penuh diurutkan sebelum setiap penghitungan nilai dan efek samping yang terkait dengan ekspresi penuh berikutnya yang akan dievaluasi.

Ekspresi penuh pada dasarnya adalah pernyataan yang diakhiri dengan titik koma. Seperti yang Anda lihat, aturan di atas menetapkan pernyataan harus dijalankan secara berurutan. Di dalam pernyataan itulah kompilator diizinkan lebih bebas kendali (yaitu dalam beberapa keadaan diizinkan untuk mengevaluasi ekspresi yang membuat pernyataan dalam urutan selain kiri-ke-kanan atau hal lain yang spesifik).

Perhatikan kondisi untuk menerapkan aturan seolah-olah tidak terpenuhi di sini. Tidak masuk akal untuk berpikir bahwa setiap kompilator akan dapat membuktikan bahwa pengubahan urutan panggilan untuk mendapatkan waktu sistem tidak akan memengaruhi perilaku program yang dapat diamati. Jika ada keadaan di mana dua panggilan untuk mendapatkan waktu dapat diatur ulang tanpa mengubah perilaku yang diamati, akan sangat tidak efisien untuk benar-benar menghasilkan kompilator yang menganalisis program dengan pemahaman yang cukup untuk dapat menyimpulkan ini dengan pasti.

Tidak.

Terkadang, dengan aturan "seolah-olah", pernyataan dapat diatur ulang. Ini bukan karena keduanya secara logis tidak bergantung satu sama lain, tetapi karena independensi tersebut memungkinkan penataan ulang semacam itu terjadi tanpa mengubah semantik program.

Memindahkan panggilan sistem yang memperoleh waktu saat ini jelas tidak memenuhi kondisi tersebut. Kompiler yang secara sadar atau tidak sadar melakukannya tidak patuh dan sangat konyol.

Secara umum, saya tidak akan mengharapkan ekspresi apa pun yang menghasilkan panggilan sistem menjadi "menebak-nebak" bahkan oleh compiler yang mengoptimalkan secara agresif. Itu hanya tidak cukup tahu tentang apa yang dilakukan oleh panggilan sistem itu.

noinline function + kotak hitam perakitan inline + dependensi data lengkap

Ini didasarkan pada https://stackoverflow.com/a/38025837/895245 tetapi karena saya tidak melihat alasan yang jelas mengapa ::now()tidak dapat diatur ulang di sana, saya lebih suka menjadi paranoid dan memasukkannya ke dalam fungsi noinline bersama dengan asm.

Dengan cara ini saya cukup yakin pengubahan urutan tidak dapat terjadi, karena noinline"mengikat" ::nowdan ketergantungan data.

main.cpp

#include <chrono>
#include <iostream>
#include <string>

// noinline ensures that the ::now() cannot be split from the __asm__
template <class T>
__attribute__((noinline)) auto get_clock(T& value) {
    // Make the compiler think we actually use / modify the value.
    // It can't "see" what is going on inside the assembly string.
    __asm__ __volatile__ ("" : "+g" (value));
    return std::chrono::high_resolution_clock::now();
}

template <class T>
static T foo(T niters) {
    T result = 42;
    for (T i = 0; i < niters; ++i) {
        result = (result * result) - (3 * result) + 1;
    }
    return result;
}

int main(int argc, char **argv) {
    unsigned long long input;
    if (argc > 1) {
        input = std::stoull(argv[1], NULL, 0);
    } else {
        input = 1;
    }

    // Must come before because it could modify input
    // which is passed as a reference.
    auto t1 = get_clock(input);
    auto output = foo(input);
    // Must come after as it could use the output.
    auto t2 = get_clock(output);
    std::cout << "output " << output << std::endl;
    std::cout << "time (ns) "
              << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
              << std::endl;
}

GitHub upstream .

Kompilasi dan jalankan:

g++ -ggdb3 -O3 -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out 1000
./main.out 10000
./main.out 100000

Satu-satunya kelemahan kecil dari metode ini adalah kita menambahkan satu callqinstruksi tambahan di atas sebuah inlinemetode. objdump -CDacara yang mainberisi:

    11b5:       e8 26 03 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>
    11ba:       48 8b 34 24             mov    (%rsp),%rsi
    11be:       48 89 c5                mov    %rax,%rbp
    11c1:       b8 2a 00 00 00          mov    $0x2a,%eax
    11c6:       48 85 f6                test   %rsi,%rsi
    11c9:       74 1a                   je     11e5 <main+0x65>
    11cb:       31 d2                   xor    %edx,%edx
    11cd:       0f 1f 00                nopl   (%rax)
    11d0:       48 8d 48 fd             lea    -0x3(%rax),%rcx
    11d4:       48 83 c2 01             add    $0x1,%rdx
    11d8:       48 0f af c1             imul   %rcx,%rax
    11dc:       48 83 c0 01             add    $0x1,%rax
    11e0:       48 39 d6                cmp    %rdx,%rsi
    11e3:       75 eb                   jne    11d0 <main+0x50>
    11e5:       48 89 df                mov    %rbx,%rdi
    11e8:       48 89 44 24 08          mov    %rax,0x8(%rsp)
    11ed:       e8 ee 02 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>

jadi kami melihat fooitu sebaris, tetapi get_clocktidak dan mengelilinginya.

get_clock Namun itu sendiri sangat efisien, terdiri dari instruksi yang dioptimalkan panggilan daun tunggal yang bahkan tidak menyentuh tumpukan:

00000000000014e0 <auto get_clock<unsigned long long>(unsigned long long&)>:
    14e0:       e9 5b fb ff ff          jmpq   1040 <std::chrono::_V2::system_clock::now()@plt>

Karena ketepatan jam itu sendiri terbatas, saya pikir Anda tidak mungkin dapat melihat efek waktu dari satu ekstra jmpq. Perhatikan bahwa satu calltetap diperlukan karena ::now()berada di pustaka bersama.

Panggilan ::now()dari perakitan inline dengan ketergantungan data

Ini akan menjadi solusi yang paling efisien, mengatasi bahkan tambahan yang jmpqdisebutkan di atas.

Sayangnya ini sangat sulit dilakukan dengan benar seperti yang ditunjukkan di: Memanggil printf dalam ASM sebaris yang diperpanjang

Jika pengukuran waktu Anda dapat dilakukan langsung dalam perakitan inline tanpa panggilan, maka teknik ini dapat digunakan. Ini adalah kasus misalnya untuk instruksi instrumentasi sihir gem5 , x86 RDTSC (tidak yakin apakah ini mewakili lagi) dan mungkin penghitung kinerja lainnya.

Utas terkait:

• Apakah legal bagi pengoptimal C ++ untuk menyusun ulang panggilan ke clock ()?

Diuji dengan GCC 8.3.0, Ubuntu 19.04.