streamvbyte simdgo
v0.4.0
Ini adalah repositori yang berisi port stream vbyte untuk pergi. Khususnya, repo ini sangat berhati -hati untuk memanfaatkan teknik SIMD untuk mencapai kinerja yang lebih baik. Saat ini, ada dukungan untuk arsitektur X86_64 yang memiliki instruksi perangkat keras AVX dan AVX2. Dalam kasus di mana itu tidak tersedia, atau pada arsitektur non x86_64 ada implementasi skalar portabel. Kami juga melakukan pemeriksaan runtime untuk memastikan bahwa ISA yang diperlukan tersedia dan jika tidak mundur ke pendekatan skalar.
Ada beberapa implementasi yang ada:
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
MemCopy8Uint32-12 463986302 2.608 ns/op 12269.03 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/decode
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
Get8uint32Fast-12 377839186 3.170 ns/op 10095.99 MB/s
Get8uint32DeltaFast-12 298522095 4.455 ns/op 7183.20 MB/s
Get8uint32Scalar-12 63384603 19.28 ns/op 1659.36 MB/s
Get8uint32DeltaScalar-12 58705828 20.04 ns/op 1596.46 MB/s
Get8uint32Varint-12 27369775 43.77 ns/op 731.10 MB/s
Get8uint32DeltaVarint-12 20924770 57.30 ns/op 558.46 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/encode
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
Put8uint32Fast-12 297620898 3.864 ns/op 8281.18 MB/s
Put8uint32DeltaFast-12 276545827 4.350 ns/op 7356.59 MB/s
Put8uint32Scalar-12 41200776 28.59 ns/op 1119.30 MB/s
Put8uint32DeltaScalar-12 37773458 30.65 ns/op 1044.11 MB/s
Put8uint32Varint-12 58668867 17.20 ns/op 1860.67 MB/s
Put8uint32DeltaVarint-12 61446153 22.88 ns/op 1398.80 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/stream/reader
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
ReadAllFast/Count_1e0-12 99354789 12.24 ns/op 326.80 MB/s
ReadAllFast/Count_1e1-12 28076071 42.81 ns/op 934.43 MB/s
ReadAllFast/Count_1e2-12 11041639 107.2 ns/op 3730.16 MB/s
ReadAllFast/Count_1e3-12 1645387 729.9 ns/op 5480.00 MB/s
ReadAllFast/Count_1e4-12 170894 7034 ns/op 5686.52 MB/s
ReadAllFast/Count_1e5-12 16848 70969 ns/op 5636.29 MB/s
ReadAllFast/Count_1e6-12 1513 728516 ns/op 5490.62 MB/s
ReadAllFast/Count_1e7-12 152 7835111 ns/op 5105.22 MB/s
ReadAllDeltaFast/Count_1e0-12 92727970 13.10 ns/op 305.44 MB/s
ReadAllDeltaFast/Count_1e1-12 26164140 45.89 ns/op 871.61 MB/s
ReadAllDeltaFast/Count_1e2-12 9458992 128.5 ns/op 3113.55 MB/s
ReadAllDeltaFast/Count_1e3-12 1277408 934.4 ns/op 4280.69 MB/s
ReadAllDeltaFast/Count_1e4-12 144405 8318 ns/op 4808.88 MB/s
ReadAllDeltaFast/Count_1e5-12 14444 83151 ns/op 4810.55 MB/s
ReadAllDeltaFast/Count_1e6-12 1426 846305 ns/op 4726.43 MB/s
ReadAllDeltaFast/Count_1e7-12 127 9337355 ns/op 4283.87 MB/s
ReadAllScalar/Count_1e0-12 122650209 9.770 ns/op 409.43 MB/s
ReadAllScalar/Count_1e1-12 38012136 31.63 ns/op 1264.64 MB/s
ReadAllScalar/Count_1e2-12 4999376 241.6 ns/op 1655.30 MB/s
ReadAllScalar/Count_1e3-12 500337 2459 ns/op 1626.38 MB/s
ReadAllScalar/Count_1e4-12 50247 24034 ns/op 1664.34 MB/s
ReadAllScalar/Count_1e5-12 5032 238354 ns/op 1678.17 MB/s
ReadAllScalar/Count_1e6-12 499 2405669 ns/op 1662.74 MB/s
ReadAllScalar/Count_1e7-12 46 24533207 ns/op 1630.44 MB/s
ReadAllDeltaScalar/Count_1e0-12 100000000 10.32 ns/op 387.49 MB/s
ReadAllDeltaScalar/Count_1e1-12 36915704 32.52 ns/op 1230.08 MB/s
ReadAllDeltaScalar/Count_1e2-12 4818140 249.8 ns/op 1601.58 MB/s
ReadAllDeltaScalar/Count_1e3-12 512492 2374 ns/op 1685.20 MB/s
ReadAllDeltaScalar/Count_1e4-12 51004 23639 ns/op 1692.11 MB/s
ReadAllDeltaScalar/Count_1e5-12 3568 333168 ns/op 1200.60 MB/s
ReadAllDeltaScalar/Count_1e6-12 520 2304864 ns/op 1735.46 MB/s
ReadAllDeltaScalar/Count_1e7-12 48 24810555 ns/op 1612.22 MB/s
ReadAllVarint/Count_1e0-12 121348074 9.967 ns/op 401.34 MB/s
ReadAllVarint/Count_1e1-12 21056739 57.34 ns/op 697.64 MB/s
ReadAllVarint/Count_1e2-12 2025081 589.0 ns/op 679.15 MB/s
ReadAllVarint/Count_1e3-12 205881 5851 ns/op 683.69 MB/s
ReadAllVarint/Count_1e4-12 20906 57446 ns/op 696.31 MB/s
ReadAllVarint/Count_1e5-12 2037 580620 ns/op 688.92 MB/s
ReadAllVarint/Count_1e6-12 208 5755083 ns/op 695.04 MB/s
ReadAllVarint/Count_1e7-12 20 57872736 ns/op 691.17 MB/s
ReadAllDeltaVarint/Count_1e0-12 139763250 8.318 ns/op 480.87 MB/s
ReadAllDeltaVarint/Count_1e1-12 19199100 62.49 ns/op 640.11 MB/s
ReadAllDeltaVarint/Count_1e2-12 2149660 556.6 ns/op 718.65 MB/s
ReadAllDeltaVarint/Count_1e3-12 207122 5810 ns/op 688.41 MB/s
ReadAllDeltaVarint/Count_1e4-12 22680 53200 ns/op 751.88 MB/s
ReadAllDeltaVarint/Count_1e5-12 2145 500177 ns/op 799.72 MB/s
ReadAllDeltaVarint/Count_1e6-12 228 5262741 ns/op 760.06 MB/s
ReadAllDeltaVarint/Count_1e7-12 27 42000722 ns/op 952.36 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/stream/writer
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
WriteAllFast/Count_1e0-12 54152408 22.05 ns/op 181.36 MB/s
WriteAllFast/Count_1e1-12 27681948 43.17 ns/op 926.49 MB/s
WriteAllFast/Count_1e2-12 7136480 167.0 ns/op 2395.79 MB/s
WriteAllFast/Count_1e3-12 928952 1273 ns/op 3141.14 MB/s
WriteAllFast/Count_1e4-12 96117 12012 ns/op 3329.93 MB/s
WriteAllFast/Count_1e5-12 9718 114260 ns/op 3500.80 MB/s
WriteAllFast/Count_1e6-12 879 1242927 ns/op 3218.21 MB/s
WriteAllFast/Count_1e7-12 100 10368754 ns/op 3857.74 MB/s
WriteAllDeltaFast/Count_1e0-12 50489378 23.38 ns/op 171.06 MB/s
WriteAllDeltaFast/Count_1e1-12 26866423 45.03 ns/op 888.33 MB/s
WriteAllDeltaFast/Count_1e2-12 6695125 175.8 ns/op 2275.37 MB/s
WriteAllDeltaFast/Count_1e3-12 899895 1391 ns/op 2875.71 MB/s
WriteAllDeltaFast/Count_1e4-12 90394 12958 ns/op 3086.82 MB/s
WriteAllDeltaFast/Count_1e5-12 10000 122319 ns/op 3270.13 MB/s
WriteAllDeltaFast/Count_1e6-12 945 1249546 ns/op 3201.16 MB/s
WriteAllDeltaFast/Count_1e7-12 100 11461852 ns/op 3489.84 MB/s
WriteAllScalar/Count_1e0-12 56106489 21.72 ns/op 184.18 MB/s
WriteAllScalar/Count_1e1-12 18309972 65.09 ns/op 614.51 MB/s
WriteAllScalar/Count_1e2-12 2776918 433.5 ns/op 922.63 MB/s
WriteAllScalar/Count_1e3-12 289309 4209 ns/op 950.38 MB/s
WriteAllScalar/Count_1e4-12 29497 40884 ns/op 978.38 MB/s
WriteAllScalar/Count_1e5-12 3027 399959 ns/op 1000.10 MB/s
WriteAllScalar/Count_1e6-12 296 4010161 ns/op 997.47 MB/s
WriteAllScalar/Count_1e7-12 28 38753790 ns/op 1032.16 MB/s
WriteAllDeltaScalar/Count_1e0-12 54981757 21.90 ns/op 182.65 MB/s
WriteAllDeltaScalar/Count_1e1-12 17823349 67.10 ns/op 596.14 MB/s
WriteAllDeltaScalar/Count_1e2-12 2711672 442.4 ns/op 904.09 MB/s
WriteAllDeltaScalar/Count_1e3-12 292664 4130 ns/op 968.62 MB/s
WriteAllDeltaScalar/Count_1e4-12 29340 41014 ns/op 975.28 MB/s
WriteAllDeltaScalar/Count_1e5-12 2289 516113 ns/op 775.02 MB/s
WriteAllDeltaScalar/Count_1e6-12 302 3930860 ns/op 1017.59 MB/s
WriteAllDeltaScalar/Count_1e7-12 30 41357670 ns/op 967.17 MB/s
WriteAllVarint/Count_1e0-12 208214545 5.720 ns/op 699.32 MB/s
WriteAllVarint/Count_1e1-12 43083270 28.02 ns/op 1427.34 MB/s
WriteAllVarint/Count_1e2-12 4972045 242.8 ns/op 1647.67 MB/s
WriteAllVarint/Count_1e3-12 499011 2409 ns/op 1660.60 MB/s
WriteAllVarint/Count_1e4-12 51022 23590 ns/op 1695.67 MB/s
WriteAllVarint/Count_1e5-12 5216 231741 ns/op 1726.07 MB/s
WriteAllVarint/Count_1e6-12 518 2305364 ns/op 1735.08 MB/s
WriteAllVarint/Count_1e7-12 50 24905825 ns/op 1606.05 MB/s
WriteAllDeltaVarint/Count_1e0-12 175269966 6.792 ns/op 588.93 MB/s
WriteAllDeltaVarint/Count_1e1-12 51799438 23.38 ns/op 1710.63 MB/s
WriteAllDeltaVarint/Count_1e2-12 5417458 221.3 ns/op 1807.60 MB/s
WriteAllDeltaVarint/Count_1e3-12 539414 2243 ns/op 1783.48 MB/s
WriteAllDeltaVarint/Count_1e4-12 52717 22753 ns/op 1757.99 MB/s
WriteAllDeltaVarint/Count_1e5-12 5716 210456 ns/op 1900.63 MB/s
WriteAllDeltaVarint/Count_1e6-12 495 2453672 ns/op 1630.21 MB/s
WriteAllDeltaVarint/Count_1e7-12 70 17491186 ns/op 2286.87 MB/s
Catatan pada tolok ukur: serangkaian UInt32 acak dihasilkan dan kemudian dikodekan/diterjemahkan berulang kali. Upaya dilakukan untuk memastikan bahwa beberapa tolok ukur ini mencerminkan metrik kinerja dunia nyata yang paling mungkin.
Stream Vbyte menggunakan format mendasar yang sama dengan pendekatan grup Google Varint. Lemire et al. Ingin melihat apakah ada cara untuk meningkatkan kinerja lebih banyak dan memperkenalkan sentuhan cerdas untuk memungkinkan kinerja yang lebih baik melalui teknik SIMD. Tujuan dasar dari format grup VARINT adalah untuk dapat mencapai karakteristik kompresi yang sama dengan format VBYTE untuk bilangan bulat dan juga dapat memuat dan memprosesnya dengan sangat cepat.
Wawasan yang mendukung penyandian VBYTE memperhatikan bahwa Anda seringkali tidak memerlukan 32 bit untuk menyandikan bilangan bulat 32-bit. Ambil contoh bilangan bulat yang tidak ditandatangani yang kurang dari 2^8 (256). Integer ini akan memiliki bit yang ditetapkan dalam byte terendah dari integer 32-bit, sedangkan 3 byte yang tersisa hanya nol.
111 in binary:
00000000 00000000 00000000 01101111
Suatu pendekatan yang dapat Anda ambil untuk mengompres bilangan bulat ini adalah dengan menyandikan bilangan bulat menggunakan jumlah variabel byte. Misalnya, Anda dapat menggunakan 7 bit yang lebih rendah untuk menyimpan data, yaitu bit dari bilangan bulat asli, dan kemudian menggunakan MSB sebagai bit kelanjutan. Jika bit MSB aktif, IE adalah 1, maka lebih banyak byte diperlukan untuk memecahkan kode integer khusus ini. Di bawah ini adalah contoh di mana Anda mungkin membutuhkan 2 byte untuk menyimpan angka 1234.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
Jika Anda ingin memecahkan kode integer ini, Anda cukup membangun angka secara iteratif. Yaitu Anda atau 7 bit terakhir dari setiap byte bergeser ke panjang yang sesuai ke bilangan bulat 32-bit Anda sampai Anda menemukan byte yang tidak memiliki set bit kelanjutan. Perhatikan bahwa ini berfungsi sama untuk angka 64-bit.
Masalah dengan pendekatan ini adalah bahwa ia dapat memperkenalkan banyak prediksi yang salah selama pengkodean/decoding. Selama fase decoding, Anda tidak tahu sebelumnya jumlah byte yang digunakan untuk menyandikan bilangan bulat yang sedang Anda proses dan karenanya Anda perlu mengulangi sampai Anda menemukan byte tanpa sedikit kelanjutan. Jika Anda memiliki bilangan bulat yang tidak seragam, yaitu bilangan bulat yang membutuhkan jumlah byte acak untuk mengkode relatif satu sama lain, ini dapat menimbulkan tantangan bagi prediktor cabang prosesor. Prediksi yang salah ini dapat menyebabkan perlambatan besar dalam pipa prosesor dan lahirlah format grup Varint.
Format grup varint (varint-gb) mengasumsikan bahwa semua yang ingin Anda capai, Anda dapat melakukannya dengan bilangan bulat 32-bit. Ini memperkenalkan konsep byte kontrol yang hanyalah byte yang menyimpan panjang yang dikodekan dari sekelompok bilangan bulat 4 32-bit, karenanya grup varint. Bilangan bulat 32-bit hanya membutuhkan hingga 4 byte untuk menyandikan dengan benar. Ini berarti bahwa Anda dapat mewakili panjangnya dengan 2 bit menggunakan panjang nol-indeks, yaitu 0, 1, 2, dan 3 untuk mewakili bilangan bulat yang membutuhkan 1, 2, 3 dan 4 byte untuk masing-masing mengkode.
00000000 00000000 00000000 01101111 = 111
00000000 00000000 00000100 11010010 = 1234
00000000 00001100 00001010 10000011 = 789123
01000000 00000000 00000000 00000000 = 1073741824
Num Len 2-bit control
----------------------------------
111 1 0b00
1234 2 0b01
789123 3 0b10
1073741824 4 0b11
Final Control byte
0b11100100
Encoded data (little endian right-to-left bottom-to-top)
0b01000000 0b00000000 0b00000000 0b00000000 0b00001100
0b00001010 0b10000011 0b00000100 0b11010010 0b01101111
Anda kemudian dapat mengawali setiap kelompok yang terdiri dari 4 bilangan bulat 32-bit yang dikodekan dengan byte kontrol mereka dan kemudian menggunakannya selama decoding. Kelemahan yang jelas adalah bahwa Anda membayar biaya penyimpanan satu byte untuk setiap 4 bilangan bulat yang ingin Anda kodekan. Untuk 2^20 bilangan bulat yang dikodekan, itu adalah ruang ekstra ekstra 256 kb: benar -benar marjinal. Namun, terbalik yang hebat adalah bahwa Anda sekarang telah menghilangkan hampir semua cabang dari fase decoding Anda. Anda tahu persis berapa banyak byte data yang perlu Anda baca dari buffer untuk nomor tertentu dan kemudian dapat menggunakan decoding tanpa cabang.
package foo
import (
"encoding/binary"
)
func decodeOne ( input [] byte , size uint8 ) uint32 {
buf := make ([] byte , 4 )
copy ( buf , input [: size ])
// func (littleEndian) Uint32(b []byte) uint32 {
// _ = b[3]
// return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
// }
return binary . LittleEndian . Uint32 ( buf )
}
func main () {
ctrl := uint8 ( 0b11_10_01_00 )
data := [] byte {
0b01101111 , 0b11010010 , 0b00000100 ,
0b10000011 , 0b00001010 , 0b00001100 ,
0b00000000 , 0b00000000 , 0b00000000 ,
0b01000000 ,
}
len0 := ( ctrl & 3 ) + 1 // 1
len1 := ( ctrl >> 2 & 3 ) + 1 // 2
len2 := ( ctrl >> 4 & 3 ) + 1 // 3
len3 := ( ctrl >> 6 & 3 ) + 1 // 4
_ = decodeOne ( data , len0 ) // 111
_ = decodeOne ( data [ len0 :], len1 ) // 1234
_ = decodeOne ( data [ len0 + len1 :], len2 ) // 789_123
_ = decodeOne ( data [ len0 + len1 + len2 :], len3 ) // 1_073_741_824
}Sayangnya, mempercepat decoding format VARINT-GB dengan hanya teknik SIMD yang terbukti tidak berhasil. Kutipan di bawah ini dari kertas menguraikan alasannya.
Untuk memahami mengapa mungkin sulit untuk mempercepat decoding data yang dikompresi dalam format VARINT-GB dibandingkan dengan format VARINT-G8IU, pertimbangkan bahwa kami tidak dapat memecahkan kode lebih cepat daripada kami dapat mengakses byte kontrol. Di Varint-G8IU, byte kontrol dengan mudah selalu terletak sembilan byte terkompresi terpisah. Jadi sementara byte kontrol sedang diproses, atau bahkan sebelumnya, prosesor superscalar kami dapat memuat dan mulai memproses byte kontrol yang akan datang, karena lokasi mereka dapat diprediksi. Instruksi tergantung pada byte kontrol ini dapat dipesan ulang oleh prosesor untuk kinerja terbaik. Namun, dalam format VARINT-GB, ada ketergantungan data yang kuat: lokasi byte kontrol berikutnya tergantung pada byte kontrol saat ini. Ini meningkatkan risiko bahwa prosesor tetap kurang dimanfaatkan, ditunda oleh latensi antara mengeluarkan beban untuk byte kontrol berikutnya dan menunggu untuk siap.
Selain itu, mereka membuktikan bahwa mendecoding 4 bilangan bulat sekaligus menggunakan register 128-bit lebih cepat daripada mencoba memecahkan kode jumlah variabel bilangan bulat yang masuk ke dalam register 8-byte, yaitu pendekatan VARINT-G8IU.
Lemire et al. telah menyusun algoritma SIMD yang brilian untuk secara bersamaan menghasilkan dua byte kontrol untuk sekelompok 8 bilangan bulat. Cara terbaik untuk memahami algoritma ini adalah dengan memahami cara kerjanya pada bilangan bulat tunggal dan kemudian menganggapnya bekerja dalam bentuk yang diveksiisasi (memang demikian). Ke depan kita akan menggunakan aliran bit kontrol untuk mewakili byte kontrol yang sedang kita bangun ini.
00000000 00000000 00000100 11010010 // 1234
Mari kita ambil salah satu bilangan bulat sebelumnya yang kita lihat, 1234 , dan berjalan melalui contoh bagaimana kontrol 2-bit dihasilkan untuk itu menggunakan teknik SIMD. Tujuannya adalah untuk dapat, untuk bilangan bulat 32-bit, menghasilkan nilai panjang indeks nol 2-bit. Misalnya, jika Anda memiliki bilangan bulat yang membutuhkan 2 byte untuk dikodekan, kami ingin algoritma menghasilkan 0b01 .
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
Algoritma ini pertama-tama menggunakan topeng di mana setiap byte sama dengan 1. Jika Anda melakukan operasi per-min per byte pada bilangan bulat kami dan topeng 1, hasilnya akan memiliki 1 di setiap byte yang memiliki nilai dalam bilangan bulat asli.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
Sekarang Anda melakukan operasi paket jenuh 16-bit hingga 8-bit yang tidak ditandatangani. Praktis ini berarti Anda mengambil setiap nilai 16-bit dan mencoba mendorong itu menjadi 8 bit. Jika bilangan bulat 16-bit lebih besar dari bit integer 8 yang tidak ditandatangani dapat didukung, paket jenuh ke nilai 8-bit tanpa tanda terbesar.
Mengapa ini dilakukan akan menjadi lebih jelas dalam langkah-langkah selanjutnya, namun, pada tingkat tinggi, untuk setiap bilangan bulat yang ingin Anda encode, Anda ingin MSB dari dua byte berturut-turut dalam aliran bit kontrol untuk mewakili kontrol 2-bit akhir. Misalnya, jika Anda memiliki bilangan bulat 3-byte, Anda ingin MSB dari dua byte berturut-turut menjadi 1 dan 0, dalam urutan itu. Alasan Anda menginginkan ini adalah karena ada instruksi paket vektor yang mengambil MSB dari setiap byte dalam aliran bit kontrol dan mengemasnya ke byte terendah. Dengan demikian, ini akan mewakili nilai 0b10 dalam byte akhir untuk bilangan bulat 3-byte ini, yang kita inginkan.
Melakukan paket jenuh yang tidak ditandatangani 16-bit hingga 8-bit memiliki efek bahwa Anda dapat menggunakan perilaku saturasi untuk secara kondisional menyalakan MSB byte ini tergantung pada byte mana yang memiliki nilai dalam bilangan bulat 32-bit asli.
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
Kami kemudian mengambil topeng 1 yang kami gunakan sebelumnya dan melakukan operasi 16-bit min yang ditandatangani . Alasan untuk ini lebih jelas jika Anda melihat contoh menggunakan bilangan bulat 3-byte.
00000000 00001100 00001010 10000011 // 789123
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(789123, 0x0101)
00000000 00000001 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000001 11111111
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000001 00000001
Operasi 16-bit Min yang ditandatangani memiliki tiga efek penting.
Pertama, untuk bilangan bulat 3-byte, ia memiliki efek mematikan MSB byte terendah. Ini diperlukan karena bilangan bulat 3-byte harus memiliki kontrol 2-bit yaitu 0b10 dan tanpa langkah ini menggunakan operasi paket MSB akan menghasilkan kontrol 2-bit yang terlihat seperti 0b_1 , di mana bit terendah aktif. Jelas ini salah, karena hanya bilangan bulat yang membutuhkan 2 atau 4 byte untuk mengkode bit yang lebih rendah, yaitu 1 atau 3 sebagai panjang nol yang diindeks.
Kedua, untuk bilangan bulat 4-byte, aspek yang ditandatangani memiliki efek meninggalkan kedua MSB dari 2 byte. Saat menggunakan operasi paket MSB nanti, itu akan menghasilkan nilai kontrol 2-bit 0b11 , yang kita inginkan.
Ketiga, untuk bilangan bulat 1 dan 2 byte, tidak berpengaruh. Ini bagus untuk nilai 2-byte karena MSB akan tetap pada dan nilai 1 byte tidak akan memiliki MSB apa pun, sehingga secara efektif merupakan NOOP di kedua skenario.
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
Selanjutnya, kami mengambil topeng dengan nilai 0x7F00 dan melakukan Tambah Jenuh yang tidak ditandatangani ke aliran Bit Control. Dalam kasus untuk Integer 1234 ini tidak memiliki efek nyata. Kami mempertahankan MSB dalam byte terendah. Namun, Anda akan mencatat bahwa satu -satunya byte yang memiliki MSB adalah yang terakhir, jadi melakukan operasi paket MSB akan menghasilkan nilai 0b0001 , yang kami inginkan. Contoh langkah ini pada Integer 789123 mungkin melukis gambar yang lebih jelas.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
Anda akan mencatat di sini bahwa penambahan 0x01 dengan 0x7F di hasil byte atas di MSB dari byte atas yang dihasilkan. MSB dalam byte bawah tetap tidak aktif dan sekarang operasi paket MSB akan diselesaikan ke 0b0010 , yang kami inginkan. Perilaku saturasi yang tidak ditandatangani sangat penting untuk angka 4-byte yang hanya memiliki bit dalam byte paling signifikan. Contoh di bawah ini:
01000000 00000000 00000000 00000000 // 1073741824
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1073741824, 0x0101)
00000001 00000000 00000000 00000000
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 11111111 00000000
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 11111111 00000000
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 11111111
Perhatikan di sini bahwa karena hanya byte atas yang memiliki nilai di dalamnya, byte terendah dalam aliran bit kontrol tetap nol selama durasi algoritma. Ini menimbulkan masalah, karena untuk nilai 4-byte, kami ingin kontrol 2-bit menghasilkan nilai 0b11 . Melakukan penambahan jenuh yang tidak ditandatangani 16-bit memiliki efek menyalakan semua bit dalam byte yang lebih rendah, dan dengan demikian kami mendapatkan hasil dengan MSB dalam byte yang lebih rendah.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
Topeng byte langkah terakhir dilakukan pada aliran bit kontrol, dan kami sekarang memiliki hasil yang kami inginkan. Sekarang setelah Anda melihat bahwa ini berfungsi untuk 1 bilangan bulat, Anda tahu cara kerjanya untuk 8 bilangan bulat secara bersamaan, karena kami menggunakan instruksi vektor yang beroperasi pada register 128 bit.
Masalah selanjutnya yang akan diselesaikan adalah bagaimana mengambil sekelompok 4 bilangan bulat, dan mengompresnya dengan menghapus byte asing/tidak digunakan sehingga semua yang tersisa hanyalah aliran byte data dengan informasi nyata. Mari kita ambil dua angka dari contoh kita di atas.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
Di sini, kita dapat menggunakan operasi shuffle. Operasi Vektor Shuffle mengatur ulang byte dalam register input sesuai dengan beberapa mask yang disediakan ke register tujuan. Setiap posisi dalam topeng menyimpan offset ke aliran vektor sumber yang mewakili byte data yang harus masuk ke posisi itu.
input [1234, 789123] (little endian R-to-L)
00000000 00001100 00001010 10000011 00000000 00000000 00000100 11010010
| | | | |
| | |____________________ | |
| |_____________________ | | |
|____________________ | | | |
v v v v v
0xff 0xff 0xff 0x06 0x05 0x04 0x01 0x00 // mask in hex
-----------------------------------------------------------------------
00000000 00000000 00000000 00001100 00001010 10000011 00000100 11010010 // packed
Kami menyimpan tabel pencarian prebuilt yang berisi pemetaan dari byte kontrol ke topeng yang diperlukan dan cukup memuatnya setelah kami membangun byte kontrol di atas. Selain itu, kami menyimpan tabel pencarian untuk pemetaan dari byte kontrol ke total panjang yang dikodekan. Ini memungkinkan kita untuk mengetahui seberapa banyak untuk menambah penunjuk output dan ditimpa, misalnya, 3 byte atas yang berlebihan dalam contoh shuffle di atas.
Membongkar selama decoding sama dengan yang di atas, tetapi secara terbalik. Kita perlu beralih dari format yang penuh sesak ke format memori yang tidak dikemas. Kami menyimpan tabel pencarian untuk mempertahankan pemetaan dari byte kontrol ke topeng shuffle terbalik, dan kemudian melakukan operasi shuffle untuk menghasilkan ke array uint32 .
Stream Vbyte: kompresi integer berorientasi byte yang lebih cepat
