streamvbyte simdgo
v0.4.0
Il s'agit d'un référentiel qui contient un port de Stream Vbyte à aller. Notamment, ce repo prend plus de soin pour tirer parti des techniques SIMD pour obtenir de meilleures performances. Actuellement, il existe une prise en charge des architectures x86_64 qui ont des instructions matérielles AVX et AVX2. Dans les cas où cela n'est pas disponible, ou sur les architectures non x86_64, il existe une implémentation scalaire portable. Nous effectuons également un chèque d'exécution pour nous assurer que l'ISA nécessaire est disponible et si ce n'est pas un secours à l'approche scalaire.
Il existe plusieurs implémentations existantes:
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
Une note sur les repères: un tableau d'Uint32 aléatoire est généré puis codé / décodé encore et encore. Une tentative est faite pour garantir que certaines de ces repères reflètent les mesures de performance réelles les plus probables.
Stream Vbyte utilise le même format sous-jacent que l'approche de groupe Varint de Google. Lemire et al. Je voulais voir s'il y avait un moyen d'améliorer encore plus les performances et d'introduire une tournure intelligente pour permettre de meilleures performances via des techniques SIMD. L'objectif de base du format de groupe Varint est de pouvoir obtenir des caractéristiques de compression similaires à celles du format VByte pour les entiers et également de les charger et de les traiter très rapidement.
La perspicacité qui soutient le codage du VByte remarque que vous n'avez souvent pas besoin de 32 bits pour coder un entier 32 bits. Prenons par exemple un entier non signé qui est inférieur à 2 ^ 8 (256). Cet entier aura des bits réglés dans l'octet le plus bas d'un entier 32 bits, tandis que les 3 octets restants seront simplement des zéros.
111 in binary:
00000000 00000000 00000000 01101111
Une approche que vous pouvez adopter pour comprimer cet entier consiste à coder l'entier à l'aide d'un nombre variable d'octets. Par exemple, vous pouvez utiliser les 7 bits inférieurs pour stocker des données, c'est-à-dire des bits à partir de l'entier d'origine, puis utiliser le MSB comme bit de continuation. Si le bit MSB est allumé, IE est 1, alors plus d'octets sont nécessaires pour décoder cet entier particulier. Vous trouverez ci-dessous un exemple où vous pourriez avoir besoin de 2 octets pour stocker le numéro 1234.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
Si vous souhaitez décoder cet entier, vous construisez simplement le numéro de manière itérative. C'est-à-dire que vous ou les 7 derniers bits de chaque octet est passé à la longueur appropriée vers votre entier 32 bits jusqu'à ce que vous trouviez un octet qui n'a pas de bit de continuation. Notez que cela fonctionne de la même manière pour les numéros 64 bits.
Le problème avec cette approche est qu'il peut introduire beaucoup de mauvaise prédiction des branches lors de l'encodage / décodage. Pendant la phase de décodage, vous ne savez pas à l'avance le nombre d'octets utilisés pour coder l'entier que vous traitez actuellement et vous devez donc itérer jusqu'à ce que vous trouviez un octet sans bit de continuation. Si vous avez des entiers non uniformes, c'est-à-dire des entiers qui nécessitent un nombre aléatoire d'octets pour coder les uns par rapport aux autres, cela peut poser un défi au prédicteur de branche du processeur. Ces prédictions peuvent provoquer des ralentissements majeurs dans les pipelines de processeur et sont donc nés le format de groupe Varint.
Le format de groupe Varint (Varint-Gb) suppose que tout ce que vous espérez réaliser, vous pouvez faire avec des entiers 32 bits. Il introduit le concept d'un octet de contrôle qui est simplement un octet qui stocke les longueurs codées d'un groupe de 4 entiers 32 bits, d'où le groupe de groupe. Les entiers 32 bits ne nécessitent que jusqu'à 4 octets pour coder correctement. Cela signifie que vous pouvez représenter leurs longueurs avec 2 bits en utilisant une longueur indexée zéro IE 0, 1, 2 et 3 pour représenter les entiers qui nécessitent 1, 2, 3 octets pour coder, respectivement.
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
Vous pouvez ensuite préfixer chaque groupe d'entiers 32 bits codés avec leur octet de contrôle, puis l'utiliser pendant le décodage. L'inconvénient évident est que vous payez un coût de stockage d'un octet pour les 4 entiers que vous souhaitez encoder. Pour 2 ^ 20 entiers codés, c'est un plus de 256 Ko d'espace supplémentaire: totalement marginal. Le grand avantage, cependant, est que vous avez maintenant supprimé presque toutes les branches de votre phase de décodage. Vous savez exactement combien d'octets de données vous devez lire à partir d'un tampon pour un numéro particulier et pouvez ensuite utiliser le décodage sans branche.
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
}Malheureusement, accélérer le décodage du format Varint-GB avec uniquement des techniques SIMD s'est avéré infructueux. L'extrait ci-dessous du papier décrit pourquoi.
Pour comprendre pourquoi il pourrait être difficile d'accélérer le décodage des données compressé dans le format Varint-GB par rapport au format Varint-G8iu, considérons que nous ne pouvons pas décoder plus rapidement que nous ne pouvons accéder aux octets de contrôle. Dans Varint-G8iu, les octets de contrôle sont commodément situés à neuf octets comprimés. Ainsi, alors qu'un octet de contrôle est en cours de traitement, ou même avant, notre processeur superscalar peut charger et commencer à traiter les octets de contrôle à venir, car leurs emplacements sont prévisibles. Les instructions en fonction de ces octets de contrôle peuvent être réorganisées par le processeur pour les meilleures performances. Cependant, dans le format Varint-GB, il existe une forte dépendance des données: l'emplacement de l'octet de contrôle suivant dépend de l'octet de contrôle actuel. Cela augmente le risque que le processeur reste sous-utilisé, retardé par la latence entre l'émission de la charge pour le prochain octet de contrôle et l'attente pour qu'il soit prêt.
De plus, ils prouvent que le décodage de 4 entiers à la fois en utilisant des registres 128 bits est plus rapide que d'essayer de décoder un nombre variable d'entiers qui s'inscrivent dans un registre de 8 octets, c'est-à-dire l'approche Varint-G8iu.
Lemire et al. ont conçu un algorithme SIMD brillant pour générer simultanément deux octets de contrôle pour un groupe de 8 entiers. La meilleure façon de comprendre cet algorithme est de comprendre comment il fonctionne sur un seul entier, puis de supposer qu'il fonctionne sous une forme vectorisée (c'est le cas). À l'avenir, nous utiliserons le flux de bits de contrôle pour représenter ces octets de contrôle que nous construisons.
00000000 00000000 00000100 11010010 // 1234
Prenons l'un des entiers précédents que nous recherchions, 1234 , et parcourons un exemple de la façon dont le contrôle 2 bits est généré pour lui en utilisant des techniques SIMD. L'objectif est de pouvoir, pour tout entier de 32 bits, générer une valeur de longueur indexée à 2 bits zéro. Par exemple, si vous avez un entier qui nécessite que 2 octets soient codés, nous voulons que l'algorithme génére 0b01 .
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
L'algorithme utilise d'abord un masque où chaque octet est égal à 1. Si vous effectuez une opération minimale par octet sur notre entier et le masque du 1, le résultat aura un 1 à chaque octet qui avait une valeur dans l'entier d'origine.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
Maintenant, vous effectuez un fonctionnement de pack saturant 16 bits à 8 bits. En pratique, cela signifie que vous prenez chaque valeur 16 bits et essayez de pousser cela en 8 bits. Si l'entier 16 bits est plus grand que le plus grand entier non signé, 8 bits peuvent prendre en charge, le pack sature à la plus grande valeur 8 bits non signée.
La raison pour laquelle cela est effectué deviendra plus clair dans les étapes suivantes, cependant, à un niveau élevé, pour chaque entier que vous souhaitez coder, vous voulez pour le MSB de deux octets consécutifs dans le flux de bits de contrôle représentatif du contrôle final 2 bits. Par exemple, si vous avez un entier de 3 octets, vous voulez que le MSB de deux octets consécutifs soit 1 et 0, dans cet ordre. La raison pour laquelle vous voudriez cela est qu'il existe une instruction de pack vector qui prend le MSB de chaque octet du flux de bits de commande et le met dans l'octet le plus bas. Cela représenterait ainsi la valeur 0b10 dans l'octet final pour cet entier de 3 octets, ce que nous voulons.
La réalisation d'un pack saturant 16 bits à 8 bits a pour effet que vous pouvez utiliser le comportement de saturation pour activer conditionnellement le MSB de ces octets en fonction des octets qui ont des valeurs dans l'entier 32 bits d'origine.
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
Nous prenons ensuite le masque du 1 que nous avons utilisé auparavant et effectuons une opération signée à 16 bits min. La raison en est plus claire si vous regardez un exemple en utilisant un entier de 3 octets.
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
L'opération Min en 16 bits signée a trois effets importants.
Premièrement, pour les entiers de 3 octets, il a pour effet de désactiver le MSB de l'octet le plus bas. Cela est nécessaire car un entier de 3 octets devrait avoir un contrôle 2 bits qui est 0b10 et sans cette étape en utilisant l'opération MSB Pack entraînerait un contrôle 2 bits qui ressemble à 0b_1 , où le bit le plus bas est allumé. De toute évidence, cela est faux, car seuls les entiers qui nécessitent 2 ou 4 octets pour encoder devraient avoir ce bit inférieur, c'est-à-dire 1 ou 3 comme une longueur indexée zéro.
Deuxièmement, pour les entiers de 4 octets, l'aspect signé a pour effet de laisser les deux MSB des 2 octets. Lorsque vous utilisez l'opération MSB Pack ultérieurement, cela se traduira par une valeur de contrôle 2 bits de 0b11 , ce que nous voulons.
Troisièmement, pour les entiers de 1 et 2 octets, cela n'a aucun effet. Ceci est idéal pour les valeurs de 2 octets, car le MSB restera activé et les valeurs d'octets n'auront pas de MSB de toute façon, il s'agit donc effectivement d'un NOOP dans les deux scénarios.
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
Ensuite, nous prenons un masque avec la valeur 0x7F00 et effectuons un ajout saturant non signé au flux de bits de commande. Dans le cas de l'Intier 1234 cela n'a aucun effet réel. Nous maintenons le MSB dans l'octet le plus bas. Vous remarquerez, cependant, que le seul octet qui a son MSB est le dernier, donc effectuer une opération de pack MSB entraînerait une valeur de 0b0001 , ce que nous voulons. Un exemple de cette étape sur l'entier 789123 pourrait peindre une image plus claire.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
Vous remarquerez ici que l'ajout de 0x01 avec 0x7F dans l'octet supérieur se traduit par le MSB de l'octet supérieur résultant. Le MSB dans l'octet inférieur reste éteint et maintenant une opération de pack MSB se résoudra à 0b0010 , ce que nous voulons. Le comportement de saturation non signé est vraiment important pour les nombres de 4 octets qui n'ont que des bits dans l'octet le plus significatif. Un exemple ci-dessous:
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
Notez ici que parce que seul l'octet supérieur avait une valeur, l'octet le plus bas du flux de bits de commande reste nul pendant la durée de l'algorithme. Cela pose un problème, car pour une valeur de 4 octets, nous voulons que le contrôle 2 bits entraîne une valeur de 0b11 . La réalisation d'un ajout saturant non signé 16 bits a pour effet de tourner sur tous les bits dans l'octet inférieur, et donc nous obtenons un résultat avec le MSB dans l'octet inférieur.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
Le masque d'octet de mouvement final est effectué sur le flux de bits de contrôle, et nous avons maintenant le résultat que nous voulions. Maintenant que vous voyez que cela fonctionne pour 1 entier, vous savez comment cela peut fonctionner simultanément pour 8 entiers, car nous utilisons des instructions vectorielles qui fonctionnent sur des registres 128 bits.
Le problème suivant à résoudre est de savoir comment prendre un groupe de 4 entiers et le comprimer en supprimant des octets étrangers / inutilisés afin que tout ce qui vous reste est un flux d'octets de données avec des informations réelles. Prenons deux nombres de nos exemples ci-dessus.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
Ici, nous pouvons utiliser une opération de shuffle. Les opérations de méchant vectoriel réorganisent les octets dans un registre d'entrée en fonction du masque fourni dans un registre de destination. Chaque position dans le masque stocke un décalage dans le flux de vecteur source qui représente l'octet de données qui devrait entrer dans cette position.
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
Nous conservons une table de recherche prédéfinie qui contient un mappage de l'octet de contrôle au masque nécessaire et le chargez simplement après avoir construit l'octet de contrôle ci-dessus. De plus, nous conservons une table de recherche pour une cartographie des octets de contrôle à la longueur totale codée. Cela nous permet de savoir par combien incrément le pointeur de sortie et l'écrasement, par exemple, les 3 octets supérieurs redondants dans l'exemple de shuffle ci-dessus.
Le déballage pendant le décodage est le même que ce qui précède, mais à l'envers. Nous devons passer d'un format emballé à un format de mémoire déballé. Nous conservons des tables de recherche pour maintenir une cartographie de l'octet de contrôle au masque de shuffle inverse, puis effectuer une opération de remaniement pour sortir vers un tableau uint32 .
Stream Vbyte: compression entier orientée octet plus rapide
