streamvbyte simdgo
v0.4.0
Este é um repositório que contém uma porta de stream vbyte para ir. Notavelmente, esse repositório toma cuidado extra para alavancar as técnicas SIMD para obter melhor desempenho. Atualmente, há suporte para arquiteturas x86_64 que possuem instruções de hardware AVX e AVX2. Nos casos em que isso não está disponível ou nas arquiteturas não x86_64, há uma implementação escalar portátil. Também realizamos uma verificação de tempo de execução para garantir que o ISA necessário esteja disponível e, se não for, fallback para a abordagem escalar.
Existem várias implementações existentes:
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
Uma nota sobre os benchmarks: uma variedade de UINT32 aleatória é gerada e depois codificada/decodificada repetidamente. É feita uma tentativa de garantir que alguns desses benchmarks reflitam as métricas de desempenho do mundo real mais prováveis.
Stream VBYTE usa o mesmo formato subjacente que a abordagem do Grupo Varint do Google. Lemire et al. Queria ver se havia uma maneira de melhorar ainda mais o desempenho e introduziu uma reviravolta inteligente para permitir um melhor desempenho por meio de técnicas SIMD. O objetivo básico do formato Varint do grupo é conseguir obter características de compressão semelhantes ao formato VBYTE para números inteiros e também carregá -los e processá -los muito rapidamente.
O insight que apóia a codificação VBYTE está percebendo que você muitas vezes não precisa de 32 bits para codificar um número inteiro de 32 bits. Tomemos, por exemplo, um número inteiro não assinado que é menor que 2^8 (256). Esse número inteiro terá bits definidos no byte mais baixo de um número inteiro de 32 bits, enquanto os 3 bytes restantes serão simplesmente zeros.
111 in binary:
00000000 00000000 00000000 01101111
Uma abordagem que você pode adotar para comprimir esse número inteiro é codificar o número inteiro usando um número variável de bytes. Por exemplo, você pode usar os 7 bits inferiores para armazenar dados, ou seja, bits do número inteiro original e, em seguida, usar o MSB como um bit de continuação. Se o bit msb estiver ligado, ou seja, é 1, mais bytes serão necessários para decodificar esse número inteiro em particular. Abaixo está um exemplo em que você pode precisar de 2 bytes para armazenar o número 1234.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
Se você deseja decodificar esse número inteiro, basta criar o número iterativamente. Ou seja, você ou os últimos 7 bits de todos os bytes mudaram para o comprimento apropriado para o seu número inteiro de 32 bits até encontrar um byte que não tenha um conjunto de bits de continuação. Observe que isso funciona da mesma forma para números de 64 bits.
O problema com essa abordagem é que ela pode introduzir muitas predefições incorretas de ramo durante a codificação/decodificação. Durante a fase de decodificação, você não sabe com antecedência o número de bytes que foram usados para codificar o número inteiro que você está processando atualmente e, portanto, precisa iterar até encontrar um byte sem um bit de continuação. Se você tem números inteiros não uniformes, ou seja, números inteiros que exigem um número aleatório de bytes para codificar em relação um ao outro, isso pode representar um desafio ao preditor de ramo do processador. Essas predições incorretas podem causar grandes desacelerações nos oleodutos de processador e, portanto, nasceu o formato Varint do grupo.
O formato Group Varint (Varint-GB) assume que tudo o que você espera alcançar, você pode fazer com números inteiros de 32 bits. Ele introduz o conceito de um byte de controle que é simplesmente um byte que armazena os comprimentos codificados de um grupo de 4 números inteiros de 32 bits, portanto, o grupo Varint. Os números inteiros de 32 bits requerem apenas até 4 bytes para codificar corretamente. Isso significa que você pode representar seus comprimentos com 2 bits usando um comprimento indexado por zero, IE 0, 1, 2 e 3, para representar números inteiros que requerem 1, 2, 3 e 4 bytes para codificar, respectivamente.
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
Você pode prefixar todos os grupos de 4 números inteiros codificados de 32 bits com seu byte de controle e depois usá-lo durante a decodificação. A desvantagem óbvia é que você paga um custo de armazenamento de um byte para cada 4 números inteiros que deseja codificar. Para 2^20 inteiros codificados, são 256 kb extras de espaço extra: totalmente marginal. A grande vantagem, no entanto, é que você agora removeu quase todas as filiais da sua fase de decodificação. Você sabe exatamente quantos bytes de dados você precisa ler de um buffer para um número específico e, em seguida, pode usar a decodificação sem ramificação.
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
}Infelizmente, a aceleração da decodificação do formato Varint-GB com apenas técnicas SIMD se mostrou malsucedida. O trecho abaixo do artigo descreve o porquê.
Para entender por que pode ser difícil acelerar a decodificação de dados compactados no formato VARINT-GB em comparação com o formato Varint-G8IU, considere que não podemos decodificar mais rapidamente do que podemos acessar os bytes de controle. Em Varint-G8IU, os bytes de controle estão convenientemente localizados, nove bytes compactados. Assim, enquanto um byte de controle está sendo processado, ou mesmo antes, nosso processador superescalar pode carregar e começar a processar os próximos bytes de controle, pois seus locais são previsíveis. As instruções, dependendo desses bytes de controle, podem ser reordenadas pelo processador para obter o melhor desempenho. No entanto, no formato VARINT-GB, há uma forte dependência de dados: a localização do próximo byte de controle depende do byte de controle atual. Isso aumenta o risco de que o processador permaneça subutilizado, atrasado pela latência entre emitir a carga para o próximo byte de controle e esperar que ele esteja pronto.
Além disso, eles provam que a decodificação de 4 números inteiros por vez usando registros de 128 bits é mais rápida do que tentar decodificar um número variável de números inteiros que se encaixam em um registro de 8 bytes, ou seja, a abordagem Varint-G8IU.
Lemire et al. desenvolveram um brilhante algoritmo SIMD para gerar simultaneamente dois bytes de controle para um grupo de 8 números inteiros. A melhor maneira de entender esse algoritmo é entender como ele funciona em um único número inteiro e, em seguida, assumir que funciona de forma vetorizada (ele faz). No futuro, usaremos o fluxo de bits de controle para representar esses bytes de controle que estamos construindo.
00000000 00000000 00000100 11010010 // 1234
Vamos pegar um dos números inteiros anteriores que estávamos olhando, 1234 , e percorrer um exemplo de como o controle de 2 bits é gerado para ele usando técnicas SIMD. O objetivo é poder, para qualquer número inteiro de 32 bits, gerar um valor de comprimento indexado zero de 2 bits. Por exemplo, se você tiver um número inteiro que exige que 2 bytes sejam codificados, queremos que o algoritmo gere 0b01 .
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
O algoritmo primeiro usa uma máscara onde todo byte é igual a 1. Se você executar uma operação por byte min em nosso número inteiro e a máscara de 1, o resultado terá um 1 em todos os bytes que tinham um valor no número inteiro original.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
Agora você realiza uma operação de pacote de saturação não assinada de 16 bits a 8 bits. Praticamente isso significa que você está assumindo todo valor de 16 bits e tentando empurrar isso em 8 bits. Se o número inteiro de 16 bits for maior que o maior número inteiro sem assinatura, 8 bits poderão suportar, o pacote satura com o maior valor de 8 bits não assinado.
Por que isso é realizado se tornará mais claro nas etapas subsequentes, no entanto, em alto nível, para cada número inteiro que você deseja codificar, você deseja que o MSB de dois bytes consecutivos no fluxo de bits de controle seja representativo do controle final de 2 bits. Por exemplo, se você tiver um número inteiro de 3 bytes, deseja que o MSB de dois bytes consecutivos seja 1 e 0, nessa ordem. A razão pela qual você deseja que isso seja que exista uma instrução de pacote vetorial que pega o MSB de todos os bytes no fluxo de bits de controle e o inclua no byte mais baixo. Isso representaria assim o valor 0b10 no byte final para esse número inteiro de 3 bytes, que é o que queremos.
A realização de um pacote de saturação não assinado de 16 bits a 8 bits tem o efeito de que você pode usar o comportamento de saturação para ativar condicionalmente o MSB desses bytes, dependendo dos quais bytes têm valores no número inteiro original de 32 bits.
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
Em seguida, pegamos a máscara do 1 que usamos antes e realizamos uma operação MIN de 16 bits assinada . A razão para isso é mais clara se você olhar para um exemplo usando um número inteiro de 3 bytes.
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
A operação MIN de 16 bits assinada tem três efeitos importantes.
Primeiro, para inteiros de 3 bytes, isso tem o efeito de desligar o MSB do byte mais baixo. Isso é necessário porque um número inteiro de 3 bytes deve ter um controle de 2 bits que seja 0b10 e sem esta etapa usando a operação do pacote MSB resultaria em um controle de 2 bits que se parece com 0b_1 , onde o bit mais baixo está ligado. Obviamente, isso está errado, já que apenas os números inteiros que exigem 2 ou 4 bytes para codificar devem ter esse bit mais baixo, ou seja, 1 ou 3 como um comprimento indexado por zero.
Segundo, para números inteiros de 4 bytes, o aspecto assinado tem o efeito de deixar os dois MSBs dos 2 bytes. Ao usar a operação do MSB Pack mais tarde, isso resultará em um valor de controle de 2 bits de 0b11 , que é o que queremos.
Terceiro, para 1 e 2 inteiros de bytes, isso não tem efeito. Isso é ótimo para valores de 2 bytes, pois o MSB permanecerá no e 1 bytes, os valores não terão nenhum MSB de qualquer maneira, por isso é efetivamente um Noop nos dois cenários.
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
Em seguida, pegamos uma máscara com o valor 0x7F00 e executamos uma saturação não assinada Adicionar ao fluxo de bits de controle. No caso do número inteiro 1234 isso não tem efeito real. Mantemos o MSB no byte mais baixo. Você notará, no entanto, que o único byte que possui seu MSB é o último, portanto, executar uma operação do MSB Pack resultaria em um valor de 0b0001 , que é o que queremos. Um exemplo desta etapa no número inteiro 789123 pode pintar uma imagem mais clara.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
Você notará aqui que a adição de 0x01 com 0x7F no byte superior resulta no MSB do byte superior resultante ligando. O MSB no byte inferior permanece desativado e agora uma operação do MSB Pack será resolvida para 0b0010 , que é o que queremos. O comportamento de saturação não assinado é realmente importante para números de 4 bytes que só têm bits no byte mais significativo. Um exemplo abaixo:
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
Observe aqui que, como apenas o byte superior tinha um valor, o byte mais baixo no fluxo de bits de controle permanece zero durante o algoritmo. Isso representa um problema, pois, para um valor de 4 bytes, queremos que o controle de 2 bits resultem em um valor de 0b11 . A realização de uma adição de 16 bits não assinada tem o efeito de ativar todos os bits no byte inferior e, portanto, obtemos um resultado com o MSB no byte inferior ligado.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
A máscara de bytes de movimento final é realizada no fluxo de bits de controle e agora temos o resultado que queríamos. Agora que você vê que isso funciona para 1 número inteiro, você sabe como ele pode funcionar para 8 números inteiros simultaneamente, pois usamos instruções vetoriais que operam em registros de 128 bits.
O próximo problema a ser resolvido é como pegar um grupo de 4 números inteiros e comprimi -lo removendo bytes estranhos/não utilizados, para que tudo o que você resta é um fluxo de bytes de dados com informações reais. Vamos tirar dois números de nossos exemplos acima.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
Aqui, podemos usar uma operação de embaralhamento. O Vector Shuffle Operations reorganiza os bytes em um registro de entrada de acordo com algumas máscara fornecidas em um registro de destino. Toda posição na máscara armazena um deslocamento no fluxo de vetores de origem que representa o byte de dados que deve entrar nessa posição.
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
Mantemos uma tabela de pesquisa pré -construída que contém um mapeamento do byte de controle para a máscara necessária e simplesmente carregue isso depois de construir o byte de controle acima. Além disso, mantemos uma tabela de pesquisa para um mapeamento de bytes de controle para o comprimento codificado total. Isso nos permite saber quanto para incrementar o ponteiro de saída e substituir, por exemplo, os 3 bytes superiores redundantes no exemplo do Shuffle acima.
Desenvolver durante a decodificação é o mesmo que acima, mas ao contrário. Precisamos ir de um formato empacotado para um formato de memória descompactado. Mantemos as tabelas de pesquisa para manter um mapeamento do byte de controle para a máscara de embaralhamento reversa e, em seguida, executam uma operação de embaralhamento para produzir uma matriz uint32 .
Stream Vbyte: compressão inteira mais rápida orientada a bytes
