streamvbyte simdgo
v0.4.0
Dies ist ein Repository, das einen Port von Stream VByte enthält. Insbesondere ist dieses Repo besonders darauf geachtet, SIMD -Techniken zu nutzen, um eine bessere Leistung zu erzielen. Derzeit gibt es Unterstützung für X86_64 -Architekturen mit AVX- und AVX2 -Hardware -Anweisungen. In Fällen, in denen dies nicht verfügbar ist, oder auf Nicht -X86_64 -Architekturen gibt es eine tragbare Skalarimplementierung. Wir führen auch eine Laufzeitprüfung durch, um sicherzustellen, dass die erforderliche ISA verfügbar ist und wenn nicht der skalare Ansatz falls ein Fallback ist.
Es gibt mehrere vorhandene Implementierungen:
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
Eine Notiz zu den Benchmarks: Es wird eine Reihe von zufälligen Uint32 erzeugt und dann immer wieder codiert/dekodiert. Es wird versucht, sicherzustellen, dass einige dieser Benchmarks die wahrscheinlichsten Leistungsmetriken der realen Welt widerspiegeln.
Stream VByte verwendet das gleiche zugrunde liegende Format wie Googles Gruppenvarint -Ansatz. Lemire et al. Ich wollte sehen, ob es eine Möglichkeit gab, die Leistung noch mehr zu verbessern, und führte eine clevere Wendung ein, um eine bessere Leistung über SIMD -Techniken zu ermöglichen. Das grundlegende Ziel des Gruppenvarint -Formats ist es, ähnliche Komprimierungseigenschaften wie das VByTE -Format für Ganzzahlen zu erreichen und sie auch sehr schnell zu laden und zu verarbeiten.
Die Erkenntnis, die die VByte-Codierung unterstützt, bemerkt, dass Sie nicht 32 Bit benötigen, um eine 32-Bit-Ganzzahl zu codieren. Nehmen wir zum Beispiel eine nicht signierte Ganzzahl, die weniger als 2^8 (256) beträgt. Diese Ganzzahl wird Bits im untersten Byte einer 32-Bit-Ganzzahl einstellen, während die verbleibenden 3 Bytes einfach Nullen sind.
111 in binary:
00000000 00000000 00000000 01101111
Ein Ansatz, den Sie zur Komprimierung dieser Ganzzahl verfolgen können, besteht darin, die Ganzzahl mit einer variablen Anzahl von Bytes zu codieren. Sie können beispielsweise die unteren 7 -Bits verwenden, um Daten, dh Bits aus der ursprünglichen Ganzzahl, zu speichern und dann das MSB als Fortsetzung zu verwenden. Wenn das MSB -Bit eingeschaltet ist, ist der IE 1, dann werden mehr Bytes benötigt, um diese bestimmte Ganzzahl zu dekodieren. Im Folgenden finden Sie ein Beispiel, in dem Sie möglicherweise 2 Bytes benötigen, um die Nummer 1234 zu speichern.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
Wenn Sie diese Ganzzahl dekodieren möchten, erstellen Sie einfach iterativ die Zahl. Dh du oder die letzten 7 Bit jedes Byte verlagerten dich auf die angemessene Länge auf deine 32-Bit-Ganzzahl, bis du ein Byte findet, das kein Fortsetzungsbit hat. Beachten Sie, dass dies für 64-Bit-Nummern gleich funktioniert.
Das Problem bei diesem Ansatz ist, dass es bei Codierung/Dekodierung viele Zweig-Fehlvorschriften einführen kann. Während der Dekodierungsphase wissen Sie die Anzahl der Bytes, mit denen die Ganzzahl, die Sie gerade verarbeiten, verwendet wurden, nicht im Voraus, und Sie müssen daher iterieren, bis Sie ein Byte ohne Fortsetzung finden. Wenn Sie Ganzzahlen haben, die ungleichmäßig sind, dh Ganzzahlen, die eine zufällige Anzahl von Bytes erfordern, um relativ zueinander zu codieren, kann dies eine Herausforderung für den Zweigprädiktor des Prozessors stellen. Diese Fehlvorschriften können zu erheblichen Verlangsamungen der Prozessorpipelines führen, ebenso wie das Gruppenvarint-Format geboren.
Das Gruppenvarint (Varint-GB) -Format geht davon aus, dass alles, was Sie erreichen möchten, mit 32-Bit-Ganzzahlen tun können. Es führt das Konzept eines Kontrollbyte ein, das einfach ein Byte ist, das die codierten Längen einer Gruppe von 4 32-Bit-Ganzzahlen speichert, daher Gruppenvarint. 32-Bit-Ganzzahlen erfordern nur bis zu 4 Bytes, um ordnungsgemäß zu codieren. Dies bedeutet, dass Sie ihre Längen mit 2 Bit unter Verwendung einer Null-Index-Länge darstellen können, dh 0, 1, 2 und 3, um Ganzzahlen darzustellen, die 1, 2, 3 und 4 Bytes benötigen, um zu codieren.
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
Sie können dann jede Gruppe von 4 codierten 32-Bit-Ganzzahlen mit ihrem Kontrollbyte präfixen und sie dann während des Dekodierens verwenden. Der offensichtliche Nachteil ist, dass Sie für alle 4 Zahlen, die Sie codieren möchten, einen Speicherkosten für ein Byte zahlen. Für 2^20 codierte ganze Zahlen ist das zusätzliche 256 KB zusätzlichen Raum: total marginal. Der große Vorteil ist jedoch, dass Sie jetzt fast alle Zweige aus Ihrer Dekodierungsphase entfernt haben. Sie wissen genau, wie viele Datenbytes Sie für eine bestimmte Zahl aus einem Puffer lesen müssen, und können dann verzweigte Dekodierung verwenden.
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
}Leider hat sich die Beschleunigung der Dekodierung des Varint-GB-Formats mit nur SIMD-Techniken als erfolglos erwiesen. Der folgende Auszug aus dem Papier beschreibt warum.
Um zu verstehen, warum es schwierig sein könnte, die Dekodierung von Daten zu beschleunigen, die im Varint-GB-Format im Vergleich zum Varint-G8IU-Format komprimiert sind, sollten wir nicht schneller dekodieren, als wir auf die Steuerbytes zugreifen können. In Varint-G8IU befinden sich die Steuerungsbytes immer intensiv neun komprimierte Bytes voneinander entfernt. Während ein Kontrollbyte verarbeitet wird oder noch zuvor, kann unser Superkalarprozessor die kommenden Kontrollbytes laden und damit beginnen, die Verarbeitung zu verarbeiten, da ihre Standorte vorhersehbar sind. Anweisungen abhängig von diesen Steuerbytes können vom Prozessor für die beste Leistung neu bestellt werden. Im Varint-GB-Format gibt es jedoch eine starke Datenabhängigkeit: Der Ort des nächsten Steuerungsbytes hängt vom aktuellen Steuerungsbyte ab. Dies erhöht das Risiko, dass der Prozessor nicht ausgelastet bleibt, und verzögert sich durch die Latenz zwischen der Ausstellung der Last für das nächste Kontroll -Byte und das Warten darauf, dass es bereit ist.
Darüber hinaus beweisen sie, dass die Dekodierung von 4 Ganzzahlen gleichzeitig mit 128-Bit-Registern schneller ist, als zu versuchen, eine variable Anzahl von Ganzzahlen zu dekodieren, die in ein 8-Byte-Register passen, dh dem Varint-G8IU-Ansatz.
Lemire et al. habe einen brillanten SIMD -Algorithmus entwickelt, um zwei Kontrollbytes für eine Gruppe von 8 Ganzzahlen gleichzeitig zu generieren. Der beste Weg, um diesen Algorithmus zu verstehen, besteht darin, zu verstehen, wie er in einer einzelnen Ganzzahl funktioniert, und dann davon auszugehen, dass er in einer vektorisierten Form funktioniert (es tut). In Zukunft werden wir Kontrollbits Stream verwenden, um diese Kontrollbytes darzustellen, die wir bauen.
00000000 00000000 00000100 11010010 // 1234
Nehmen wir eine der vorherigen Ganzzahlen, die wir uns angesehen haben, 1234 und gehen Sie ein Beispiel dafür, wie die 2-Bit-Steuerung mithilfe von SIMD-Techniken für sie erzeugt wird. Das Ziel ist es, für jede 32-Bit-Ganzzahl einen 2-Bit-Null-Index-Längenwert zu erzeugen. Wenn Sie beispielsweise eine Ganzzahl haben, für die 2 Bytes codiert werden müssen, möchten wir, dass der Algorithmus 0b01 erzeugt.
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
Der Algorithmus verwendet zunächst eine Maske, bei der jedes Byte gleich 1 ist. Wenn Sie eine pro-byte-min-Operation auf unserer Ganzzahl und in der Maske der 1 durchführen, hat das Ergebnis eine 1 an jedem Byte, das im ursprünglichen Ganzzahlen einen Wert hat.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
Jetzt führen Sie einen 16-Bit-Vorgang von 8-Bit-Sättigungspaketen durch. Praktisch bedeutet dies, dass Sie jeden 16-Bit-Wert einnehmen und versuchen, dies in 8 Bit zu schieben. Wenn die 16-Bit-Ganzzahl größer ist als die größte nicht signierte Ganzzahl 8-Bits, die die Packung auf den größten nicht signierten 8-Bit-Wert sättigt.
Warum dies durchgeführt wird, wird in den nachfolgenden Schritten deutlicher. Auf einer hohen Ebene, die Sie für jede Ganzzahl, die Sie codieren möchten, möchten Sie für die MSB von zwei aufeinanderfolgenden Bytes im Steuerbitsstrom als repräsentativ für die endgültige 2-Bit-Kontrolle sein. Wenn Sie beispielsweise eine 3-Byte-Ganzzahl haben, möchten Sie, dass der MSB von zwei aufeinanderfolgenden Bytes in dieser Reihenfolge 1 und 0 beträgt. Der Grund, warum Sie dies möchten, ist, dass es eine Vektorpackungsanweisung gibt, die die MSB von jedem Byte im Steuerbitsstrom entnimmt und ihn in das niedrigste Byte packt. Dies würde somit den Wert 0b10 im endgültigen Byte für diese 3-Byte-Ganzzahl darstellen, was wir wollen.
Durch die Durchführung eines 16-Bit-bis 8-Bit-Sättigungspacks wird der Effekt geführt, dass Sie das Sättigungsverhalten verwenden können, um die MSB dieser Bytes bedingt einzuschalten, je nachdem, welche Bytes Werte im ursprünglichen 32-Bit-Ganzzahl haben.
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
Wir nehmen dann die Maske der 1, die wir zuvor verwendet haben, und führen eine signierte 16-Bit- Minimaloperation durch. Der Grund dafür ist klarer, wenn Sie sich ein Beispiel mit einer 3-Byte-Ganzzahl ansehen.
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
Der signierte 16-Bit-MIN-Betrieb hat drei wichtige Auswirkungen.
Erstens hat es für 3-Byte-Ganzzahlen den Einfluss, die MSB des niedrigsten Byte auszuschalten. Dies ist notwendig, da eine 3-Byte-Ganzzahl eine 2-Bit-Steuerung mit 0b10 haben sollte und ohne diesen Schritt die MSB-Pack-Operation zu einem 2-Bit-Steuerelement führen würde, das etwas wie 0b_1 aussieht, bei dem das niedrigste Bit eingeschaltet ist. Offensichtlich ist dies falsch, da nur Ganzzahlen, die 2 oder 4 Bytes benötigen, um zu codieren, dieses niedrigere Bit haben, dh 1 oder 3 als Null-Indexed-Länge.
Zweitens hat der unterzeichnete Aspekt für 4-Byte-Zahlen den Einfluss, beide MSBs der 2 Bytes auf zu lassen. Bei der späteren Verwendung des MSB-Packungsvorgangs führt dies zu einem 2-Bit-Steuerwert von 0b11 , was wir wollen.
Drittens hat es für 1 und 2 Byte -Ganzzahlen keine Wirkung. Dies ist ideal für 2-Byte-Werte, da die MSB eingeschaltet bleibt und 1 Byte-Werte sowieso keine MSB aufweisen, daher ist es in beiden Szenarien effektiv eine 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
Als nächstes nehmen wir eine Maske mit dem Wert 0x7F00 und führen einen nicht signierten Sättigungs -Add zum Steuerungsstrom aus. Im Fall für die Ganzzahl 1234 hat dies keinen wirklichen Effekt. Wir behalten die MSB im untersten Byte bei. Sie werden jedoch feststellen, dass das einzige Byte, das seinen MSB anmacht, der letzte ist. Die Durchführung eines MSB -Packbetriebs würde also zu einem Wert von 0b0001 führen, was wir wollen. Ein Beispiel für diesen Schritt auf der Ganzzahl 789123 könnte ein klareres Bild malen.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
Sie werden hier feststellen, dass die Zugabe von 0x01 mit 0x7F im oberen Byte zum MSB des resultierenden oberen Byte führt. Das MSB im unteren Byte bleibt ausgeschaltet und jetzt wird ein MSB -Packbetrieb auf 0b0010 auflösen, was wir wollen. Das nicht signierte Sättigungsverhalten ist für 4-Byte-Zahlen, die nur Bits im bedeutendsten Byte haben, wirklich wichtig. Ein Beispiel unten:
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
Beachten Sie hier, dass, weil nur das obere Byte einen Wert hatte, das niedrigste Byte im Kontrollbitsstrom für die Dauer des Algorithmus Null bleibt. Dies ist ein Problem, da wir für einen 4-Byte-Wert wollen, dass die 2-Bit-Steuerung zu einem Wert von 0b11 führt. Durch die Durchführung einer 16-Bit- Sättigungszusatzung wird alle Bits im unteren Byte eingeschaltet, und somit erhalten wir ein Ergebnis mit dem MSB im unteren Byte.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
Die endgültige Move -Byte -Maske erfolgt auf dem Stream der Kontrollbits, und wir haben jetzt das Ergebnis, das wir uns gewünscht haben. Jetzt, da Sie sehen, dass dies für 1 Ganzzahl funktioniert, wissen Sie, wie es gleichzeitig 8 Ganzzahlen funktionieren kann, da wir Vektoranweisungen verwenden, die mit 128 -Bit -Registern funktionieren.
Das nächste Problem ist, wie man eine Gruppe von 4 Ganzzahlen einnimmt und sie komprimiert, indem sie fremde/nicht verwendete Bytes entfernen, damit nur noch ein Strom von Datenbytes mit echten Informationen ist. Nehmen wir zwei Zahlen aus unseren oben genannten Beispielen.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
Hier können wir einen Shuffle -Betrieb verwenden. Vektor Shuffle Operations ordnen die Bytes in einem Eingangsregister gemäß einigen bereitgestellten Maske in ein Zielregister neu. Jede Position in der Maske speichert einen Offset in den Quellvektorstrom, der das Datenbyte darstellt, das in diese Position eingehen sollte.
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
Wir führen eine vorgebaute Suchtabelle, die eine Zuordnung vom Steuerbyte auf die erforderliche Maske enthält, und laden einfach, dass nach dem Erstellen des oben genannten Steuerungs Byte einfach geladen wird. Darüber hinaus führen wir eine Nachschlagtabelle für eine Zuordnung von Steuerbytes bis hin zur gesamten codierten Länge. Auf diese Weise können wir wissen, wie viel wir den Ausgangszeiger und das Überschreiben in Erkrankungen haben, beispielsweise die redundanten oberen 3 Bytes im obigen Beispiel.
Das Auspacken beim Dekodieren ist das gleiche wie oben, aber umgekehrt. Wir müssen von einem verpackten Format zu einem ausgepackten Speicherformat wechseln. Wir führen Suchtabellen bei, um eine Zuordnung von Steuerungsbyte bis zur Reverse Shuffle Maske zu verwalten und dann einen Shuffle -Operation durchzuführen, um an ein uint32 -Array auszugeben.
Stream VByte: schneller byte-orientierte Ganzzahlkomprimierung
