首頁>編程相關>其他源碼
下載

流Vbyte Simd Go

這是一個存儲庫，其中包含流式vbyte的端口。值得注意的是，此倉庫要額外謹慎地利用SIMD技術來取得更好的性能。當前，對具有AVX和AVX2硬件說明的X86_64體系結構有所支持。如果沒有可用的情況，或者在非X86_64體系結構上有一個便攜式標量實現。我們還執行運行時檢查，以確保必要的ISA可用，如果不是標量方法的後備。

有幾種現有的實現：

  1. 參考C/C ++
  2. 銹
  3. 去
    • 注意：只有一個標量實現，該實現促使使用SIMD技術實現。

基準

 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方法相同的基礎格式。 Lemire等。想看看是否有一種方法可以進一步提高性能，並引入了一個巧妙的轉折，以通過SIMD技術實現更好的性能。組Varint格式的基本目標是能夠獲得與整數的VBYTE格式相似的壓縮特性，並能夠真正快速加載和處理它們。

vbyte格式

背面編碼的洞察力指出，您通常不需要32位來編碼32位整數。以小於2^8（256）的無符號整數為例。該整數將在32位整數的最低字節中設置為位，而其餘的3個字節僅是零。 

 111 in binary:

00000000 00000000 00000000 01101111

您可以採用一種壓縮該整數的方法是使用可變數量的字節編碼整數。例如，您可以使用較低的7位存儲數據，即原始整數中的位，然後將MSB用作延續位。如果MSB位打開，IE為1，則需要更多字節來解碼此特定整數。以下是一個示例，您可能需要2個字節來存儲編號1234。 

 1234 in binary:

00000000 00000000 00000100 11010010

Num compressed:

v          v          Continuation bits
0|0001001| 1|1010010|
    ^           ^     Data bits

如果要解碼此整數，則只需迭代地構建數字即可。即您或每個字節的最後7位轉移到32位整數的適當長度，直到找到一個沒有延續位的字節為止。請注意，這對於64位數字也相同。

這種方法的問題在於，它可以在編碼/解碼過程中引入許多分支錯誤預測。在解碼階段，您不提前知道用於編碼當前正在處理的整數的字節數，因此您需要迭代，直到找到一個字節而沒有延續為止。如果您的整數是不均勻的，則需要隨機數的字節數以相對編碼的IE整數，這可能會對處理器的分支預測變量構成挑戰。這些錯誤的預測可能會導致處理器管道的嚴重放緩，因此誕生了小組Varint格式。

組Varint格式

組Varint（Varint-GB）格式假定您希望實現的一切，您可以使用32位整數。它介紹了控製字節的概念，該字節只是一個字節，該字節存儲了一個4個32位整數的組的編碼長度，因此coute varint。 32位整數最多需要4個字節才能正確編碼。這意味著您可以使用零索引長度IE 0、1、2和3表示他們的長度，以代表需要1、2、3和4個字節的整數。 

 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

然後，您可以將每組4個組成的4組編碼32位整數及其控件字節前綴，然後在解碼過程中使用它。顯而易見的缺點是，您要為要編碼的每4個整數支付一個字節的存儲成本。對於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
}

流Vbyte格式

不幸的是，僅使用SIMD技術加速VARINT-GB格式的解碼已證明未能成功。下面的摘要概述了原因。

要了解為什麼與Varint-G8IU格式相比，要加速在VARINT-GB格式中壓縮數據的解碼可能很難，請考慮我們不能比訪問控件字節更快地解碼速度。在Varint-G8IU中，控製字節總是很方便地定位了9個壓縮字節。因此，當對控件字節進行處理或甚至之前，我們的SuperScalar處理器可以加載並開始處理即將到來的控製字節，因為它們的位置是可以預測的。根據這些控製字節，可以由處理器重新排序說明以獲得最佳性能。但是，在VARINT-GB格式中，存在一個強大的數據依賴性：下一個控件字節的位置取決於當前控件字節。這增加了處理器未充分利用的風險，這會因發出下一個控製字節的負載與等待其準備就緒之間的延遲延遲。

此外，他們證明，一次使用128位寄存器一次解碼4個整數要比試圖解碼適合8字節寄存器的可變數量的整數，即Varint-G8IU方法。

SIMD控製字節生成算法

Lemire等。已經設計了一種出色的SIMD算法，用於同時為一個8個整數組生成兩個控製字節。理解該算法的最佳方法是了解其在單個整數上的工作原理，然後假設其以矢量形式起作用（確實可以）。展望未來，我們將使用控制位流來表示我們正在構建的控製字節。 

 00000000 00000000 00000100 11010010 // 1234

讓我們以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位值。

為什麼在後續步驟中執行此操作將變得更加清楚，但是，對於要編碼的每個整數，您都希望在控制位流中的兩個連續字節的MSB代表最終的2位控制。例如，如果您有一個3字節整數，則希望以該順序為1和0的MSB為1和0。您想要的原因是，有一個矢量包指令將MSB從控制位流中的每個字節中獲取並將其包裝到最低字節中。因此，這將代表最終字節中這個3字節整數的值0b10 ，這是我們想要的。

執行16位至8位未簽名的飽和包的效果，您可以使用飽和行為有條件地打開這些字節的MSB，這取決於字節在原始的32位整數中具有值。 

 00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111

然後，我們採用以前使用的1個面具，並執行簽名的16位最小操作。如果您使用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位最小操作具有三個重要效果。

首先，對於三字節整數，它具有關閉最低字節的MSB的效果。這是必要的，因為一個3字節整數應具有0b10的2位控件，並且沒有此步驟，使用MSB PACK操作將導致2位控件看起來像0b_1 ，最低位為ON。顯然，這是錯誤的，因為只有需要編碼2或4個字節的整數應具有較低的位，即1或3作為零索引長度。

其次，對於4個字節整數，簽名的方面的作用是將兩個字節的兩個MSB留在上面。稍後使用MSB Pack操作時，它將導致2位控制值為0b11 ，這是我們想要的。

第三，對於1和2個字節整數，它沒有效果。這對於2字節值非常有用，因為MSB將保留在上面，並且無論如何都不會有任何MSB，因此在兩種情況下，這實際上都是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的值，這是我們想要的。 Integer 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位未簽名的飽和添加的效果可以打開下部字節中的所有位，因此我們在下部字節中獲得了一個結果。 

 01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask 
00000000 00000000 00000000 00000010 // 2-bit control

最終的MOVE字節掩碼是在控制位流上執行的，現在我們有了所需的結果。現在您可以看到它適用於1個整數，您知道它如何同時適用於8個整數，因為我們使用在128位寄存器上運行的矢量說明。

SIMD整數包裝/解開包裝

要解決的下一個問題是如何使用一組4個整數，並通過刪除外部/未使用的字節來壓縮它，以便您剩下的只是具有真實信息的數據字節。讓我們從上面的示例中獲取兩個數字。 

               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陣列。

參考

流Vbyte：更快面向字節的整數壓縮

展開
附加信息
相關應用
爲您推薦
相關資訊 全部