streamvbyte simdgo
v0.4.0
これは、行くべきストリームvbyteを含むリポジトリです。特に、このリポジトリは、SIMDテクニックを活用してパフォーマンスを向上させるために特別な注意を払っています。現在、AVXおよびAVX2ハードウェアの命令を持つX86_64アーキテクチャのサポートがあります。それが利用できない場合、またはx86_64以外のアーキテクチャでは、ポータブルスカラーの実装があります。また、必要なISAが利用可能であることを確認し、スカラーアプローチにフォールバックしないことを確認するために、ランタイムチェックを実行します。
いくつかの既存の実装があります：
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
ベンチマークに関するメモ：ランダムUINT32の配列が生成され、何度もエンコード/デコードされます。これらのベンチマークの一部が、最も可能性の高い現実世界のパフォーマンスメトリックを反映していることを確認する試みがなされています。
Stream Vbyteは、GoogleのGroup Varint Approachと同じ基礎形式を使用します。 Lemire et al。パフォーマンスをさらに改善する方法があるかどうかを確認したかったのですが、SIMDテクニックを介してより良いパフォーマンスを可能にするために巧妙なひねりを加えました。グループVARINT形式の基本的な目標は、整数のVBYTE形式と同様の圧縮特性を達成し、それらを非常に迅速にロードして処理できるようにすることです。
VByteエンコードを裏付ける洞察は、32ビット整数をエンコードするために32ビットを必要としないことが多いことに気付くことです。たとえば、2^8（256）未満の署名されていない整数を考えてみましょう。この整数には、32ビット整数の最低バイトにビットが設定され、残りの3バイトは単にゼロになります。
111 in binary:
00000000 00000000 00000000 01101111
この整数を圧縮するために取ることができるアプローチは、可変数のバイトを使用して整数をエンコードすることです。たとえば、下部7ビットを使用してデータ、つまり元の整数からビットを保存し、MSBを継続ビットとして使用できます。 MSBビットがオンの場合、IEは1である場合、この特定の整数をデコードするにはより多くのバイトが必要です。以下は、番号1234を保存するために2バイトが必要になる場合がある例です。
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
この整数をデコードしたい場合は、数字を繰り返し作成するだけです。 IEまたはすべてのバイトの最後の7ビットは、継続ビットセットがないバイトが見つかるまで、適切な長さに32ビット整数にシフトしました。これは、64ビットの数値でも同じように機能することに注意してください。
このアプローチの問題は、エンコード/デコード中に多くの支店の誤処理を導入できることです。デコードフェーズでは、現在処理している整数をエンコードするために使用されたバイトの数を事前に知りません。そのため、継続ビットをオンにすることなくバイトを見つけるまで反復する必要があります。不均一な整数、すなわち乱数のバイトを互いにエンコードする必要がある整数がある場合、これはプロセッサのブランチ予測子に課題をもたらす可能性があります。これらの誤った予測は、プロセッサパイプラインの大幅な減速を引き起こす可能性があるため、グループVarint形式が生まれました。
Group Varint（Varint-GB）形式は、あなたが達成したいすべてのことを想定しています。32ビットの整数でできることを前提としています。コントロールバイトの概念を導入します。これは、4つの32ビット整数のグループのエンコードされた長さを保存する単なるバイトであるため、グループVarintです。 32ビット整数は、適切にエンコードするには最大4バイトのみが必要です。これは、エンコードするのに1、2、3、および4バイトを必要とする整数を表すために、ゼロインデックスされた長さの長さを使用して2ビットの長さを2ビットで表すことができることを意味します。
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
次に、コントロールバイトでエンコードされた32ビット整数の4つのグループのすべてのグループをプレフィックスし、デコード中に使用できます。明らかな欠点は、エンコードする4つの整数ごとに1バイトのストレージコストを支払うことです。 2^20エンコードされた整数の場合、それは余分な256 kbの余分なスペースです。しかし、大きな利点は、デコードフェーズからほぼすべての枝を削除したことです。特定の番号のバッファーから読み取る必要があるデータバイトの数を正確に知っています。その後、分岐のないデコードを使用できます。
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
}残念ながら、SIMDテクニックのみを使用してVARINT-GB形式のデコードを加速することで失敗しました。論文からの以下の抜粋は、その理由を概説しています。
VARINT-G8IU形式と比較して、VARINT-GB形式で圧縮されたデータのデコードを加速するのが難しい理由を理解するために、コントロールバイトにアクセスできるよりも速くデコードできないことを考慮してください。 VARINT-G8IUでは、制御バイトは常に常に9つの圧縮バイトが離れて配置されています。したがって、制御バイトが処理されている間、または以前にさえ、スーパースカラープロセッサは、その場所が予測可能であるため、今後のコントロールバイトのロードと処理を開始できます。これらの制御バイトに依存する手順は、最高のパフォーマンスのためにプロセッサによって並べ替えることができます。ただし、VARINT-GB形式では、強力なデータ依存性があります。次のコントロールバイトの位置は、現在のコントロールバイトに依存します。これにより、プロセッサが十分に活用されていないリスクが高まり、次のコントロールバイトの負荷を発行してから準備ができるようになるまでの遅延によって遅れます。
さらに、128ビットレジスタを使用して一度に4つの整数を解読することは、8バイトレジスタ、つまりVARINT-G8IUアプローチに適合する可変数の整数をデコードしようとするよりも速いことを証明しています。
Lemire et al。 8つの整数のグループに対して2つのコントロールバイトを同時に生成するための素晴らしいSIMDアルゴリズムを考案しました。このアルゴリズムを理解する最良の方法は、単一の整数でどのように機能するかを理解し、それがベクトル化された形式で機能すると仮定することです（それはそうです）。今後、コントロールビットストリームを使用して、構築しているこれらのコントロールバイトを表します。
00000000 00000000 00000100 11010010 // 1234
私たちが見ていた以前の整数の1つである1234取り、SIMDテクニックを使用して2ビットコントロールがどのように生成されるかの例を進みましょう。目標は、32ビットの整数に対して、2ビットのゼロインデックス付き長さの値を生成できることです。たとえば、2バイトをエンコードする必要がある整数がある場合、アルゴリズムが0b01を生成する必要があります。
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
アルゴリズムは、最初にすべてのバイトが1に等しいマスクを使用します。整数と1のマスクで最小操作を実行すると、結果には元の整数に値があるすべてのバイトに1があります。
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
これで、16ビットから8ビットの符号なし飽和パック操作を実行します。実際には、これは16ビットの価値を取得し、それを8ビットに押し込もうとしていることを意味します。 16ビットの整数が最大の署名されていない整数8ビットがサポートできるよりも大きい場合、パックは最大の署名されていない8ビット値に飽和します。
これが実行される理由は、後続のステップでより明確になりますが、エンコードするすべての整数に対して、コントロールビットストリーム内の2つの連続したバイトのMSBが最終的な2ビットコントロールを代表することを望みます。たとえば、3バイトの整数がある場合、2つの連続したバイトのMSBをその順に1と0にする必要があります。これを望む理由は、コントロールビットストリームのすべてのバイトからMSBを取得し、最低バイトに詰めるベクトルパック命令があるからです。したがって、これは、この3バイト整数の最終バイトの値0b10を表します。これが私たちが望むものです。
16ビットから8ビットの符号なし飽和パックを実行すると、飽和挙動を使用して、元の32ビット整数の値があるバイトの値に応じて、これらのバイトのMSBを条件付けて条件付けできるという効果があります。
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
次に、前に使用した1のマスクを取り、署名された16ビットMin操作を実行します。この理由は、3バイトの整数を使用して例を見ると、より明確です。
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
署名された16ビットMin操作には、3つの重要な効果があります。
まず、3バイトの整数の場合、最低バイトのMSBをオフにする効果があります。これは、3バイトの整数に0b10の2ビット制御が必要であり、MSBパック操作を使用するこのステップがないと、最低のビットがオンになっている0b_1のような2ビット制御が得られるためです。エンコードに2つまたは4バイトまたは4バイトを必要とする整数のみが、ゼロインデックスされた長さとして1つまたは3をより低いものにする必要があるため、明らかにこれは間違っています。
第二に、4バイトの整数の場合、署名された側面は、2バイトの両方のMSBをオンにする効果があります。後でMSBパック操作を使用すると、 0b11の2ビット制御値が得られます。これが私たちが望むものです。
第三に、1および2バイトの整数では、効果はありません。これは、MSBが留まり、1バイト値がとにかくMSBを持たないため、2バイトの値に最適なため、両方のシナリオで事実上NOOPです。
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
次に、値0x7F00のマスクを使用し、コントロールビットストリームに符号なしの飽和追加を実行します。整数1234の場合、これは実際の効果はありません。 MSBを最低バイトに維持します。ただし、MSBがオンになっている唯一のバイトは最後のバイトであるため、MSBパック操作を実行すると、値が0b0001になります。整数789123のこのステップの例は、より明確な絵を描くかもしれません。
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
ここでは、上部バイトに0x7Fを含む0x01を追加すると、結果の上部バイトがオンになっているMSBが発生することに注意してください。下部バイトのMSBはオフのままで、MSBパック操作は0b0010に解決されます。これが私たちが望むものです。署名されていない飽和挙動は、最も重要なバイトのみにビットしかない4バイトの数字にとって非常に重要です。以下の例：
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
ここでは、上部バイトのみが値を持っているため、コントロールビットストリームの最低バイトはアルゴリズムの期間中はゼロのままであることに注意してください。これは問題を提起します。4バイト値の場合、2ビットコントロールが0b11の値になることを望んでいるためです。 16ビットの符号なし飽和添加を実行すると、下部バイトのすべてのビットをオンにする効果があるため、下部バイトのMSBが結果になります。
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
最終的な移動バイトマスクは、コントロールビットストリームで実行され、必要な結果が得られました。これが1つの整数で機能することがわかったので、128ビットレジスタで動作するベクトル命令を使用するため、8つの整数で同時にどのように機能するかがわかります。
解決すべき次の問題は、4つの整数のグループを採取し、外観/未使用のバイトを削除して圧縮する方法です。上記の例から2つの数字を取得しましょう。
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
ここでは、シャッフル操作を使用できます。ベクトルシャッフル操作いくつかの提供されたマスクに従って、宛先レジスタに入力レジスタのバイトを再配置します。マスク内のすべての位置は、その位置に入るべきデータバイトを表すソースベクトルストリームにオフセットを保存します。
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
コントロールバイトから必要なマスクへのマッピングを含む事前に構築されたルックアップテーブルを保持し、上記のコントロールバイトを作成した後に単純にロードします。さらに、コントロールバイトから総エンコードされた長さまでのマッピング用のルックアップテーブルを保持します。これにより、出力ポインターをどの程度増分して上書きするかを知ることができます。たとえば、上記のシャッフルの例では冗長な上部3バイトです。
デコード中の開梱は上記と同じですが、逆です。梱包された形式から、未梱包のメモリ形式に移動する必要があります。ルックアップテーブルを保持して、コントロールバイトから逆シャッフルマスクへのマッピングを維持し、シャッフル操作を実行してuint32アレイに出力します。
Stream Vbyte：バイト指向の整数圧縮が速くなります
