Menggunakan pointer ini menyebabkan deoptimisasi yang aneh di hot loop

Saya baru-baru ini menemukan deoptimisasi yang aneh (atau lebih tepatnya melewatkan peluang pengoptimalan).

Pertimbangkan fungsi ini untuk pembongkaran array yang efisien dari bilangan bulat 3-bit menjadi bilangan bulat 8-bit. Ini membongkar 16 int di setiap iterasi loop:

void unpack3bit(uint8_t* target, char* source, int size) {
   while(size > 0){
      uint64_t t = *reinterpret_cast<uint64_t*>(source);
      target[0] = t & 0x7;
      target[1] = (t >> 3) & 0x7;
      target[2] = (t >> 6) & 0x7;
      target[3] = (t >> 9) & 0x7;
      target[4] = (t >> 12) & 0x7;
      target[5] = (t >> 15) & 0x7;
      target[6] = (t >> 18) & 0x7;
      target[7] = (t >> 21) & 0x7;
      target[8] = (t >> 24) & 0x7;
      target[9] = (t >> 27) & 0x7;
      target[10] = (t >> 30) & 0x7;
      target[11] = (t >> 33) & 0x7;
      target[12] = (t >> 36) & 0x7;
      target[13] = (t >> 39) & 0x7;
      target[14] = (t >> 42) & 0x7;
      target[15] = (t >> 45) & 0x7;
      source+=6;
      size-=6;
      target+=16;
   }
}

Berikut adalah perakitan yang dihasilkan untuk bagian-bagian kode:

 ...
 367:   48 89 c1                mov    rcx,rax
 36a:   48 c1 e9 09             shr    rcx,0x9
 36e:   83 e1 07                and    ecx,0x7
 371:   48 89 4f 18             mov    QWORD PTR [rdi+0x18],rcx
 375:   48 89 c1                mov    rcx,rax
 378:   48 c1 e9 0c             shr    rcx,0xc
 37c:   83 e1 07                and    ecx,0x7
 37f:   48 89 4f 20             mov    QWORD PTR [rdi+0x20],rcx
 383:   48 89 c1                mov    rcx,rax
 386:   48 c1 e9 0f             shr    rcx,0xf
 38a:   83 e1 07                and    ecx,0x7
 38d:   48 89 4f 28             mov    QWORD PTR [rdi+0x28],rcx
 391:   48 89 c1                mov    rcx,rax
 394:   48 c1 e9 12             shr    rcx,0x12
 398:   83 e1 07                and    ecx,0x7
 39b:   48 89 4f 30             mov    QWORD PTR [rdi+0x30],rcx
 ...

Ini terlihat cukup efektif. Cukup shift rightdiikuti oleh and, dan kemudian a storeke targetbuffer. Tapi sekarang, lihat apa yang terjadi ketika saya mengubah fungsi menjadi metode di struct:

struct T{
   uint8_t* target;
   char* source;
   void unpack3bit( int size);
};

void T::unpack3bit(int size) {
        while(size > 0){
           uint64_t t = *reinterpret_cast<uint64_t*>(source);
           target[0] = t & 0x7;
           target[1] = (t >> 3) & 0x7;
           target[2] = (t >> 6) & 0x7;
           target[3] = (t >> 9) & 0x7;
           target[4] = (t >> 12) & 0x7;
           target[5] = (t >> 15) & 0x7;
           target[6] = (t >> 18) & 0x7;
           target[7] = (t >> 21) & 0x7;
           target[8] = (t >> 24) & 0x7;
           target[9] = (t >> 27) & 0x7;
           target[10] = (t >> 30) & 0x7;
           target[11] = (t >> 33) & 0x7;
           target[12] = (t >> 36) & 0x7;
           target[13] = (t >> 39) & 0x7;
           target[14] = (t >> 42) & 0x7;
           target[15] = (t >> 45) & 0x7;
           source+=6;
           size-=6;
           target+=16;
        }
}

Saya pikir perakitan yang dihasilkan harus sama, tetapi ternyata tidak. Ini sebagian darinya:

...
 2b3:   48 c1 e9 15             shr    rcx,0x15
 2b7:   83 e1 07                and    ecx,0x7
 2ba:   88 4a 07                mov    BYTE PTR [rdx+0x7],cl
 2bd:   48 89 c1                mov    rcx,rax
 2c0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2c3:   48 c1 e9 18             shr    rcx,0x18
 2c7:   83 e1 07                and    ecx,0x7
 2ca:   88 4a 08                mov    BYTE PTR [rdx+0x8],cl
 2cd:   48 89 c1                mov    rcx,rax
 2d0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2d3:   48 c1 e9 1b             shr    rcx,0x1b
 2d7:   83 e1 07                and    ecx,0x7
 2da:   88 4a 09                mov    BYTE PTR [rdx+0x9],cl
 2dd:   48 89 c1                mov    rcx,rax
 2e0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 2e3:   48 c1 e9 1e             shr    rcx,0x1e
 2e7:   83 e1 07                and    ecx,0x7
 2ea:   88 4a 0a                mov    BYTE PTR [rdx+0xa],cl
 2ed:   48 89 c1                mov    rcx,rax
 2f0:   48 8b 17                mov    rdx,QWORD PTR [rdi] // Load, BAD!
 ...

Seperti yang Anda lihat, kami memperkenalkan redundan tambahan loaddari memori sebelum setiap shift ( mov rdx,QWORD PTR [rdi]). Sepertinya targetpointer (yang sekarang menjadi anggota dan bukan variabel lokal) harus selalu dimuat ulang sebelum menyimpannya. Ini sangat memperlambat kode (sekitar 15% dalam pengukuran saya).

Pertama saya pikir mungkin model memori C ++ memberlakukan bahwa penunjuk anggota mungkin tidak disimpan dalam register tetapi harus dimuat ulang, tetapi ini sepertinya pilihan yang canggung, karena akan membuat banyak pengoptimalan yang layak menjadi tidak mungkin. Jadi saya sangat terkejut bahwa kompilator tidak menyimpan targetdalam register di sini.

Saya mencoba menyimpan pointer anggota sendiri ke dalam variabel lokal:

void T::unpack3bit(int size) {
    while(size > 0){
       uint64_t t = *reinterpret_cast<uint64_t*>(source);
       uint8_t* target = this->target; // << ptr cached in local variable
       target[0] = t & 0x7;
       target[1] = (t >> 3) & 0x7;
       target[2] = (t >> 6) & 0x7;
       target[3] = (t >> 9) & 0x7;
       target[4] = (t >> 12) & 0x7;
       target[5] = (t >> 15) & 0x7;
       target[6] = (t >> 18) & 0x7;
       target[7] = (t >> 21) & 0x7;
       target[8] = (t >> 24) & 0x7;
       target[9] = (t >> 27) & 0x7;
       target[10] = (t >> 30) & 0x7;
       target[11] = (t >> 33) & 0x7;
       target[12] = (t >> 36) & 0x7;
       target[13] = (t >> 39) & 0x7;
       target[14] = (t >> 42) & 0x7;
       target[15] = (t >> 45) & 0x7;
       source+=6;
       size-=6;
       this->target+=16;
    }
}

Kode ini juga menghasilkan assembler yang "baik" tanpa penyimpanan tambahan. Jadi tebakan saya adalah: Kompiler tidak diperbolehkan untuk mengangkat beban pointer anggota dari sebuah struct, jadi seperti "pointer panas" harus selalu disimpan dalam variabel lokal.

• Jadi, mengapa kompilator tidak dapat mengoptimalkan beban ini?
• Apakah model memori C ++ yang melarang ini? Atau apakah itu hanya kekurangan kompiler saya?
• Apakah tebakan saya benar atau apa alasan sebenarnya mengapa pengoptimalan tidak dapat dilakukan?

Kompiler yang digunakan adalah g++ 4.8.2-19ubuntu1dengan -O3optimasi. Saya juga mencoba clang++ 3.4-1ubuntu3dengan hasil yang serupa: Clang bahkan dapat memvektorisasi metode dengan targetpenunjuk lokal . Namun, menggunakan this->targetpointer menghasilkan hasil yang sama: Beban ekstra dari pointer sebelum setiap penyimpanan.

Saya memeriksa assembler beberapa metode serupa dan hasilnya sama: Tampaknya anggota thisselalu harus dimuat ulang sebelum disimpan, bahkan jika beban seperti itu dapat diangkat di luar loop. Saya harus menulis ulang banyak kode untuk menyingkirkan penyimpanan tambahan ini, terutama dengan menyimpan penunjuk ke dalam cache sendiri ke variabel lokal yang dideklarasikan di atas kode panas. Tetapi saya selalu berpikir mengotak-atik detail seperti menyimpan pointer dalam variabel lokal pasti akan memenuhi syarat untuk pengoptimalan prematur di hari-hari ini di mana kompiler menjadi sangat pintar. Tapi sepertinya saya salah disini . Caching penunjuk anggota dalam hot loop tampaknya merupakan teknik pengoptimalan manual yang diperlukan.

Pointer aliasing tampaknya menjadi masalah, ironisnya antara thisdan this->target. Kompiler memperhitungkan kemungkinan yang agak tidak senonoh yang Anda inisialisasi:

this->target = &this

Dalam hal ini, menulis ke this->target[0]akan mengubah konten this(dan dengan demikian, this->target).

Masalah aliasing memori tidak terbatas pada yang di atas. Pada prinsipnya, setiap penggunaan this->target[XX]nilai yang sesuai (dalam) XXmungkin mengarah ke this.

Saya lebih ahli dalam C, di mana hal ini dapat diatasi dengan mendeklarasikan variabel pointer dengan __restrict__kata kunci.

Aturan aliasing yang ketat memungkinkan char*untuk membuat alias penunjuk lainnya. Jadi this->targetboleh alias dengan this, dan dalam metode kode Anda, bagian pertama kode,

target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;

sebenarnya

this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;

sebagaimana thisdapat diubah saat Anda mengubah this->targetkonten.

Setelah di this->target-cache ke variabel lokal, alias tidak lagi dimungkinkan dengan variabel lokal.

Masalahnya di sini adalah aliasing ketat yang mengatakan bahwa kita diizinkan untuk membuat alias melalui char * sehingga mencegah pengoptimalan compiler dalam kasus Anda. Kami tidak diizinkan untuk membuat alias melalui pointer dari tipe berbeda yang akan menjadi perilaku tidak terdefinisi, biasanya pada SO kami melihat masalah ini yaitu pengguna mencoba membuat alias melalui tipe pointer yang tidak kompatibel .

Tampaknya masuk akal untuk mengimplementasikan uint8_t sebagai unsigned char dan jika kita melihat cstdint di Coliru itu termasuk stdint.h yang typedefs uint8_t sebagai berikut:

typedef unsigned char       uint8_t;

jika Anda menggunakan tipe non-char lain maka kompilator harus bisa mengoptimalkan.

Ini tercakup dalam draf standar C ++ bagian 3.10 Lvalues ​​dan rvalues yang mengatakan:

Jika program mencoba mengakses nilai yang disimpan dari suatu objek melalui glvalue selain salah satu dari jenis berikut, perilaku tidak ditentukan

dan termasuk poin berikut:

• jenis char atau unsigned char.

Catatan, saya memposting komentar tentang kemungkinan solusi dalam pertanyaan yang menanyakan When is uint8_t ≠ unsigned char? dan rekomendasinya adalah:

Solusi sepele, bagaimanapun, adalah dengan menggunakan kata kunci batasi, atau untuk menyalin penunjuk ke variabel lokal yang alamatnya tidak pernah diambil sehingga kompilator tidak perlu khawatir tentang apakah objek uint8_t dapat alias itu.

Karena C ++ tidak mendukung kata kunci pembatasan, Anda harus mengandalkan ekstensi kompilator, misalnya gcc menggunakan __restrict__ jadi ini tidak sepenuhnya portabel tetapi saran lain harus digunakan.