streamvbyte simdgo
v0.4.0
Это репозиторий, который содержит порт потока Vbyte. Примечательно, что это репо требует особого внимания, чтобы использовать методы SIMD для достижения лучшей производительности. В настоящее время существует поддержка архитектур X86_64, которые имеют инструкции AVX и AVX2. В тех случаях, когда это недоступно, или на архитектурах Non x86_64, существует портативная скалярная реализация. Мы также выполняем проверку времени выполнения, чтобы убедиться, что необходимый ISA доступен, а если не отступает на скалярном подходе.
Есть несколько существующих реализаций:
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
MemCopy8Uint32-12 463986302 2.608 ns/op 12269.03 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/decode
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
Get8uint32Fast-12 377839186 3.170 ns/op 10095.99 MB/s
Get8uint32DeltaFast-12 298522095 4.455 ns/op 7183.20 MB/s
Get8uint32Scalar-12 63384603 19.28 ns/op 1659.36 MB/s
Get8uint32DeltaScalar-12 58705828 20.04 ns/op 1596.46 MB/s
Get8uint32Varint-12 27369775 43.77 ns/op 731.10 MB/s
Get8uint32DeltaVarint-12 20924770 57.30 ns/op 558.46 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/encode
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
Put8uint32Fast-12 297620898 3.864 ns/op 8281.18 MB/s
Put8uint32DeltaFast-12 276545827 4.350 ns/op 7356.59 MB/s
Put8uint32Scalar-12 41200776 28.59 ns/op 1119.30 MB/s
Put8uint32DeltaScalar-12 37773458 30.65 ns/op 1044.11 MB/s
Put8uint32Varint-12 58668867 17.20 ns/op 1860.67 MB/s
Put8uint32DeltaVarint-12 61446153 22.88 ns/op 1398.80 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/stream/reader
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
ReadAllFast/Count_1e0-12 99354789 12.24 ns/op 326.80 MB/s
ReadAllFast/Count_1e1-12 28076071 42.81 ns/op 934.43 MB/s
ReadAllFast/Count_1e2-12 11041639 107.2 ns/op 3730.16 MB/s
ReadAllFast/Count_1e3-12 1645387 729.9 ns/op 5480.00 MB/s
ReadAllFast/Count_1e4-12 170894 7034 ns/op 5686.52 MB/s
ReadAllFast/Count_1e5-12 16848 70969 ns/op 5636.29 MB/s
ReadAllFast/Count_1e6-12 1513 728516 ns/op 5490.62 MB/s
ReadAllFast/Count_1e7-12 152 7835111 ns/op 5105.22 MB/s
ReadAllDeltaFast/Count_1e0-12 92727970 13.10 ns/op 305.44 MB/s
ReadAllDeltaFast/Count_1e1-12 26164140 45.89 ns/op 871.61 MB/s
ReadAllDeltaFast/Count_1e2-12 9458992 128.5 ns/op 3113.55 MB/s
ReadAllDeltaFast/Count_1e3-12 1277408 934.4 ns/op 4280.69 MB/s
ReadAllDeltaFast/Count_1e4-12 144405 8318 ns/op 4808.88 MB/s
ReadAllDeltaFast/Count_1e5-12 14444 83151 ns/op 4810.55 MB/s
ReadAllDeltaFast/Count_1e6-12 1426 846305 ns/op 4726.43 MB/s
ReadAllDeltaFast/Count_1e7-12 127 9337355 ns/op 4283.87 MB/s
ReadAllScalar/Count_1e0-12 122650209 9.770 ns/op 409.43 MB/s
ReadAllScalar/Count_1e1-12 38012136 31.63 ns/op 1264.64 MB/s
ReadAllScalar/Count_1e2-12 4999376 241.6 ns/op 1655.30 MB/s
ReadAllScalar/Count_1e3-12 500337 2459 ns/op 1626.38 MB/s
ReadAllScalar/Count_1e4-12 50247 24034 ns/op 1664.34 MB/s
ReadAllScalar/Count_1e5-12 5032 238354 ns/op 1678.17 MB/s
ReadAllScalar/Count_1e6-12 499 2405669 ns/op 1662.74 MB/s
ReadAllScalar/Count_1e7-12 46 24533207 ns/op 1630.44 MB/s
ReadAllDeltaScalar/Count_1e0-12 100000000 10.32 ns/op 387.49 MB/s
ReadAllDeltaScalar/Count_1e1-12 36915704 32.52 ns/op 1230.08 MB/s
ReadAllDeltaScalar/Count_1e2-12 4818140 249.8 ns/op 1601.58 MB/s
ReadAllDeltaScalar/Count_1e3-12 512492 2374 ns/op 1685.20 MB/s
ReadAllDeltaScalar/Count_1e4-12 51004 23639 ns/op 1692.11 MB/s
ReadAllDeltaScalar/Count_1e5-12 3568 333168 ns/op 1200.60 MB/s
ReadAllDeltaScalar/Count_1e6-12 520 2304864 ns/op 1735.46 MB/s
ReadAllDeltaScalar/Count_1e7-12 48 24810555 ns/op 1612.22 MB/s
ReadAllVarint/Count_1e0-12 121348074 9.967 ns/op 401.34 MB/s
ReadAllVarint/Count_1e1-12 21056739 57.34 ns/op 697.64 MB/s
ReadAllVarint/Count_1e2-12 2025081 589.0 ns/op 679.15 MB/s
ReadAllVarint/Count_1e3-12 205881 5851 ns/op 683.69 MB/s
ReadAllVarint/Count_1e4-12 20906 57446 ns/op 696.31 MB/s
ReadAllVarint/Count_1e5-12 2037 580620 ns/op 688.92 MB/s
ReadAllVarint/Count_1e6-12 208 5755083 ns/op 695.04 MB/s
ReadAllVarint/Count_1e7-12 20 57872736 ns/op 691.17 MB/s
ReadAllDeltaVarint/Count_1e0-12 139763250 8.318 ns/op 480.87 MB/s
ReadAllDeltaVarint/Count_1e1-12 19199100 62.49 ns/op 640.11 MB/s
ReadAllDeltaVarint/Count_1e2-12 2149660 556.6 ns/op 718.65 MB/s
ReadAllDeltaVarint/Count_1e3-12 207122 5810 ns/op 688.41 MB/s
ReadAllDeltaVarint/Count_1e4-12 22680 53200 ns/op 751.88 MB/s
ReadAllDeltaVarint/Count_1e5-12 2145 500177 ns/op 799.72 MB/s
ReadAllDeltaVarint/Count_1e6-12 228 5262741 ns/op 760.06 MB/s
ReadAllDeltaVarint/Count_1e7-12 27 42000722 ns/op 952.36 MB/s
goos: darwin
goarch: amd64
pkg: github.com/theMPatel/streamvbyte-simdgo/pkg/stream/writer
cpu: Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
--
WriteAllFast/Count_1e0-12 54152408 22.05 ns/op 181.36 MB/s
WriteAllFast/Count_1e1-12 27681948 43.17 ns/op 926.49 MB/s
WriteAllFast/Count_1e2-12 7136480 167.0 ns/op 2395.79 MB/s
WriteAllFast/Count_1e3-12 928952 1273 ns/op 3141.14 MB/s
WriteAllFast/Count_1e4-12 96117 12012 ns/op 3329.93 MB/s
WriteAllFast/Count_1e5-12 9718 114260 ns/op 3500.80 MB/s
WriteAllFast/Count_1e6-12 879 1242927 ns/op 3218.21 MB/s
WriteAllFast/Count_1e7-12 100 10368754 ns/op 3857.74 MB/s
WriteAllDeltaFast/Count_1e0-12 50489378 23.38 ns/op 171.06 MB/s
WriteAllDeltaFast/Count_1e1-12 26866423 45.03 ns/op 888.33 MB/s
WriteAllDeltaFast/Count_1e2-12 6695125 175.8 ns/op 2275.37 MB/s
WriteAllDeltaFast/Count_1e3-12 899895 1391 ns/op 2875.71 MB/s
WriteAllDeltaFast/Count_1e4-12 90394 12958 ns/op 3086.82 MB/s
WriteAllDeltaFast/Count_1e5-12 10000 122319 ns/op 3270.13 MB/s
WriteAllDeltaFast/Count_1e6-12 945 1249546 ns/op 3201.16 MB/s
WriteAllDeltaFast/Count_1e7-12 100 11461852 ns/op 3489.84 MB/s
WriteAllScalar/Count_1e0-12 56106489 21.72 ns/op 184.18 MB/s
WriteAllScalar/Count_1e1-12 18309972 65.09 ns/op 614.51 MB/s
WriteAllScalar/Count_1e2-12 2776918 433.5 ns/op 922.63 MB/s
WriteAllScalar/Count_1e3-12 289309 4209 ns/op 950.38 MB/s
WriteAllScalar/Count_1e4-12 29497 40884 ns/op 978.38 MB/s
WriteAllScalar/Count_1e5-12 3027 399959 ns/op 1000.10 MB/s
WriteAllScalar/Count_1e6-12 296 4010161 ns/op 997.47 MB/s
WriteAllScalar/Count_1e7-12 28 38753790 ns/op 1032.16 MB/s
WriteAllDeltaScalar/Count_1e0-12 54981757 21.90 ns/op 182.65 MB/s
WriteAllDeltaScalar/Count_1e1-12 17823349 67.10 ns/op 596.14 MB/s
WriteAllDeltaScalar/Count_1e2-12 2711672 442.4 ns/op 904.09 MB/s
WriteAllDeltaScalar/Count_1e3-12 292664 4130 ns/op 968.62 MB/s
WriteAllDeltaScalar/Count_1e4-12 29340 41014 ns/op 975.28 MB/s
WriteAllDeltaScalar/Count_1e5-12 2289 516113 ns/op 775.02 MB/s
WriteAllDeltaScalar/Count_1e6-12 302 3930860 ns/op 1017.59 MB/s
WriteAllDeltaScalar/Count_1e7-12 30 41357670 ns/op 967.17 MB/s
WriteAllVarint/Count_1e0-12 208214545 5.720 ns/op 699.32 MB/s
WriteAllVarint/Count_1e1-12 43083270 28.02 ns/op 1427.34 MB/s
WriteAllVarint/Count_1e2-12 4972045 242.8 ns/op 1647.67 MB/s
WriteAllVarint/Count_1e3-12 499011 2409 ns/op 1660.60 MB/s
WriteAllVarint/Count_1e4-12 51022 23590 ns/op 1695.67 MB/s
WriteAllVarint/Count_1e5-12 5216 231741 ns/op 1726.07 MB/s
WriteAllVarint/Count_1e6-12 518 2305364 ns/op 1735.08 MB/s
WriteAllVarint/Count_1e7-12 50 24905825 ns/op 1606.05 MB/s
WriteAllDeltaVarint/Count_1e0-12 175269966 6.792 ns/op 588.93 MB/s
WriteAllDeltaVarint/Count_1e1-12 51799438 23.38 ns/op 1710.63 MB/s
WriteAllDeltaVarint/Count_1e2-12 5417458 221.3 ns/op 1807.60 MB/s
WriteAllDeltaVarint/Count_1e3-12 539414 2243 ns/op 1783.48 MB/s
WriteAllDeltaVarint/Count_1e4-12 52717 22753 ns/op 1757.99 MB/s
WriteAllDeltaVarint/Count_1e5-12 5716 210456 ns/op 1900.63 MB/s
WriteAllDeltaVarint/Count_1e6-12 495 2453672 ns/op 1630.21 MB/s
WriteAllDeltaVarint/Count_1e7-12 70 17491186 ns/op 2286.87 MB/s
Примечание на тестах: генерируется множество случайных UINT32, а затем кодируется/декодирован снова и снова. Предпринимается попытка гарантировать, что некоторые из этих критериев отражают наиболее вероятные показатели производительности в реальном мире.
Stream Vbyte использует тот же базовый формат, что и подход группы Google Varint. Lemire et al. Хотел посмотреть, есть ли способ еще больше улучшить производительность, и ввел умный поворот, чтобы обеспечить лучшую производительность с помощью методов SIMD. Основная цель формата группы Varint состоит в том, чтобы иметь возможность достичь аналогичных характеристик сжатия, как формат Vbyte для целых чисел, а также иметь возможность загружать и обрабатывать их очень быстро.
Понимание, подтверждающее кодирование Vbyte, замечает, что вам часто не нужно 32 бита, чтобы кодировать 32-разрядное целое число. Возьмем, к примеру, без знакового целого числа, которое составляет менее 2^8 (256). Это целое число будет иметь биты, установленные в самом низком байте 32-разрядного целого числа, в то время как оставшиеся 3 байта будут просто нули.
111 in binary:
00000000 00000000 00000000 01101111
Подход, который вы можете использовать для сжатия этого целого числа, - это кодировать целое число, используя переменное число байтов. Например, вы можете использовать более низкие 7 бит для хранения данных, т.е. биты из исходного целого числа, а затем использовать MSB в качестве бита продолжения. Если бит MSB включен, то есть 1, то для декодирования этого конкретного целого числа необходимо больше байтов. Ниже приведен пример, где вам может понадобиться 2 байта для хранения номера 1234.
1234 in binary:
00000000 00000000 00000100 11010010
Num compressed:
v v Continuation bits
0|0001001| 1|1010010|
^ ^ Data bits
Если вы хотите расшифровать это целое число, вы просто итеративно нажимаете номер. Т.е. вы или последние 7 бит каждого байта перешли на соответствующую длину на ваше 32-разрядное целое число, пока не найдете байт, который не будет установлен на продолжение. Обратите внимание, что это работает так же для 64-битных чисел.
Проблема с таким подходом заключается в том, что он может ввести много ошибок в филиале во время кодирования/декодирования. На этапе декодирования вы не знаете заранее количество байтов, которые использовались для кодирования целого числа, которое вы в настоящее время обрабатываете, и поэтому вам нужно итерацию, пока не найдете байт без продолжения. Если у вас есть целые числа, которые неравномерные, то есть целые числа, которые требуют случайных чисел байтов для кодирования относительно друг друга, это может представлять собой проблему для предиктора ветви процессора. Эти ошибки могут вызвать значительные замедления в процессоре трубопроводов и, таким образом, родились в формате Varint Group.
Формат группы Varint (Varint-GB) предполагает, что все, что вы надеетесь достичь, вы можете сделать с 32-битными целыми числами. Он вводит концепцию управляющего байта, который является просто байтом, который хранит закодированные длины группы из 4 32-битных целых чисел, следовательно, группа Varint. 32-разрядные целые числа требуют только 4 байта для правильного кодирования. Это означает, что вы можете представлять их длины с 2 битами, используя индексированную длина с нулевой индексом, то есть 0, 1, 2 и 3, чтобы представлять целые числа, которые требуют 1, 2, 3 и 4 байтов для кодирования соответственно.
00000000 00000000 00000000 01101111 = 111
00000000 00000000 00000100 11010010 = 1234
00000000 00001100 00001010 10000011 = 789123
01000000 00000000 00000000 00000000 = 1073741824
Num Len 2-bit control
----------------------------------
111 1 0b00
1234 2 0b01
789123 3 0b10
1073741824 4 0b11
Final Control byte
0b11100100
Encoded data (little endian right-to-left bottom-to-top)
0b01000000 0b00000000 0b00000000 0b00000000 0b00001100
0b00001010 0b10000011 0b00000100 0b11010010 0b01101111
Затем вы можете префикс каждой группы из 4 кодированных 32-разрядных целых чисел с их контрольным байтом, а затем использовать его во время декодирования. Очевидным недостатком является то, что вы оплачиваете стоимость хранения одного байта за каждые 4 целых числа, которые вы хотите кодировать. Для 2^20 кодируемых целых чисел это дополнительное 256 КБ дополнительного пространства: совершенно маргинальный. Однако отличный потенциал в том, что вы теперь удалили почти все ветви с фазы декодирования. Вы точно знаете, сколько байтов данных вам нужно прочитать из буфера для определенного числа, а затем использовать декодирование без ветви.
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
}К сожалению, ускорение декодирования формата Varint-GB с помощью только методов SIMD оказалось неудачным. В приведенном ниже отрывке из бумаги описывается почему.
Чтобы понять, почему может быть трудно ускорить декодирование данных, сжатых в формате Varint-GB по сравнению с форматом Varint-G8IU, считайте, что мы не можем декодировать быстрее, чем мы можем получить доступ к контрольным байтам. В Varint-G8IU управляющие байты удобно всегда расположены на девять сжатых байтов друг от друга. Таким образом, в то время как управляющий байт обрабатывается или даже раньше, наш суперскалярный процессор может загружать и начать обработку предстоящих управляющих байтов, поскольку их местоположения предсказуемы. Инструкции в зависимости от этих контрольных байтов могут быть переупорядочены процессором для достижения наилучшей производительности. Однако в формате Varint-GB существует сильная зависимость данных: местоположение следующего управляющего байта зависит от текущего контрольного байта. Это увеличивает риск того, что процессор остается недостаточно используемым, задерживается задержкой между выпуском нагрузки для следующего контрольного байта и ожиданием его готовности.
Кроме того, они доказывают, что декодирование 4 целых числа за раз с использованием 128-битных регистров происходит быстрее, чем попытка декодировать переменное количество целых чисел, которые вписываются в 8-байтовый реестр, то есть подход Varint-G8IU.
Lemire et al. разработали блестящий алгоритм SIMD для одновременного создания двух контрольных байтов для группы из 8 целых чисел. Лучший способ понять этот алгоритм - понять, как он работает на одном целом, а затем предположить, что он работает в векторизованной форме (это делает). В дальнейшем мы будем использовать потоки управления для представления этих контрольных байтов, которые мы строим.
00000000 00000000 00000100 11010010 // 1234
Давайте возьмем одну из предыдущих целых чисел, на которые мы смотрели, 1234 , и проведем пример того, как для него генерируется 2-битный элемент управления с использованием методов SIMD. Цель состоит в том, чтобы иметь возможность для любого 32-разрядного целого числа генерировать 2-битное нулевое значение индексированной длины. Например, если у вас есть целое число, которое требует 2 байта для кодирования, мы хотим, чтобы алгоритм генерировал 0b01 .
00000000 00000000 00000100 11010010 // 1234
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1234, 0x0101)
00000000 00000000 00000001 00000001
Алгоритм сначала использует маску, в которой каждый байт равен 1. Если вы выполняете операцию на мин на нашем целом и маске 1, результат будет иметь 1 на каждом байте, который имел значение в исходном целом.
00000000 00000000 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000000 11111111
Теперь вы выполняете 16-битную до 8-битную беззначную насыщенную работу. Практически это означает, что вы принимаете каждую 16-битную ценность и пытаетесь засунуть это на 8 битов. Если 16-разрядное целое число больше, чем самое большое, не знаковое целое число 8 бит может поддержать, пакет насыщается до самого большого 8-битного значения без знака.
Почему это выполняется, станет более ясным на последующих этапах, однако, на высоком уровне, для каждого целого числа, которое вы хотите кодировать, вы хотите, чтобы MSB двух последовательных байтов в потоке управляющих битов был репрезентативным для окончательного 2-битного управления. Например, если у вас есть 3-байтовое целое число, вы хотите, чтобы MSB двух последовательных байтов составлял 1 и 0, в таком порядке. Причина, по которой вы хотели бы, заключается в том, что есть инструкция по векторным пакетам, которая берет MSB с каждого байта в потоке управления битами и упаковывает ее в самый низкий байт. Таким образом, это будет представлять значение 0b10 в последнем байте для этого 3-байтового целого числа, что мы и хотим.
Выполнение 16-битного до 8-битного насыщающего насыщающего пакета оказывает тот эффект, который вы можете использовать для условного включения MSB этих байтов в зависимости от того, какие байты имеют значения в исходном 32-разрядном целом.
00000000 00000000 00000000 11111111 // control bits stream
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000000 11111111
Затем мы принимаем маску 1, которую мы использовали раньше, и выполняем подписанную 16-битную операцию. Причина этого становится более ясной, если вы посмотрите на пример с использованием 3-байтового целого числа.
00000000 00001100 00001010 10000011 // 789123
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(789123, 0x0101)
00000000 00000001 00000001 00000001
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 00000001 11111111
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 00000001 00000001
Подписанная 16-битная операция мин имеет три важных эффекта.
Во-первых, для 3-байтовых целых чисел он имеет эффект отключения MSB самого низкого байта. Это необходимо, потому что 3-байтовое целое число должно иметь 2-битный элемент управления, который составляет 0b10 , и без этого шага с использованием операции пакета MSB приведет к 2-битному управлению, который выглядит примерно 0b_1 , где на самом низком бите. Очевидно, что это неправильно, поскольку только целые числа, которым требуется 2 или 4 байта для кодирования, должны иметь этот нижний бит, т.е. 1 или 3 в виде длина индексации с нулевой индексом.
Во-вторых, для 4-байтовых целых чисел подписанный аспект влияет на то, чтобы оставить оба MSB 2 байта. При использовании работы пакета MSB это приведет к 2-битному управляющему значению 0b11 , что мы хотим.
В -третьих, для целых чисел 1 и 2 байтов это не имеет никакого эффекта. Это отлично подходит для 2-байтовых значений, так как MSB останется включенным, а значения 1 байта в любом случае не будут иметь никакого MSB, поэтому в обоих сценариях это фактически невы
00000000 00000000 00000000 11111111 // control bits stream (original 1234)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 01111111 11111111
Затем мы берем маску со значением 0x7F00 и выполняем беззнательное насыщение, добавьте к потоку управления. В случае для целого числа 1234 это не имеет реального эффекта. Мы поддерживаем MSB в самом низком байте. Вы заметите, однако, что единственный байт, на котором есть свой MSB, является последним, поэтому выполнение операции MSB Pack приведет к значению 0b0001 , что мы хотим. Пример этого шага на Integer 789123 может нарисовать более четкую картину.
00000000 00000000 00000001 00000001 // control bits stream (789123)
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 00000001
Здесь вы заметите, что добавление 0x01 с 0x7F в верхнем байте приводит к MSB результирующего верхнего байта. MSB в нижнем байте остается отключенным, и теперь операция пакета MSB будет разрешена до 0b0010 , что мы хотим. Неподписанное поведение насыщения действительно важно для 4-байтовых чисел, которые имеют только биты в самом значительном байте. Пример ниже:
01000000 00000000 00000000 00000000 // 1073741824
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // byte-min(1073741824, 0x0101)
00000001 00000000 00000000 00000000
----------------------------------- // pack unsigned saturating 16-bit to 8-bit
00000000 00000000 11111111 00000000
00000001 00000001 00000001 00000001 // 0x0101 mask
----------------------------------- // signed 16-bit min
00000000 00000000 11111111 00000000
01111111 00000000 01111111 00000000 // 0x7F00 mask
----------------------------------- // add unsigned saturating 16-bit
01111111 00000000 11111111 11111111
Обратите внимание, что, поскольку только верхний байт имел значение в нем, самый низкий байт в потоке управляющих битов остается нулевым в течение всего алгоритма. Это создает проблему, поскольку для 4-байтового значения мы хотим, чтобы 2-битный элемент управления приводил к значению 0b11 . Выполнение 16-битного насыщающего насыщающего добавления имеет эффект включения всех битов в нижнем байте, и, таким образом, мы получаем результат с MSB в нижнем байте.
01111111 00000000 11111111 00000001 // control bits stream (789123)
----------------------------------- // move byte mask
00000000 00000000 00000000 00000010 // 2-bit control
Последняя маска для перемещения выполняется в потоке управления битами, и теперь у нас есть такой результат, который мы хотели. Теперь, когда вы видите, что это работает для 1 целого числа, вы знаете, как это может работать для 8 целых чисел одновременно, поскольку мы используем векторные инструкции, которые работают в 128 -битных регистрах.
Следующая проблема, которая должна быть решена, - это то, как взять группу из 4 целых чисел и сжать ее, удалив посторонние/неиспользованные байты, так что все, что вы остаетесь, - это поток байтов данных с реальной информацией. Давайте возьмем два числа из наших примеров выше.
789123 1234
00000000 00001100 00001010 10000011 | 00000000 00000000 00000100 11010010
-------------------------------------------------------------------------
00001100 00001010 10000011 00000100 11010010 // packed
Здесь мы можем использовать операцию. Операции Vector Shuffle перестараются байты в входном реестре в соответствии с некоторыми предоставленными масками в регистр назначения. Каждая позиция в маске сохраняет смещение в векторный поток исходного исходного исходного исходного исходного вектора, который представляет байт данных, который должен перейти в эту позицию.
input [1234, 789123] (little endian R-to-L)
00000000 00001100 00001010 10000011 00000000 00000000 00000100 11010010
| | | | |
| | |____________________ | |
| |_____________________ | | |
|____________________ | | | |
v v v v v
0xff 0xff 0xff 0x06 0x05 0x04 0x01 0x00 // mask in hex
-----------------------------------------------------------------------
00000000 00000000 00000000 00001100 00001010 10000011 00000100 11010010 // packed
Мы сохраняем предварительную таблицу поиска, которая содержит отображение от управляющего байта в необходимую маску и просто загружаем, что после того, как мы построем контрольный байт выше. Кроме того, мы сохраняем таблицу поиска для картирования от контрольных байтов до общей кодируемой длины. Это позволяет нам узнать, сколько можно увеличить выходной указатель и перезаписать, например, избыточные верхние 3 байта в примере перерыва выше.
Распаковка во время декодирования совпадает с вышеизложенным, но наоборот. Нам нужно перейти от упакованного формата в распакованный формат памяти. Мы продолжаем поиск таблиц, чтобы поддерживать отображение от байта управления до маски обратного перетасовки, а затем выполняем операцию перетасовки для вывода на массив uint32 .
Stream Vbyte: более быстрое байтологическое целочисленное сжатие
