Pertanyaan Mengapa strcmp tidak dioptimalkan SIMD?


Saya sudah mencoba mengkompilasi program ini di komputer x64:

#include <cstring>

int main(int argc, char* argv[])
{
  return ::std::strcmp(argv[0],
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really long string"
  );
}

Saya menyusunnya seperti ini:

g++ -std=c++11 -msse2 -O3 -g a.cpp -o a

Tetapi pembongkaran yang dihasilkan adalah seperti ini:

   0x0000000000400480 <+0>:     mov    (%rsi),%rsi
   0x0000000000400483 <+3>:     mov    $0x400628,%edi
   0x0000000000400488 <+8>:     mov    $0x22d,%ecx
   0x000000000040048d <+13>:    repz cmpsb %es:(%rdi),%ds:(%rsi)
   0x000000000040048f <+15>:    seta   %al
   0x0000000000400492 <+18>:    setb   %dl
   0x0000000000400495 <+21>:    sub    %edx,%eax
   0x0000000000400497 <+23>:    movsbl %al,%eax
   0x000000000040049a <+26>:    retq 

Mengapa SIMD tidak digunakan? Saya kira itu bisa untuk membandingkan, katakanlah, 16 karakter sekaligus. Haruskah saya menulis SIMD saya sendiri strcmp, atau itu ide yang tidak masuk akal untuk beberapa alasan?


36
2017-10-27 10:59


asal


Jawaban:


Dalam implementasi SSE2, bagaimana seharusnya compiler memastikan bahwa tidak ada akses memori yang terjadi di akhir string? Itu harus mengetahui panjang pertama dan ini membutuhkan pemindaian string untuk mengakhiri nol byte.

Jika Anda memindai panjang string yang sudah Anda capai sebagian besar dari pekerjaan fungsi strcmp. Oleh karena itu tidak ada manfaat menggunakan SSE2.

Namun, Intel menambahkan instruksi untuk penanganan string dalam set instruksi SSE4.2. Ini menangani masalah zero byte yang diakhiri. Untuk menulis yang bagus pada mereka baca posting blog ini:

http://www.strchr.com/strcmp_and_strlen_using_sse_4.2


42
2017-10-27 11:31



GCC dalam hal ini menggunakan builtin strcmp. Jika Anda ingin menggunakan versi dari penggunaan glibc -fno-builtin. Tetapi Anda tidak boleh berasumsi bahwa versi builtin GCC strcmp atau implementasi glibc dari strcmp efisien. Saya tahu dari pengalaman itu Builtin GCC memcpy dan glibc memcpy tidak seefisien mungkin.

Saya sarankan Anda lihat Asmlib Agner Fog. Dia telah mengoptimalkan beberapa fungsi perpustakaan standar dalam perakitan. Lihat file strcmp64.asm. Ini memiliki dua versi: versi generik untuk CPU tanpa SSE4.2 dan versi untuk CPU dengan SSE4.2. Berikut ini adalah loop utama untuk versi SSE4.2

compareloop:
        add     rax, 16                ; increment offset
        movdqu  xmm1, [rs1+rax]        ; read 16 bytes of string 1
        pcmpistri xmm1, [rs2+rax], 00011000B ; unsigned bytes, equal each, invert. returns index in ecx
        jnbe    compareloop            ; jump if not carry flag and not zero flag

Untuk versi generik yang ditulisnya

Ini adalah solusi yang sangat sederhana. Tidak banyak yang bisa didapat dengan menggunakan SSE2 atau yang rumit

Berikut ini adalah loop utama dari versi generik:

_compareloop:
        mov     al, [ss1]
        cmp     al, [ss2]
        jne     _notequal
        test    al, al
        jz      _equal
        inc     ss1
        inc     ss2
        jmp     _compareloop 

Saya akan membandingkan kinerja builtin GCC strcmp , GLIBC strcmp dan asmlib strcmp. Anda harus melihat pembongkaran untuk memastikan bahwa Anda mendapatkan kode bawaan. Misalnya GCC memcpy tidak menggunakan versi bawaan dari ukuran yang lebih besar dari 8192.

Edit: Sehubungan dengan panjang string, versi SSE4.2 Agner membaca hingga 15 byte di luar string. Dia berpendapat ini jarang masalah karena tidak ada yang ditulis. Ini bukan masalah untuk stack array yang dialokasikan. Untuk array yang dialokasikan secara statis, ini bisa menjadi masalah untuk batas halaman memori. Untuk menyiasatinya, ia menambahkan 16 byte ke bagian .bss setelah bagian .data. Untuk lebih jelasnya lihat bagian 1.7 Instruksi String dan tindakan pencegahan keamanan di manaul dari asmlib.


16
2017-10-27 11:56



Ketika pustaka standar untuk C dirancang, implementasi dari string.h metode yang paling efisien ketika menangani sejumlah besar data akan cukup efisien untuk jumlah kecil, dan sebaliknya. Meskipun mungkin ada beberapa skenario perbandingan-string yang menggunakan instruksi SIMD yang canggih dapat menghasilkan kinerja yang lebih baik daripada "penerapan naif", dalam banyak skenario dunia nyata string yang dibandingkan akan berbeda dalam beberapa karakter pertama. Dalam situasi seperti itu, implementasi naif dapat menghasilkan hasil dalam waktu kurang dari "lebih canggih" pendekatan akan menghabiskan memutuskan bagaimana perbandingan harus dilakukan. Perhatikan bahwa bahkan jika kode SIMD mampu memproses 16 byte sekaligus dan berhenti ketika kondisi ketidakcocokan atau akhir string terdeteksi, itu masih harus melakukan pekerjaan tambahan yang setara dengan menggunakan pendekatan naif pada 16 karakter terakhir yang dipindai . Jika banyak kelompok 16 byte cocok, dapat memindai melalui mereka dengan cepat dapat menguntungkan kinerja. Namun dalam kasus di mana 16 byte pertama tidak cocok, akan lebih efisien untuk memulai dengan perbandingan karakter demi karakter.

Kebetulan, keuntungan potensial lain dari pendekatan "naif" adalah bahwa hal itu mungkin untuk mendefinisikannya sebagai bagian dari header (atau kompiler mungkin menganggap dirinya memiliki "pengetahuan" khusus tentang hal itu). Mempertimbangkan:

int strcmp(char *p1, char *p2)
{
  int idx=0,t1,t2;
  do
  {
    t1=*p1; t2=*p2;
    if (t1 != t2)
    {
      if (t1 > t2) return 1;
      return -1;
    }
    if (!t1)
      return 0;
    p1++; p2++;
  } while(1);
}
...invoked as:
if (strcmp(p1,p2) > 0) action1();
if (strcmp(p3,p4) != 0) action2();

Meskipun metodenya akan sedikit besar untuk di-lined, in-lining dapat pada kasus pertama memungkinkan compiler untuk menghilangkan kode untuk memeriksa apakah nilai yang dikembalikan lebih besar dari nol, dan pada yang kedua menghilangkan kode yang memeriksa apakah t1 lebih besar dari t2. Pengoptimalan seperti itu tidak akan mungkin jika metode itu dikirim melalui lompatan tidak langsung.


7
2017-10-27 18:10



Saya menduga tidak ada gunanya dalam versi SIMD dari fungsi perpustakaan dengan perhitungan yang sangat sedikit. Saya membayangkan itu berfungsi seperti strcmp, memcpy dan mirip sebenarnya dibatasi oleh bandwidth memori dan bukan kecepatan CPU.


3
2017-10-27 11:13



Itu tergantung pada implementasi Anda. Pada MacOS X, fungsi seperti memcpy, memmove dan memset memiliki implementasi yang dioptimalkan tergantung pada perangkat keras yang Anda gunakan (panggilan yang sama akan mengeksekusi kode yang berbeda tergantung pada prosesor, diatur pada saat boot); implementasi ini menggunakan SIMD dan untuk jumlah besar (megabyte) menggunakan beberapa trik yang agak mewah untuk mengoptimalkan penggunaan cache. Tidak ada yang strcpy dan strcmp sejauh yang saya tahu.

Meyakinkan pustaka standar C ++ untuk menggunakan kode semacam itu sulit.


3
2017-10-27 11:20



Membuat versi SSE2 dari strcmp adalah tantangan yang menarik bagi saya.
Saya tidak terlalu suka fungsi intrinsik kompilator karena kode yang kembung, jadi saya memutuskan untuk memilih pendekatan auto-vectorization. Pendekatan saya didasarkan pada templat dan mendekati daftar SIMD sebagai larik kata dengan ukuran yang berbeda.

Saya mencoba menulis implementasi auto-vectorizing dan mengujinya dengan compiler GCC dan MSVC ++.

Jadi, apa yang saya pelajari adalah:
1. GCC's auto-vectorizer bagus (mengagumkan?)
2. MSVC's auto-vectorizer lebih buruk dari GCC's (tidak mengotak-atik fungsi pengepakan saya)
3. Semua kompiler menolak untuk menghasilkan instruksi PMOVMSKB, itu benar-benar menyedihkan

Hasil:
Versi dikompilasi oleh keuntungan online-GCC ~ 40% dengan auto-vektorisasi SSE2. Pada mesin Windows saya dengan Bulldozer-arsitektur CPU auto-vectorized kode lebih cepat daripada kompiler online dan hasil cocok dengan implementasi asli dari strcmp. Tetapi hal terbaik dari ide ini adalah kode yang sama dapat dikompilasi untuk setiap set instruksi SIMD, setidaknya pada ARM & X86.

catatan:
Jika ada yang akan menemukan cara untuk membuat compiler untuk menghasilkan instruksi PMOVMSKB maka kinerja keseluruhan harus mendapatkan dorongan yang signifikan.

Opsi baris perintah untuk GCC: -std = c ++ 11 -O2 -m64 -mfpmath = sse -march = asli -tahap-vektorize -msse2 -march = asli -Wall -Wextra

Tautan:
Kode sumber dikompilasi oleh Coliru online compiler
Assembly + Source code (Compiler Explorer)

@PeterCordes, terima kasih atas bantuannya.


2
2017-08-01 19:51



AVX 2.0 akan lebih cepat sebenarnya

Edit: Ini terkait dengan register dan IPC

Daripada mengandalkan 1 instruksi besar, Anda dapat menggunakan sejumlah instruksi SIMD dengan 16 register 32 byte, baik, di UTF16 Anda memberi Anda 265 karakter untuk dimainkan!

gandakan itu dengan avx512 dalam beberapa tahun!

Instruksi AVX juga memiliki throughput yang tinggi.

Menurut blog ini: https://blog.cloudflare.com/improving-picohttpparser-further-with-avx2/

Hari ini pada prosesor Haswell terbaru, kami memiliki AVX2 yang kuat   instruksi. Instruksi AVX2 beroperasi pada 32 byte, dan sebagian besar   instruksi boolean / logika bekerja dengan kecepatan 0,5 siklus   per instruksi. Ini berarti kita dapat mengeksekusi sekitar 22 AVX2   instruksi dalam jumlah waktu yang sama untuk mengeksekusi satu   PCMPESTRI. Mengapa tidak mencobanya?

Edit 2.0 Unit SSE / AVX adalah gerbang listrik, dan mencampur SSE dan / atau instruksi AVX dengan yang biasa melibatkan sakelar konteks dengan penalti kinerja, yang tidak boleh Anda miliki dengan instruksi strcmp.


0
2017-10-18 02:03



Saya tidak melihat titik dalam "mengoptimalkan" fungsi seperti strcmp.

Anda harus mencari panjang string sebelum menerapkan pemrosesan paralel apa pun, yang akan memaksa Anda untuk membaca memori setidaknya sekali. Sementara Anda melakukannya, Anda mungkin juga menggunakan data untuk melakukan perbandingan dengan cepat.

Jika Anda ingin melakukan apapun dengan cepat dengan string, Anda akan membutuhkan alat khusus seperti mesin negara yang terbatas (lexx terlintas dalam pikiran untuk parser).

Adapun C ++ std::string, mereka tidak efisien dan lambat karena sejumlah besar alasan, sehingga keuntungan dari pengecekan panjang dalam perbandingan dapat diabaikan.


-3
2017-10-27 11:29