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 그룹 Varint 접근 방식과 동일한 기본 형식을 사용합니다. Lemire et al. 성능을 더욱 향상시킬 수있는 방법이 있는지 확인하고 Simd 기술을 통해 더 나은 성능을 가능하게하기 위해 영리한 트위스트를 도입했습니다. Group Varint 형식의 기본 목표는 정수의 vbyte 형식과 유사한 압축 특성을 달성 할 수 있고 실제로 빠르게로드하고 처리 할 수 있다는 것입니다.
vbyte 인코딩을 뒷받침하는 통찰력은 종종 32 비트 정수를 인코딩하기 위해 32 비트가 필요하지 않다는 것을 알게됩니다. 예를 들어 2^8 (256) 미만의 서명되지 않은 정수를 예로 들어보십시오. 이 정수에는 32 비트 정수의 가장 낮은 바이트에 비트가 설정되어 있고 나머지 3 바이트는 단순히 0이됩니다.
111 in binary:
00000000 00000000 00000000 01101111
이 정수를 압축하기 위해 취할 수있는 접근법은 가변 수의 바이트를 사용하여 정수를 인코딩하는 것입니다. 예를 들어, 낮은 7 비트를 사용하여 데이터를 저장, 즉 원래 정수의 비트를 저장 한 다음 MSB를 연속 비트로 사용할 수 있습니다. MSB 비트가 켜져 있으면이 특정 정수를 해독하기 위해 더 많은 바이트가 필요합니다. 아래는 숫자 1234를 저장하기 위해 2 바이트가 필요한 예입니다.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
이 정수를 해독하려면 단순히 숫자를 반복적으로 구축합니다. 즉, 모든 바이트의 마지막 7 비트는 연속 비트 세트가없는 바이트를 찾을 때까지 32 비트 정수로 적절한 길이로 이동했습니다. 이것은 64 비트 숫자와 동일하게 작동합니다.
이 접근법의 문제점은 인코딩/디코딩 중에 많은 지점 잘못 예측을 도입 할 수 있다는 것입니다. 디코딩 단계에서는 현재 처리중인 정수를 인코딩하는 데 사용 된 바이트 수를 미리 알지 못하므로 연속 비트가없는 바이트를 찾을 때까지 반복해야합니다. 불균일 한 정수가있는 경우, 즉 서로에 대해 임의의 바이트가 필요한 임의의 바이트가 필요한 정수가있는 경우 프로세서의 분기 예측 변수에 도전 할 수 있습니다. 이러한 잘못된 예측은 프로세서 파이프 라인에서 큰 둔화를 일으킬 수 있으며 그룹 변형 형식에서 태어났습니다.
Group Varint (Varint-GB) 형식은 달성하고자하는 모든 것을 32 비트 정수로 할 수 있다고 가정합니다. 그것은 단순히 4 32 비트 정수 그룹의 인코딩 된 길이를 저장하는 바이트 인 제어 바이트의 개념을 소개합니다. 32 비트 정수는 올바르게 인코딩하기 위해 최대 4 바이트 만 있으면됩니다. 즉, 제로 인드 덱스 길이의 길이를 사용하여 길이를 각각 1, 2, 3 및 4 바이트를 필요로하는 정수를 나타 내기 위해 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
그런 다음 4 개의 인코딩 된 32 비트 정수 그룹의 모든 그룹을 제어 바이트로 접두사 한 다음 디코딩 중에 사용할 수 있습니다. 명백한 단점은 인코딩하려는 4 개의 정수마다 1 바이트의 스토리지 비용을 지불한다는 것입니다. 2^20 인코딩 된 정수의 경우 256kB의 추가 공간입니다. 그러나 큰 상승은 이제 디코딩 단계에서 거의 모든 지점을 제거했다는 것입니다. 특정 숫자에 대한 버퍼에서 읽어야 할 데이터 바이트 수를 정확히 알고 있으며 Branchless Decoding을 사용할 수 있습니다.
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 개의 압축 바이트 간격으로 편리하게 위치합니다. 따라서 제어 바이트가 처리되는 동안 또는 심지어 이전에도 SuperScalar 프로세서는 위치가 예측 가능하면 다가오는 제어 바이트를로드하고 시작할 수 있습니다. 이러한 제어 바이트에 따라 지침은 프로세서에서 최상의 성능을 위해 재정렬 할 수 있습니다. 그러나 Varint-GB 형식에는 강력한 데이터 종속성이 있습니다. 다음 제어 바이트의 위치는 전류 제어 바이트에 따라 다릅니다. 이로 인해 프로세서가 활용률이 낮아질 위험이 높아져 다음 제어 바이트의 부하를 발행하고 준비되기를 기다리는 사이의 대기 시간에 의해 지연됩니다.
또한 128 비트 레지스터를 사용하여 한 번에 4 개의 정수를 디코딩하는 것이 8 바이트 레지스터에 맞는 가변 수의 정수를 디코딩하는 것보다 더 빠릅니다.
Lemire et al. 8 개의 정수 그룹에 대해 2 개의 제어 바이트를 동시에 생성하기위한 훌륭한 SIMD 알고리즘을 고안했습니다. 이 알고리즘을 이해하는 가장 좋은 방법은 단일 정수에서 작동하는 방법을 이해 한 다음 벡터화 된 형태로 작동한다고 가정하는 것입니다. 앞으로 우리는 제어 비트 스트림을 사용하여 우리가 구축하는 이러한 제어 바이트를 나타냅니다.
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 비트 값으로 포화됩니다.
그러나이를 수행하는 이유는 다음 단계에서 높은 수준에서 더 명확해질 것입니다. 높은 수준에서 인코딩하려는 모든 정수에 대해 제어 비트 스트림의 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 's 마스크를 가져 와서 서명 된 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 비트 최소 작업에는 세 가지 중요한 효과가 있습니다.
첫째, 3 바이트 정수의 경우 가장 낮은 바이트의 MSB를 끄는 효과가 있습니다. 3 바이트 정수는 0b10 인 2 비트 컨트롤이 있어야하며 MSB 팩 작업을 사용하지 않으면 가장 낮은 비트가 켜져있는 0b_1 과 같은 2 비트 컨트롤이 발생하기 때문에 필요합니다. 인코딩하기 위해 2 또는 4 바이트가 필요한 정수만이 해당 하단 비트 (예 : 1 또는 3)가 0 인덱스 길이 로야하므로 이것은 잘못된 것입니다.
둘째, 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
여기서 상단 바이트 만 값을 가졌기 때문에 제어 비트 스트림에서 가장 낮은 바이트는 알고리즘 지속 시간 동안 0으로 유지됩니다. 4 바이트 값의 경우 2 비트 제어가 0b11 의 값을 초래하기를 원하기 때문에 문제가 발생합니다. 16 비트 서명되지 않은 포화 첨가를 수행하면 하부 바이트의 모든 비트를 켜는 효과가 있으므로 하부 바이트 ON의 MSB로 결과를 얻습니다.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
최종 이동 바이트 마스크는 Control Bits 스트림에서 수행되며 이제 원하는 결과를 얻었습니다. 이제 이것은 1 정수에 대해 작동한다는 것을 알았으므로 128 비트 레지스터에서 작동하는 벡터 지침을 사용하기 때문에 8 개의 정수에서 동시에 작동하는 방법을 알 수 있습니다.
다음으로 해결해야 할 문제는 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 : 더 빠른 바이트 지향 정수 압축
