首页>编程相关>其他源码
下载

流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：更快面向字节的整数压缩

展开
附加信息
相关应用
为您推荐
相关资讯 全部