streamvbyte simdgo
v0.4.0
Este es un repositorio que contiene un puerto de transmisión VByte para ir. En particular, este repositorio tiene mucho cuidado para aprovechar las técnicas SIMD para lograr un mejor rendimiento. Actualmente, hay soporte para las arquitecturas X86_64 que tienen instrucciones de hardware AVX y AVX2. En los casos en que eso no está disponible, o en arquitecturas no X86_64, existe una implementación escalar portátil. También realizamos una verificación de tiempo de ejecución para asegurarnos de que la ISA necesaria esté disponible y, si no el enfoque escalar al escalar.
Hay varias implementaciones 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
Una nota en los puntos de referencia: se genera una matriz de UINT32 aleatorias y luego se codifica/decodifica una y otra vez. Se intenta garantizar que algunos de estos puntos de referencia reflejen las métricas de rendimiento del mundo real más probable.
Stream VByte utiliza el mismo formato subyacente que el enfoque de VarInt del grupo de Google. Lemire et al. Quería ver si había una manera de mejorar el rendimiento aún más e introdujo un giro inteligente para permitir un mejor rendimiento a través de técnicas SIMD. El objetivo básico del formato de varint de grupo es poder lograr características de compresión similares como el formato VBYTE para enteros y también poder cargarlos y procesarlos muy rápidamente.
La idea que respalda la codificación VByte es notar que a menudo no necesita 32 bits para codificar un entero de 32 bits. Tomemos, por ejemplo, un entero sin firmar que es inferior a 2^8 (256). Este entero tendrá bits establecidos en el byte más bajo de un entero de 32 bits, mientras que los 3 bytes restantes simplemente serán ceros.
111 in binary:
00000000 00000000 00000000 01101111
Un enfoque que puede adoptar para comprimir este entero es codificar el entero utilizando un número variable de bytes. Por ejemplo, puede usar los 7 bits más bajos para almacenar datos, es decir, bits del entero original, y luego usar el MSB como un bit de continuación. Si el bit MSB está encendido, es decir, es 1, entonces se necesitan más bytes para decodificar este entero en particular. A continuación se muestra un ejemplo en el que es posible que necesite 2 bytes para almacenar el número 1234.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
Si desea decodificar este entero, simplemente construya el número de iteración. Es decir, usted o los últimos 7 bits de cada byte se desplazaron a la longitud apropiada a su número entero de 32 bits hasta que encuentre un byte que no tenga un conjunto de bits de continuación. Tenga en cuenta que esto funciona igual para números de 64 bits.
El problema con este enfoque es que puede introducir muchas predicciones erróneas de ramas durante la codificación/decodificación. Durante la fase de decodificación, no sabe con anticipación el número de bytes que se usaron para codificar el entero que está procesando actualmente y, por lo tanto, debe iterar hasta que encuentre un byte sin un poco de continuación. Si tiene enteros que no son uniformes, es decir, enteros que requieren números aleatorios de bytes para codificar entre sí, esto puede plantear un desafío para el predictor de la rama del procesador. Estas predicciones erróneas pueden causar ralentizaciones importantes en las tuberías de procesadores y, por lo tanto, nació el formato Varint del grupo.
El formato del grupo Varint (VarInt-GB) supone que todo lo que espera lograr, puede hacer con enteros de 32 bits. Introduce el concepto de un byte de control que es simplemente un byte que almacena las longitudes codificadas de un grupo de 4 enteros de 32 bits, por lo tanto, el grupo Varint. Los enteros de 32 bits solo requieren hasta 4 bytes para codificar correctamente. Esto significa que puede representar sus longitudes con 2 bits utilizando una longitud de índice cero, es decir, 0, 1, 2 y 3 para representar enteros que requieren 1, 2, 3 y 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
Luego puede prefirir cada grupo de 4 enteros codificados de 32 bits con su byte de control y luego usarlo durante la decodificación. El inconveniente obvio es que paga un costo de almacenamiento de un byte por cada 4 enteros que desea codificar. Para 2^20 enteros codificados, son un espacio adicional de 256 kb de espacio adicional: totalmente marginal. Sin embargo, la gran ventaja es que ahora ha eliminado casi todas las ramas de su fase de decodificación. Sabe exactamente cuántos bytes de datos necesita leer desde un búfer para un número particular y luego puede usar decodificación sin sucursales.
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
}Desafortunadamente, acelerar la decodificación del formato VarInt-GB con solo técnicas SIMD ha demostrado que no tiene éxito. El siguiente extracto del documento describe por qué.
Para comprender por qué podría ser difícil acelerar la decodificación de los datos comprimidos en el formato VarInt-GB en comparación con el formato VARINT-G8IU, considere que no podemos decodificar más rápido de lo que podemos acceder a los bytes de control. En Varint-G8IU, los bytes de control están convenientemente ubicados a nueve bytes comprimidos de distancia. Por lo tanto, mientras se procesa un byte de control, o incluso antes, nuestro procesador superscalar puede cargar y comenzar a procesar los próximos bytes de control, ya que sus ubicaciones son predecibles. El procesador puede reordenar las instrucciones que dependen de estos bytes de control para el mejor rendimiento. Sin embargo, en el formato VarInt-GB, existe una fuerte dependencia de datos: la ubicación del siguiente byte de control depende del byte de control actual. Esto aumenta el riesgo de que el procesador permanezca subutilizado, retrasado por la latencia entre emitir la carga para el próximo byte de control y esperar a que esté listo.
Además, prueban que decodificar 4 enteros a la vez que usan registros de 128 bits es más rápido que tratar de decodificar un número variable de enteros que se ajustan a un registro de 8 bytes, es decir, el enfoque Varint-G8IU.
Lemire et al. han ideado un algoritmo SIMD brillante para generar simultáneamente dos bytes de control para un grupo de 8 enteros. La mejor manera de comprender este algoritmo es comprender cómo funciona en un solo entero y luego asumir que funciona en forma vectorizada (lo hace). En el futuro, usaremos la transmisión de bits de control para representar estos bytes de control que estamos construyendo.
00000000 00000000 00000100 11010010 // 1234
Tomemos uno de los enteros anteriores que estábamos viendo, 1234 , y pase por un ejemplo de cómo se genera el control de 2 bits utilizando técnicas SIMD. El objetivo es poder, para cualquier número entero de 32 bits, generar un valor de longitud indexada cero de 2 bits. Por ejemplo, si tiene un entero que requiere que se codifiquen 2 bytes, queremos que el algoritmo genere 0b01 .
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
El algoritmo primero usa una máscara donde cada byte es igual a 1. Si realiza una operación mínima por byte en nuestro entero y la máscara de 1, el resultado tendrá un 1 en cada byte que tuviera un valor en el entero original.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
Ahora realiza una operación de paquete saturante sin firmar de 16 bits a 8 bits. Prácticamente esto significa que está tomando cada valor de 16 bits e intentando empujarlo en 8 bits. Si el número entero de 16 bits es más grande que el mayor entero sin firmar que 8 bits pueden soportar, el paquete se satura al mayor valor de 8 bits sin firmar.
Por qué se realiza esto se volverá más claro en los pasos posteriores, sin embargo, en un alto nivel, por cada entero que desee codificar, desea que el MSB de dos bytes consecutivos en la corriente de bits de control sea representativo del control final de 2 bits. Por ejemplo, si tiene un entero de 3 bytes, desea que el MSB de dos bytes consecutivos sea 1 y 0, en ese orden. La razón por la que desea esto es que hay una instrucción de paquete de vectores que toma el MSB de cada byte en la corriente de bits de control y la empaca en el byte más bajo. Por lo tanto, esto representaría el valor 0b10 en el byte final para este entero de 3 bytes, que es lo que queremos.
Realizar un paquete saturado sin firmar de 16 bits a 8 bits tiene el efecto de que puede usar el comportamiento de saturación para activar condicionalmente el MSB de estos bytes dependiendo de qué bytes tengan valores en el entero 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
Luego tomamos la máscara de 1 que usamos antes y realizamos una operación mínima de 16 bits firmada . La razón de esto es más clara si observa un ejemplo usando un entero 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
La operación mínima firmada de 16 bits tiene tres efectos importantes.
Primero, para enteros de 3 bytes, tiene el efecto de apagar el MSB del byte más bajo. Esto es necesario porque un entero de 3 bytes debe tener un control de 2 bits que sea 0b10 y sin este paso utilizando la operación del paquete MSB daría como resultado un control de 2 bits que se parece a 0b_1 , donde está el bit más bajo. Obviamente, esto está mal, ya que solo los enteros que requieren 2 o 4 bytes para codificar deberían tener ese bit más bajo encendido, es decir, 1 o 3 como una longitud indexada por cero.
En segundo lugar, para enteros de 4 bytes, el aspecto firmado tiene el efecto de dejar ambos MSB de los 2 bytes. Al usar la operación del paquete MSB más adelante, dará como resultado un valor de control de 2 bits de 0b11 , que es lo que queremos.
Tercero, para enteros de 1 y 2 bytes, no tiene ningún efecto. Esto es excelente para los valores de 2 bytes, ya que el MSB permanecerá encendido y los valores de 1 byte no tendrán ningún MSB en todos modos, por lo que es efectivamente un NOOP en ambos escenarios.
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
A continuación, tomamos una máscara con el valor 0x7F00 y realizamos un agregado saturante sin firmar a la corriente de bits de control. En el caso del entero 1234 esto no tiene ningún efecto real. Mantenemos el MSB en el byte más bajo. Sin embargo, observará que el único byte que tiene su MSB es el último, por lo que realizar una operación de paquete MSB daría como resultado un valor de 0b0001 , que es lo que queremos. Un ejemplo de este paso en el entero 789123 podría pintar una imagen más clara.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
Notarás aquí que la adición de 0x01 con 0x7F en el byte superior da como resultado el MSB del byte superior resultante activado. El MSB en el byte inferior permanece apagado y ahora una operación de MSB Pack se resolverá a 0b0010 , que es lo que queremos. El comportamiento de saturación sin firmar es realmente importante para los números de 4 bytes que solo tienen bits en el byte más significativo. Un ejemplo a continuación:
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
Tenga en cuenta aquí que debido a que solo el byte superior tenía un valor en él, el byte más bajo en la corriente de bits de control sigue siendo cero durante la duración del algoritmo. Esto plantea un problema, ya que para un valor de 4 bytes, queremos que el control de 2 bits resulte en un valor de 0b11 . La realización de una adición saturante sin firmar de 16 bits tiene el efecto de activar todos los bits en el byte inferior, y por lo tanto obtenemos un resultado con el MSB en el byte inferior encendido.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
La máscara de byte de movimiento final se realiza en la secuencia de bits de control, y ahora tenemos el resultado que queríamos. Ahora que ve que esto funciona para 1 entero, sabe cómo puede funcionar para 8 enteros simultáneamente, ya que utilizamos instrucciones vectoriales que operan en registros de 128 bits.
El siguiente problema a resolver es cómo tomar un grupo de 4 enteros y comprimirlo eliminando bytes extraños/no utilizados para que todo lo que le quede es un flujo de bytes de datos con información real. Tomemos dos números de nuestros ejemplos anteriores.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
Aquí, podemos usar una operación de baraja. Las operaciones de vectores Shuffle reorganizan los bytes en un registro de entrada de acuerdo con alguna máscara proporcionada en un registro de destino. Cada posición en la máscara almacena un desplazamiento en la secuencia de vectores de origen que representa el byte de datos que debe ir a esa posición.
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
Mantenemos una tabla de búsqueda preconstruida que contiene un mapeo del byte de control a la máscara necesaria y simplemente cargamos que después de construir el byte de control anterior. Además, mantenemos una tabla de búsqueda para un mapeo de bytes de control a una longitud codificada total. Esto nos permite saber por cuánto incrementar el puntero de salida y sobrescribir, por ejemplo, los 3 bytes superiores redundantes en el ejemplo de Shuffle anterior.
Desempacar durante la decodificación es lo mismo que el anterior, pero en reversa. Necesitamos pasar de un formato lleno a un formato de memoria desempaquetado. Mantenemos las tablas de búsqueda para mantener un mapeo desde el byte de control hasta la máscara de baraja inversa, y luego realizamos una operación de baraja para emitir una matriz uint32 .
Stream Vbyte: compresión entera orientada a bytes más rápida
