streamvbyte simdgo
v0.4.0
นี่คือที่เก็บที่มีพอร์ตของสตรีม VBYTE ที่จะไป โดยเฉพาะอย่างยิ่ง repo นี้ใช้ความระมัดระวังเป็นพิเศษในการใช้เทคนิค SIMD เพื่อให้ได้ประสิทธิภาพที่ดีขึ้น ปัจจุบันมีการสนับสนุนสำหรับสถาปัตยกรรม x86_64 ที่มีคำแนะนำฮาร์ดแวร์ AVX และ AVX2 ในกรณีที่ไม่สามารถใช้งานได้หรือในสถาปัตยกรรมที่ไม่ใช่ 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 ถูกสร้างขึ้นแล้วเข้ารหัส/ถอดรหัสซ้ำแล้วซ้ำอีก มีความพยายามเพื่อให้แน่ใจว่าบางส่วนของมาตรฐานเหล่านี้สะท้อนให้เห็นถึงการวัดประสิทธิภาพในโลกแห่งความเป็นจริงที่น่าจะเป็นไปได้มากที่สุด
สตรีม VBYTE ใช้รูปแบบพื้นฐานเดียวกันกับวิธีการ Varint กลุ่มของ Google Lemire และคณะ ต้องการดูว่ามีวิธีการปรับปรุงประสิทธิภาพมากยิ่งขึ้นและแนะนำการบิดอย่างชาญฉลาดเพื่อให้ประสิทธิภาพที่ดีขึ้นผ่านเทคนิค 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 กลุ่ม
รูปแบบกลุ่ม Varint (Varint-GB) ถือว่าทุกสิ่งที่คุณหวังว่าจะบรรลุคุณสามารถทำได้ด้วยจำนวนเต็ม 32 บิต มันแนะนำแนวคิดของไบต์ควบคุมซึ่งเป็นเพียงไบต์ที่เก็บความยาวที่เข้ารหัสของกลุ่มจำนวนเต็ม 32 บิต 4 บิตจึงเป็นตัวแปรกลุ่ม จำนวนเต็ม 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
จากนั้นคุณสามารถนำหน้าจำนวนเต็ม 32 บิตที่เข้ารหัส 4 กลุ่มด้วยไบต์ควบคุมของพวกเขาแล้วใช้ในระหว่างการถอดรหัส ข้อเสียที่เห็นได้ชัดคือคุณจ่ายค่าพื้นที่เก็บข้อมูลหนึ่งไบต์สำหรับจำนวนเต็มทุก ๆ 4 ตัวที่คุณต้องการเข้ารหัส สำหรับจำนวนเต็มที่เข้ารหัส 2^20 นั่นคือพื้นที่พิเศษ 256 kb พิเศษ: ขอบโดยสิ้นเชิง อย่างไรก็ตามสิ่งที่ยอดเยี่ยมคือตอนนี้คุณได้ลบสาขาเกือบทั้งหมดออกจากขั้นตอนการถอดรหัสของคุณ คุณรู้ว่าคุณต้องอ่านจำนวนไบต์จำนวนเท่าใดในการอ่านจากบัฟเฟอร์สำหรับหมายเลขใดหมายเลขหนึ่งจากนั้นสามารถใช้การถอดรหัสแบบไม่มีสาขาได้
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 ไบต์ควบคุมจะอยู่ห่างกันเก้าไบต์ที่ถูกบีบอัดเก้าไบต์ ดังนั้นในขณะที่ไบต์การควบคุมกำลังถูกประมวลผลหรือแม้กระทั่งก่อนหน้านี้โปรเซสเซอร์ superscalar ของเราสามารถโหลดและเริ่มประมวลผลไบต์ควบคุมที่กำลังจะมาถึงเนื่องจากตำแหน่งของพวกเขาสามารถคาดการณ์ได้ คำแนะนำขึ้นอยู่กับไบต์การควบคุมเหล่านี้สามารถจัดลำดับใหม่ได้โดยโปรเซสเซอร์เพื่อประสิทธิภาพที่ดีที่สุด อย่างไรก็ตามในรูปแบบ Varint-GB มีการพึ่งพาข้อมูลที่แข็งแกร่ง: ตำแหน่งของไบต์ควบคุมถัดไปขึ้นอยู่กับไบต์ควบคุมปัจจุบัน สิ่งนี้จะเพิ่มความเสี่ยงที่โปรเซสเซอร์ยังคงอยู่ในระดับต่ำสุดล่าช้าโดยเวลาแฝงระหว่างการออกโหลดสำหรับไบต์ควบคุมครั้งต่อไปและรอให้มันพร้อม
นอกจากนี้พวกเขาพิสูจน์ว่าการถอดรหัสจำนวนเต็ม 4 ครั้งในแต่ละครั้งโดยใช้การลงทะเบียน 128 บิตนั้นเร็วกว่าการพยายามถอดรหัสจำนวนจำนวนเต็มของตัวแปรที่พอดีกับการลงทะเบียน 8 ไบต์เช่นวิธี Varint-G8IU
Lemire และคณะ ได้คิดค้นอัลกอริทึม 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 ผลลัพธ์จะมี 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 ไบต์แง่มุมที่ลงนามมีผลต่อการออกจาก MSBS ทั้งสองของ 2 ไบต์บน เมื่อใช้การดำเนินการ MSB Pack ในภายหลังจะส่งผลให้ค่าควบคุม 2 บิตเป็น 0b11 ซึ่งเป็นสิ่งที่เราต้องการ
ประการที่สามสำหรับจำนวนเต็ม 1 และ 2 ไบต์ไม่มีผล นี่เป็นค่าที่ยอดเยี่ยมสำหรับค่า 2 ไบต์เนื่องจาก MSB จะยังคงอยู่และค่าไบต์ 1 ค่าจะไม่มี MSB ใด ๆ ในทุก ๆ ด้านดังนั้นจึงเป็น 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
ต่อไปเราใช้หน้ากากที่มีค่า 0x7F00 และดำเนินการเพิ่มความอิ่มตัวที่ไม่ได้ลงนามในสตรีมบิตควบคุม ในกรณีของจำนวนเต็ม 1234 สิ่งนี้ไม่มีผลจริง เรารักษา MSB ไว้ในไบต์ที่ต่ำที่สุด อย่างไรก็ตามคุณจะทราบว่าไบต์เพียงอย่างเดียวที่มี MSB อยู่นั้นเป็นครั้งสุดท้ายดังนั้นการดำเนินการ MSB Pack จะส่งผลให้ค่า 0b0001 ซึ่งเป็นสิ่งที่เราต้องการ ตัวอย่างของขั้นตอนนี้บนจำนวนเต็ม 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
ที่นี่เราสามารถใช้การดำเนินการสับเปลี่ยนได้ การดำเนินการสับเปลี่ยนแบบเวกเตอร์จัดเรียงไบต์ใหม่ในการลงทะเบียนอินพุตตามหน้ากากที่ให้ไว้ในการลงทะเบียนปลายทาง ทุกตำแหน่งในหน้ากากจะเก็บชดเชยลงในสตรีมเวกเตอร์ต้นทางที่แสดงถึงไบต์ข้อมูลที่ควรเข้าสู่ตำแหน่งนั้น
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
เราเก็บตารางการค้นหา prebuilt ที่มีการแมปจากไบต์ควบคุมไปยังหน้ากากที่จำเป็นและเพียงแค่โหลดว่าหลังจากเราสร้างไบต์ควบคุมด้านบน นอกจากนี้เราเก็บตารางการค้นหาสำหรับการแมปจากไบต์ควบคุมไปจนถึงความยาวที่เข้ารหัสทั้งหมด สิ่งนี้ช่วยให้เรารู้ว่าจะเพิ่มตัวชี้เอาท์พุทและการเขียนทับได้มากน้อยเพียงใดตัวอย่างเช่น 3 ไบต์บนซ้ำซ้อนในตัวอย่างการสลับด้านบน
การเปิดตัวในระหว่างการถอดรหัสนั้นเหมือนกับข้างต้น แต่กลับด้าน เราต้องเปลี่ยนจากรูปแบบที่บรรจุไปเป็นรูปแบบหน่วยความจำที่ยังไม่ได้บรรจุ เราเก็บตารางการค้นหาเพื่อรักษาการแมปจากไบต์ควบคุมไปยังหน้ากากแบบย้อนกลับแบบไม่มีการเปลี่ยนแปลงแล้วดำเนินการสับเปลี่ยนเพื่อส่งออกไปยังอาร์เรย์ uint32
สตรีม VBYTE: การบีบอัดจำนวนเต็มที่มุ่งเน้นไบต์เร็วขึ้น
