Retasan hidup: cara mengurai gigabyte ganda per detik

Bagaimana cara membaca nilai ganda dari string dalam kode C ++?

std::stringstream in(mystring);
while(in >> x) {
   sum += x;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Pada Intel Skylake dengan kompiler GCC 8.3, kode ini mem-parsing 50 MB / s. Hard drive dapat dengan mudah memberikan pembacaan berurutan dengan kecepatan beberapa GB / s, jadi tidak diragukan lagi bahwa bukan kecepatan membaca dari disk yang membatasi kita, tetapi kecepatan parsing. Bagaimana saya bisa mempercepatnya?



Hal pertama yang menyarankan dirinya sendiri adalah mengabaikan kenyamanan yang disediakan oleh streaming di C ++ dan memanggil strtod (3) secara langsung:

do {
    number = strtod(s, &end);
    if(end == s) break;
    sum += number;
    s = end; 
} while (s < theend);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kecepatan bertambah hingga 90 MB / s; profiling menunjukkan bahwa ketika membaca dari aliran ~ 1600 instruksi dijalankan untuk setiap nomor yang dibaca, saat menggunakan strtod - ~ 1100 instruksi per nomor. Pustaka standar C dan C ++ dapat dibenarkan dengan persyaratan universalitas dan portabilitas; tetapi jika kita membatasi diri kita pada parsing hanya dua kali lipat dan hanya pada x64, maka kita dapat menulis kode yang jauh lebih efisien: 280 instruksi per nomor sudah cukup.

Mengurai bilangan bulat

Mari kita mulai dengan subtugas: jika diberi angka desimal delapan digit, kita perlu mengubahnya menjadi int. Di sekolah, kita semua diajari melakukan ini dalam satu siklus:

int sum = 0;
for (int i = 0; i <= 7; i++)
{
	sum = (sum * 10) + (num[i] - '0');
}
return sum;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

GCC 9.3.1 -O3 yang dikompilasi, bagi saya kode ini menangani 3 GB / s. Cara yang jelas untuk mempercepatnya adalah dengan membalik putaran; tetapi kompilator melakukannya sendiri.



Perhatikan bahwa notasi desimal angka delapan digit cocok dengan variabel int64_t: misalnya, string "87654321" disimpan dengan cara yang sama seperti nilai int64_t 0x3132333435363738 (byte pertama berisi 8 bit paling tidak signifikan, yang terakhir - yang paling signifikan). Ini berarti bahwa alih-alih delapan akses memori, kita dapat mengalokasikan nilai setiap digit dengan pergeseran:

int64_t sum = *(int64_t*)num;
return (sum      & 15) * 10000000 +
    ((sum >> 8)  & 15) * 1000000 +
    ((sum >> 16) & 15) * 100000 +
    ((sum >> 24) & 15) * 10000 +
    ((sum >> 32) & 15) * 1000 +
    ((sum >> 40) & 15) * 100 +
    ((sum >> 48) & 15) * 10 +
    ((sum >> 56) & 15);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Belum ada percepatan; sebaliknya, kecepatannya turun menjadi 1,7 GB / s! Mari melangkah lebih jauh: AND dengan mask 0x000F000F000F000F akan memberi kita 0x0002000400060008 - digit desimal dalam posisi genap. Mari gabungkan masing-masing dengan yang berikut:

sum = ((sum & 0x000F000F000F000F) * 10) + 
      ((sum & 0x0F000F000F000F00) >> 8);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Setelah itu, 0x3132333435363738 berubah menjadi 0x00 (12) 00 (34) 00 (56) 00 (78) - byte pada posisi genap dinolkan, pada ganjil - berisi representasi biner dari dua digit angka desimal.

return (sum        & 255) * 1000000 +
      ((sum >> 16) & 255) * 10000 +
      ((sum >> 32) & 255) * 100 +
      ((sum >> 48) & 255);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- menyelesaikan konversi angka delapan digit.



Trik yang sama dapat diulangi dengan pasangan angka dua digit:

sum = ((sum & 0x0000007F0000007F) * 100) +
      ((sum >> 16) & 0x0000007F0000007F);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- 0x00 (12) 00 (34) 00 (56) 00 (78) menjadi 0x0000 (1234) 0000 (5678);

dan dengan hasil pasangan empat digit:

return ((sum & 0x3FFF) * 10000) + ((sum >> 32) & 0x3FFF);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- 0x00 (12) 00 (34) 00 (56) 00 (78) menjadi 0x00000000 (12345678). Setengah yang lebih kecil dari int64_t yang dihasilkan adalah hasil yang diinginkan. Terlepas dari penyederhanaan kode yang terlihat (tiga perkalian, bukan tujuh), kecepatan parsing (2,6 GB / s) tetap lebih buruk daripada implementasi naif.



Tetapi menggabungkan pasangan angka dapat disederhanakan bahkan jika Anda melihat bahwa tindakan berikut akan menerapkan mask 0x007F007F007F007F, yang berarti bahwa sampah apa pun dapat dibiarkan dalam byte yang dapat dinolkan:

sum = ((sum & 0x0?0F0?0F0?0F0?0F) * 10) + ((sum & 0x0F??0F??0F??0F??) >> 8) =
   = (((sum & 0x0F0F0F0F0F0F0F0F) * 2560)+ (sum & 0x0F0F0F0F0F0F0F0F)) >> 8 =
    = ((sum & 0x0F0F0F0F0F0F0F0F) * 2561) >> 8;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dalam istilah yang disederhanakan, satu topeng bukan dua, dan tidak ada penambahan. Dua ekspresi yang tersisa disederhanakan dengan cara yang sama:

sum = ((sum & 0x00FF00FF00FF00FF) * 6553601) >> 16;
return((sum & 0x0000FFFF0000FFFF) * 42949672960001) >> 32;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Trik ini disebut SIMD dalam register (SWAR): menggunakannya, kecepatan parsing tumbuh menjadi 3,6 GB / s.



Trik SWAR serupa dapat digunakan untuk memeriksa apakah string delapan karakter adalah angka desimal delapan digit:

return ((val & 0xF0F0F0F0F0F0F0F0) |
      (((val + 0x0606060606060606) & 0xF0F0F0F0F0F0F0F0) >> 4))
            == 0x3333333333333333;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Perangkat ganda

Standar IEEE menetapkan 52 bit ke mantissa dan 11 ke eksponen dalam angka-angka ini; ini berarti bahwa nomor tersebut disimpan sebagai $$$\pm1.m\cdot2^e$ dimana $$$0\le m<2^{52}<10^{16}$ dan $$$-1022\le e\le+1023$ ... Secara khusus, ini berarti bahwa dalam notasi desimal ganda, hanya 17 digit paling signifikan yang signifikan; bit yang paling tidak signifikan tidak dapat memengaruhi nilai ganda dengan cara apa pun. Bahkan 17 digit signifikan jauh lebih banyak daripada yang mungkin diperlukan untuk aplikasi praktis apa pun: Angka yang dinormalisasi sedikit mempersulit pekerjaan (dari







$$$2^{-1074}$ sebelum $$$2^{-1022}$ dengan jumlah bit signifikan yang lebih kecil dalam mantissa) dan persyaratan pembulatan (bilangan desimal apa pun harus diwakili oleh biner terdekat, dan jika angkanya persis di tengah antara biner terdekat, maka mantissa genap lebih disukai). Semua ini memastikan bahwa jika komputer A mengubah angka X menjadi string desimal dengan 17 digit signifikan, maka komputer B mana pun, yang membaca string ini, akan menerima angka X yang sama, bit demi bit - terlepas dari apakah A dan B sama. model prosesor, sistem operasi, dan bahasa pemrograman. (Bayangkan betapa menyenangkannya men-debug kode Anda jika kesalahan pembulatan berbeda pada komputer yang berbeda.) Karena persyaratan pembulatan, kesalahpahaman yang baru-baru ini disebutkan muncul. di Habré: pecahan desimal 0,1 direpresentasikan sebagai pecahan biner terdekat dengannya $$$7205759403792794\cdot2^{-56}$ sama dengan persis 0.1000000000000000055511151231257827021181583404541015625; 0,2 - dalam formulir $$$7205759403792794\cdot2^{-55}$ sama dengan tepat 0.200000000000000011102230246251565404236316680908203125; tetapi jumlahnya bukan pecahan biner yang paling dekat dengan 0,3: perkiraan dari bawah $$$5404319552844595\cdot2^{-54}$ = 0.299999999999999988897769753748434595763683319091796875 ternyata lebih akurat. Oleh karena itu, standar IEEE memerlukan penambahan 0,1 + 0,2 untuk menghasilkan hasil selain 0,3.

Parsing ganda

Sebuah generalisasi langsung dari algoritma integer terdiri dari perkalian berulang dan pembagian dengan 10.0 - tidak seperti penguraian bilangan bulat, di sini perlu untuk memproses angka dari rendah ke tinggi sehingga kesalahan pembulatan dalam angka tinggi "menyembunyikan" kesalahan pembulatan dalam angka rendah. Pada saat yang sama, penguraian mantissa dengan mudah direduksi menjadi penguraian bilangan bulat: itu cukup untuk mengubah normalisasi sehingga titik biner imajiner tidak berada di awal mantissa, tetapi di akhir; bilangan bulat 53-bit yang dihasilkan mengalikan atau membagi dengan pangkat sepuluh yang diinginkan; dan terakhir, kurangi 52 dari eksponennya, yaitu pindahkan titik 52 bit ke kiri - di mana itu harus sesuai dengan standar IEEE. Selain itu, ada tiga fakta penting yang perlu diperhatikan:

1. Mempelajari cara mengalikan atau membagi dengan 5 saja sudah cukup, dan perkalian atau pembagian dengan 2 hanyalah kenaikan atau penurunan eksponen;
2. uint64_t 5 0xcccccccccccccccd 66 , , $$$\frac{\texttt{0xcccccccccccccccd}}{2^{66}} - \frac1 5 = \frac1{5\cdot2^{66}} < 2^{-68}$ 64 ( );
3. – $$$10^{-324} < 2^{-1074}$ $$$2^{1024} < 10^{309}$ ; , 309 , 324 0xcccccccccccccccd, . ( 53 ; 128- , 53- 53- .) 633 double ( , ⅕, 7205759403792794 – 0xcccccccccccccccd, 53 ), double ; 53 , . , , 64 64 , , 128- . .

Kompleksitas pembulatan standar adalah untuk mengetahui bahwa hasilnya persis di tengah antara pecahan biner terdekat, kita tidak hanya membutuhkan 54 bit signifikan dari hasil (bit nol signifikan terkecil berarti "semuanya beres", the one berarti "hit the middle"), tetapi dan Anda perlu memperhatikan apakah ada kelanjutan selain nol setelah bit yang paling tidak signifikan. Secara khusus, ini berarti bahwa hanya mempertimbangkan 17 digit paling signifikan dalam notasi desimal bilangan tersebut tidak cukup: mereka menentukan mantissa biner hanya dengan akurasi ± 1, dan untuk memilih arah pembulatan yang diinginkan, Anda harus mempertimbangkan angka yang lebih rendah. Misalnya, 10000000000000003 dan 10000000000000005 adalah nilai ganda yang sama (sama dengan 10000000000000004), dan 10000000000000005.00 (banyak nol) 001 adalah nilai yang berbeda (sama dengan 10000000000000006).



Profesor Daniel Lemire dari Correspondence University of Quebec (TÉLUQ), yang menemukan parser ini, menerbitkannya di github . Pustaka ini menyediakan dua fungsi from_chars



: satu mengurai string menjadi dua kali lipat, yang lain mengapung. Eksperimennya menunjukkan bahwa dalam 99,8% kasus itu cukup untuk mempertimbangkan 19 digit desimal signifikan (64 bit): jika untuk dua nilai berturut-turut dari 64-bit mantissa diperoleh nilai ganda akhir yang sama, maka ini adalah nilai yang benar . Hanya dalam 0,2% kasus, ketika kedua nilai ini tidak bertepatan, kode yang lebih kompleks dan lebih universal dijalankan yang selalu mengimplementasikan pembulatan yang benar.