อัลกอริทึม SIMD ที่ออกแบบตั้งแต่ต้น

 (mcyoung.xyz)
2 คะแนน โดย GN⁺ 2023-11-29 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โค้ดค base64 vb64 ที่สร้างด้วย std::simd ของ Rust จะกลายเป็นโค้ด SIMD ที่เร็วและพกพาได้ก็ต่อเมื่อออกแบบการจัดวางข้อมูลและลำดับการคำนวณใหม่ให้เหมือนวงจร แทนที่จะเวกเตอร์ไรซ์ลูปเชิงขั้นตอนแบบเดิมตรง ๆ
  • การปรับแต่งหลักอยู่ที่การลด stall ที่เกิดจาก branch และการเข้าถึงหน่วยความจำ โดยสร้างโครงสร้างแบบ branchless ที่ทำงานเหมือนกันไม่ขึ้นกับอินพุต ด้วย comparison, mask, select และ shuffle
  • ในการถอดรหัส base64 จะสร้าง perfect hash โดยใช้ byte >> 4 และการปรับแก้สำหรับ / เพื่อแปลงอักขระ ASCII เป็น sextet แล้วใช้ lookup table ภายในเวกเตอร์ SIMD ร่วมกับ shuffle เพื่อหา offset
  • เมื่อต้องแพ็ก sextet ขนาด 6 บิตสี่ตัวให้เป็นสามไบต์ จะขยาย lane เป็น u16 แล้ว shift จากนั้นแยก low/high byte และรวมชิ้นส่วนไบต์ของ lane ข้างเคียงด้วย rotate_lanes_left และ OR
  • ในเบนช์มาร์ก หลังใช้ชุด -Zbuild-std, -Ctarget-cpu=native, N = 32 และปรับแต่งการโหลด remainder แล้ว แสดง ประสิทธิภาพราว 2 เท่า เมื่อเทียบกับ implementation base64 baseline บน crates.io ในเกือบทุกช่วง

พื้นฐานทางกายภาพที่ทำให้ต้องใช้ SIMD

  • การเพิ่มประสิทธิภาพคอมพิวเตอร์ไม่ได้เชื่อมโยงกับวิทยาการคอมพิวเตอร์เชิงทฤษฎีเท่านั้น แต่เกี่ยวข้องโดยตรงกับ ข้อจำกัดทางกายภาพ
  • ณ ปี 2023 Moore’s law ยังดูเหมือนจะคงอยู่ แต่ในช่วง 15 ปีที่ผ่านมา ผลของ Dennard scaling พังทลายลง ทำให้ทรานซิสเตอร์ที่หนาแน่นขึ้นนำไปสู่ความหนาแน่นการใช้พลังงานที่สูงขึ้น
  • หลังจากการเพิ่มความถี่สัญญาณนาฬิกาต่อไปทำได้ยาก ตั้งแต่ต้นทศวรรษ 2000 ทิศทางหลักของการเพิ่มประสิทธิภาพจึงย้ายไปสู่การใช้คอร์จำนวนมากขึ้น
  • มัลติเธรดต้องอาศัยความร่วมมือระหว่างคอร์ จึงมีต้นทุนการซิงโครไนซ์ และ control flow เช่น jump, virtual call, synchronization ทำให้เกิด stall
  • สาเหตุหลักของ stall มีสองอย่าง
    • branch: control flow อย่าง if, ลูป, การเรียกฟังก์ชัน, การคืนค่าจากฟังก์ชัน, switch ของ C
    • งานหน่วยความจำ: load/store โดยเฉพาะการเข้าถึงที่ไม่เป็นมิตรกับแคช

โค้ดเชิงขั้นตอนและ instruction-level parallelism

  • คอร์ CPU สมัยใหม่ไม่ได้รันโค้ดทีละบรรทัด แต่จะออกคำสั่งการคำนวณที่ไม่ขึ้นต่อกันพร้อมกัน
  • การคำนวณที่ไม่ขึ้นต่อกัน เช่น a = x + y และ b = x ^ y สามารถใช้วงจร add และ xor พร้อมกันได้
  • วิธีนี้คือ instruction-level parallelism และ dependency ที่ขัดขวางสิ่งนี้เรียกว่า data hazard
  • ยิ่ง CPU สามารถทำให้ functional unit อิ่มตัวได้ดีเท่าไร ก็ยิ่งประมวลผลการคำนวณได้มากขึ้นต่อหน่วยเวลา
  • branch ต้องรอให้คำนวณเงื่อนไขเสร็จก่อนจึงจะดึงคำสั่งถัดไปได้ ส่วนงานหน่วยความจำต้องรอให้ข้อมูลเดินทางมาถึง CPU ทางกายภาพ จึงเกิด stall
  • GPU จัดการภาพในรูปแบบพิกเซลแบบเวกเตอร์และทำงานที่มี locality สูงจำนวนมาก จึงใกล้เคียงกับเครื่อง SIMD ที่ออกแบบมาให้เหมาะกับการประมวลผลแบบ batch และ control flow ที่จำกัด
  • SIMD คือ single instruction, multiple data เป็นวิธีที่คำสั่งหนึ่งคำสั่งทำการคำนวณแบบขนานบน data lane หลายตัว

วิธีคิดแบบ lane

  • SIMD และ vector มักถูกใช้ในความหมายเดียวกัน และหน่วยพื้นฐานของคำสั่ง SIMD คือ vector ซึ่งเป็นอาร์เรย์ตัวเลขขนาดคงที่
  • องค์ประกอบแต่ละตัวของ vector เรียกว่า lane
  • เวกเตอร์ SIMD ต้องอยู่ในรีจิสเตอร์ได้ จึงมักมีขนาดเล็ก
    • ความกว้างเวกเตอร์สูงสุดของสภาพแวดล้อมตัวอย่างคือ 256 บิต
    • เท่ากับ 32 ไบต์ของ u8x32 หรือ double 4 ตัวของ f64x8
  • แม้เป็นเวกเตอร์ขนาดเล็ก หากลดภาระการทำให้ pipeline อิ่มตัวได้ 4 เท่า ก็อาจนำไปสู่การปรับปรุง latency ได้ในสัดส่วนนั้น

divide and conquer ที่เห็นจาก popcnt

  • การคำนวณเวกเตอร์ที่ง่ายที่สุดคือ bitwise and/or/xor
  • จำนวนเต็มทั่วไปก็สามารถมองเป็นเวกเตอร์ของ lane ขนาด 1 บิตได้จากมุมมองของ bitwise operation
    • จากมุมมองนี้ i32 เทียบเท่ากับ i1x32
  • popcnt คือการคำนวณที่นับจำนวนบิต 1 ในจำนวนเต็ม และหากมอง i32 เป็น i1x32 ก็ถือเป็นการคำนวณแบบ reduce
  • implementation แบบง่ายที่ดึง 32 บิตออกมาเป็นอาร์เรย์แล้วบวกกันอาจสร้างโค้ดที่แย่
  • วิธีที่ดีกว่าคือเพิ่มความกว้างของ lane ไปพร้อมกับรวมผล โดยบวกบิตคู่ที่อยู่ติดกัน แล้วบวกคู่ของคู่ต่อไปเรื่อย ๆ
    • แยกบิตตำแหน่งคู่/คี่ด้วย mask 0x55555555, 0xaaaaaaaa
    • ใช้ shift เพื่อจัด lane ให้ตรงกันแล้วบวก
    • จากนั้นทำซ้ำในหน่วย 2 บิต, 4 บิต, 8 บิต, 16 บิต
  • implementation นี้ไม่ได้ถูกปรับให้เป็นคำสั่ง popcnt แต่จะเป็นโค้ดที่เล็กและเร็วบนระบบที่ไม่มีคำสั่งดังกล่าว
  • สามารถนำไปใช้กับ u64 ได้โดยเพิ่มขั้นตอน reduction อีกหนึ่งขั้นเท่านั้น และไม่จำเป็นต้องใช้การบวก u64 ทั้งตัว
  • แนวทาง divide and conquer เช่นนี้เป็นแพตเทิร์นสำคัญของการเขียนโปรแกรม SIMD

เครื่องมือหลักของชุดคำสั่ง SIMD

  • เวกเตอร์ SIMD จริงให้ความหมายที่ซับซ้อนกว่า scalar และฟีเจอร์สำหรับทดแทน control flow ที่ช้ามีความสำคัญเป็นพิเศษ
  • คำสั่งที่ใช้ได้ขึ้นอยู่กับสถาปัตยกรรมอย่างมาก
    • คอร์ประสิทธิภาพสูงจำนวนมากของ x86 implement AVX2
    • AVX2 ให้เวกเตอร์ ymm ขนาด 256 บิต
    • ตัวรีจิสเตอร์เองไม่มีจำนวน lane กำกับอยู่ แต่คำสั่งจะกำหนดวิธีตีความ lane
    • ตัวอย่างเช่น vpaddb ตีความ ymm เป็น i8x32
  • การคำนวณที่โดยทั่วไปใช้ได้มีดังนี้
    • bitwise operation: ความกว้างของ lane เป็น 1 บิตโดยนัยเสมอ
    • lane-wise arithmetic: การบวก ลบ คูณ หาร integer shift, min/max ฯลฯ
    • lane-wise comparison: สร้าง mask vector เช่น m[i] = a[i] < b[i]
    • select: ใช้ mask เพื่อเลือกค่าจากเวกเตอร์สองตัวแยกตาม lane
    • shuffle/swizzle: มองเวกเตอร์หนึ่งเป็นเหมือน lookup table แล้วจัดเรียง lane ใหม่ด้วย index vector
  • true/false ของ mask vector มักใช้รูปแบบบิต all-ones หรือ all-zeros
  • comparison และ select เป็นเครื่องมือหลักที่ช่วยให้โค้ด SIMD คงสถานะ branchless
  • โค้ด branchless ทำงานเหมือนกันโดยไม่ขึ้นกับอินพุต และทิ้งผลลัพธ์ที่ไม่จำเป็นด้วยคุณสมบัติอย่าง x * 0 = 0, a ^ b ^ a = b

ใช้ shuffle เพื่อจัดตำแหน่งข้อมูล

  • shuffle เป็นเครื่องมือหลักใน SIMD ที่ทำให้ข้อมูลมาอยู่ใน “ตำแหน่งที่ถูกต้อง”
  • broadcast หรือ splat สร้างเวกเตอร์ที่ทุก lane มี scalar เดียวกัน และสามารถแสดงได้ด้วย index shuffle แบบ [0, 0, ...]
  • interleave หรือ zip/pack คือการวาง lane ของเวกเตอร์สองตัว a, b สลับกัน
    • c = [a[0], b[0], a[1], b[1], ...]
    • สามารถ implement ด้วย shuffle2 ได้
  • deinterleave หรือ unzip/unpack คือสิ่งตรงข้ามของ interleave
  • rotate หมุน lane ในรูป b[i] = a[(i + j) % n] และสิ่งนี้ก็เป็น shuffle เช่นกัน
  • ในการเขียนโปรแกรม SIMD มักต้องตีความและจัดวางบล็อกข้อมูลที่ใหญ่กว่าจำนวนเต็มใหม่ให้เป็นบล็อกเล็ก ๆ หลายขนาด

intrinsics, target feature, portable SIMD

  • การดำเนินการที่ใช้ได้ใน SIMD จะแตกต่างกันไปตามสถาปัตยกรรมและ instruction set extension
  • x86 อาจมีการดำเนินการที่ ARM ไม่มี และแม้แต่ภายในผู้ผลิตเดียวกันก็อาจมีส่วนขยายที่มีเฉพาะในชิปเซิร์ฟเวอร์ระดับสูง เช่น Intel AVX-512
  • toolchain ทำให้ส่วนขยายเหล่านี้เป็นนามธรรมทั่วไปในรูปของ target feature
    • lscpu บน Linux แสดง feature ที่ CPU รับรู้
    • LLVM จะเลือกคำสั่งต่างกันตามการตั้งค่า feature
    • ต้องมี +avx2 LLVM จึงจะสร้างโค้ดที่ใช้ ymm ได้
  • -march=native หรือ -Ctarget-cpu=native สามารถสร้างโค้ดที่ดีให้เหมาะกับเครื่องที่ใช้ build ได้ แต่ความสามารถในการพกพาไปยังโปรเซสเซอร์อื่นอาจลดลง
  • runtime feature detection คือวิธีตรวจสอบความสามารถที่ CPU รองรับ แล้วตัดสินใจว่าจะเรียกฟังก์ชันเวอร์ชันใด ใช้ในโค้ดที่เผยแพร่ไปยังอุปกรณ์หลากหลาย เช่น ไลบรารีเข้ารหัส
  • โค้ด SIMD ใน C++ มักใช้ intrinsics เช่น _mm256_cvtps_epu32
    • แทนการดำเนินการระดับต่ำของ instruction set เฉพาะ
    • ไม่จำเป็นต้อง map เป็นคำสั่งเดียวเสมอไป
    • compiler สามารถทำการรวม กำจัดส่วนซ้ำ และปรับแต่งการเลือกคำสั่งได้
  • หากต้องเขียนโค้ดคล้ายกันซ้ำ ๆ สำหรับหลาย instruction set ข้อดีด้านการบำรุงรักษาเมื่อเทียบกับ assembly อาจไม่มากนัก
  • ไลบรารี portable SIMD เป็นแนวทางที่จัดการการเลือกคำสั่งบางส่วนในระดับไลบรารี และปล่อยส่วนที่เหลือให้ compiler
  • การ implement vb64 เป็นการทดลองเพื่อดูว่า portable SIMD ของ Rust สร้างโค้ดที่แข่งขันได้หรือไม่

เปลี่ยนการ decode base64 เป็น SIMD

  • base64 เป็นวิธี encode ข้อมูลไบนารีใด ๆ ให้เป็น ASCII
  • มอง byte string ขาเข้าเป็น bit vector แล้วแบ่งเป็น chunk ขนาด 6 บิตที่เรียกว่า sextet
  • ค่า sextet จะถูก map เป็นอักขระต่อไปนี้
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • base64 มีหลายรูปแบบย่อย แต่ความซับซ้อนส่วนใหญ่เหมือนกัน
  • มีสองประเด็นที่ต้องระวัง
    • base64 เป็นรูปแบบที่บิตภายในไบต์เป็น big endian
    • ความยาวอินพุตอาจหารด้วย 4 ไม่ลงตัว โดยหลักแล้วจะใช้ padding = ให้เป็นจำนวนเท่าของ 4 แต่ก็สามารถจัดการข้อความที่ padding ไม่ถูกต้องได้
  • decoded length คำนวณโดยเอา input / 4 * 3 แล้วบวกความยาวส่วนที่เหลือตาม input % 4

การ refactor พื้นฐานเพื่อไปสู่ branchless

  • decoder base64 แบบเรียบง่ายมี branch หลายจุด
    • loop ที่ไล่ตาม chunk ของอินพุต
    • loop ของ byte ภายใน chunk
    • match ตามอักขระ ASCII
    • return Err เมื่อเกิดข้อผิดพลาด
    • match ภายใน decoded_len
    • ความเป็นไปได้ที่จะเรียก Vec::extend_from_slice และ allocator
  • แนวทางการ optimize คือ ลบ branch ทั้งหมด
  • match ของ decoded_len map ค่า input % 4 คือ 0, 1, 2, 3 เป็น 0, 1, 1, 2
  • หากเปลี่ยนเป็น mod4 - mod4 / 2 ก็จะเป็นเวอร์ชัน branchless
  • LLVM สามารถพับ match เดิมให้เป็น switch table ได้ แต่ในบริเวณนี้ การเข้าถึงหน่วยความจำที่ไม่จำเป็นทำให้ประสิทธิภาพลดลง

แยก loop ที่ร้อนที่สุดออกมา

  • จุดแข็งของ SIMD คือการประมวลผลข้อมูลจำนวนมากในครั้งเดียว ทำให้ unroll loop ได้แรงและทำให้ใกล้เคียง branchless
  • เป้าหมายของ hot loop คืออ่านได้สูงสุด 4 ไบต์ สร้างผล decode ได้สูงสุด 3 ไบต์ และแจ้งได้ด้วยว่ามี syntax error หรือไม่
  • มีข้อเท็จจริงที่นำมาใช้ได้สามอย่าง
    • ความยาวเอาต์พุตคำนวณได้ด้วย decoded_len() แบบ branchless
    • มอง base64 ที่ไม่ถูกต้องเป็นเส้นทางที่พบได้น้อยมาก และหากต้องการตำแหน่งข้อผิดพลาดก็สามารถสแกนซ้ำภายหลังได้
    • ใน base64 ตัว A มีค่าเป็น 0 ดังนั้นการ padding truncated chunk ด้วย A จะไม่ทำให้ค่าเปลี่ยน
  • decode_hot() ถูกแยกออกมาเป็นรูปแบบที่ประมวลผลไบต์อินพุตสี่ตัว แล้วคืนผลลัพธ์ที่ decode แล้วพร้อม bool ว่าสำเร็จหรือไม่
  • หากคืน bool แยกต่างหากแทน Option<[u8; 3]> จะทำให้ง่ายต่อการลบ branch if !ok ในภายหลัง
  • ในเวอร์ชัน SIMD รับ Simd<u8, 4> เป็นอินพุต และตั้งเอาต์พุตเป็น Simd<u8, 4> ให้ตรงกับจำนวน lane ที่เป็น power-of-two ด้วย
    • เอาต์พุตที่ต้องใช้จริงคือ 3 ไบต์
    • lane สุดท้ายไม่ถูกใช้งาน

วิธีเปลี่ยน ASCII เป็น sextet

  • match ที่เปลี่ยนอักขระ ASCII เป็น sextet ส่วนใหญ่สามารถเขียนในรูป byte - C ได้
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • สร้าง vector offset แยกตาม lane แล้วทำ ascii - offsets ก็พอ
  • แนวทางแรกคือ compare-and-select
    • สร้าง mask สำหรับ A-Z, a-z, 0-9, +, /
    • lane ที่ไม่มี mask ใดถูกเลือกจะถือว่า invalid
    • splat offset ที่สอดคล้องกับแต่ละ mask แล้วรวมด้วย OR
  • วิธีนี้สร้างโค้ดที่สง่างามและแข่งขันได้ แต่ต้องเปรียบเทียบรวม 8 ครั้ง และมีค่าที่ยังมีชีวิตอยู่จำนวนมาก ทำให้เกิด register pressure ได้

SIMD hash table และ perfect hash

  • ช่วง byte ของ A-Z, a-z, 0-9 คือ 0x41..0x5b, 0x61..0x7b, 0x30..0x3a ตามลำดับ และมี high nibble ต่างกัน
  • + และ / คือ 0x2b, 0x2f ดังนั้นแค่ byte >> 4 ก็แยกแยะได้เกือบทั้งหมด
  • กรณี / หากลบออกหนึ่ง จะกลายเป็น perfect hash สำหรับช่วงดังกล่าว
  • การ map ของ (byte >> 4) - (byte == '/') เป็นดังนี้
    • A-Z → 4 หรือ 5
    • a-z → 6 หรือ 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • ค่านี้มีขนาดเล็ก จึงใส่ offset lookup table ไว้ใน SIMD vector แล้ว lookup ด้วย shuffle ได้
  • แนวคิด perfect hash นี้เสนอโดยผู้ใช้ไม่ระบุตัวตนใน GitHub issue
  • Simd::swizzle_dyn() มีข้อจำกัดว่า index array และความยาวของ lookup table ต้องเท่ากัน
  • ในวิธี perfect hash กระบวนการคำนวณ sextet ไม่ได้ให้ validation มาเป็นผลข้างเคียง จึงตรวจสอบความถูกต้องของ byte ด้วย exact bloom filter จาก GitHub issue เดียวกัน
  • ตัวอย่าง implementation อยู่ที่ simd.rs ของ vb64

การ pack sextet สี่ตัวเป็นสามไบต์

  • ขั้นตอนรวม sextet ขนาด 6 บิตสี่ตัวให้เป็นสามไบต์นั้นยากกว่า
  • หากตั้ง sextet อินพุตตัวใดตัวหนึ่งเป็น all-ones แล้วดูว่าบิตย้ายไปที่ใดในเอาต์พุต ก็จะติดตามความสัมพันธ์ของการจัดวางได้
  • shuffle ระดับ byte อย่างเดียวไม่เพียงพอ
    • เป้าหมายที่ต้องย้ายเป็นชิ้นส่วนของไบต์
    • ใช้ shift อย่างเดียวก็ยังไม่พอ
    • บิตที่ถูก overshift ต้องย้ายไปยัง lane ที่อยู่ติดกัน
  • วิธีแก้คือ ทำให้ lane ใหญ่ขึ้น
  • cast sextets เป็น vector u16 แล้ว shift แยกตาม lane
    • input[0] shift 2 บิต
    • input[1] shift 4 บิต
    • input[2] shift 6 บิต
    • input[3] shift 8 บิตเพื่อปรับตำแหน่ง
  • แยก vector ของ low byte และ high byte จากผลลัพธ์ของ shift
  • ใช้ hi.rotate_lanes_left::<1>() จัดชิ้นส่วนฝั่ง high byte ให้ตรงกับ lane ข้างเคียง แล้วรวมด้วย lo | hi_rotated
  • วิธีนี้ใช้ hardware primitive อย่างจริงจัง ทำให้โค้ดสั้นและมีประสิทธิภาพ

การขยายจำนวน lane และการกำจัด garbage lane

  • Simd<u8, 4> มีขนาดเล็กกว่าเวกเตอร์รีจิสเตอร์ขั้นต่ำ 128 บิตของ x86 ด้วยซ้ำ จึงทำให้ decode_hot() เป็น generic ตามจำนวน lane N
  • ใช้ข้อจำกัด LaneCount<N>: SupportedLaneCount เพื่อรับประกันจำนวน lane แบบ power-of-two ขนาดเล็ก
  • lookup table และ shift table สร้างเวกเตอร์ที่เป็นแพตเทิร์นซ้ำด้วย helper tiled()
  • ในกรณี N = 4 แค่ละเว้นค่า garbage ใน lane สุดท้ายก็พอ แต่เมื่อ N ใหญ่ขึ้น garbage จะปนอยู่ใน every fourth lane
  • เพื่อกำจัดสิ่งนี้จึงใช้ shuffle
    • ความสัมพันธ์ที่ต้องการคือ shuffled[i] = output[i + i / 3]
    • ลบ garbage lane โดยข้ามทุก ๆ อินเด็กซ์ที่สี่
    • ส่วนที่ overflow เป็น 1/4 ด้านบนของเวกเตอร์เอาต์พุตสุดท้าย จึงละเว้นได้
  • ด้วยวิธีนี้ decode_hot::<32>() จะสามารถถอดรหัส base64 byte จำนวน 32 ตัวแบบขนานได้

การปรับ outer loop ให้เหมาะสม

  • decode() ก็ถูกเปลี่ยนให้เป็น generic ตามจำนวน lane ภายใน N ด้วย
  • ต้นทุนที่ยังเหลืออยู่มีดังนี้
    • branch เปรียบเทียบความยาวของ for chunks in ...
    • memcpy แบบ variable-length ของ [T]::copy_from_slice
    • branch ok ในแต่ละ loop iteration
    • ความเป็นไปได้ในการเรียก allocator ของ Vec::extend_from_slice และ memcpy อีกชุดหนึ่ง
  • เนื่องจากทราบความยาวเอาต์พุตอยู่แล้ว จึงจองพื้นที่ล่วงหน้าด้วย out.reserve(final_len + N / 4)
  • นอกจากนี้ยังเผื่อพื้นที่ slop ไว้ เพื่อทำ full SIMD store แทน variable-length memcpy
  • แต่ละ iteration จะเขียน SIMD vector ทั้งก้อน และการเขียนครั้งถัดไปจะเลื่อนไป 3/4 * N เพื่อเขียนทับ garbage byte ก่อนหน้า
  • garbage byte สุดท้ายจะไม่ถูกรวมอยู่ใน Vec::set_len() สุดท้าย จึงถูกจัดการเหมือนถูกลบไปแล้ว
  • แม้จะ early return เพราะ if !ok แต่ยังไม่ได้ commit ด้วย set_len() ดังนั้น out จึงยังคงอยู่ในสถานะที่ไม่ถูกแก้ไข

เลื่อนการจัดการข้อผิดพลาดออกนอก hot loop

  • ไม่ return ด้วย if !ok ในทุก iteration แต่สะสมด้วย error |= !ok
  • ตรวจสอบว่ามีข้อผิดพลาดหรือไม่เพียงครั้งเดียวก่อน set_len() สุดท้าย
  • ภายใต้สมมติฐานว่า base64 blob ส่วนใหญ่ valid เส้นทางข้อผิดพลาดจึงถูกดันออกไปนอก hot loop
  • แม้จะมี syntax error การคำนวณ SIMD หลังจากนั้นก็จะไม่ misbehave แบบสุ่ม ดังนั้น garbage write จะไม่ถูก commit และหายไป
  • หลังจากนั้น การเรียกอย่าง Vec::push() อาจเขียนทับพื้นที่บัฟเฟอร์เดียวกันได้

unroll and jam และการจัดการ remainder

  • ใช้ unroll and jam เพื่อลด variable-length memcpy ของ copy_from_slice
  • แบ่งลูปออกเป็นสองส่วน
    • hot vectorized loop: ประมวลผลอินพุตความยาว N เสมอ
    • cold remainder part: ประมวลผลอินพุต i < N ไม่เกินหนึ่งครั้ง
  • ใช้ Iterator::chunks_exact() ของ Rust เพื่อทำ hand-rolled unroll-and-jam
  • ใน hot loop เรียก Simd::from_slice() เพื่อทำ load ขนาดเท่าเวกเตอร์เพียงครั้งเดียว
  • bounds check จะอยู่ในรูปแบบที่คอมไพเลอร์กำจัดได้ง่าย

เบนช์มาร์กและการปรับ manual loading ให้เหมาะสม

  • เบนช์มาร์กถอดรหัสข้อความตั้งแต่ความยาว 0 จนถึงประมาณ 200 หรือ 500 ไบต์ และเปรียบเทียบกับ implementation base64 baseline บน crates.io
  • ตัวเลือกคอมไพล์ใช้ -Zbuild-std และ -Ctarget-cpu=native
  • ผลการจูนพบว่า N = 32 ดีที่สุด และใช้ YMM register หนึ่งตัวต่อ hot loop iteration
  • ตอนแรกชนะ baseline แต่เกิดความผันผวนของประสิทธิภาพในรูปแบบ heartbeat ที่สัมพันธ์อย่างมากกับ data.len() % 32
  • หลังตรวจสอบ assembly จึงสรุปว่า copy_from_slice น่าจะถูก inline/unroll เป็น byte-wise load loop
  • ลองใช้ Simd::gather_or() ด้วย แต่สร้าง assembly ที่แย่กว่า จึงไม่ใช้
  • แทนที่จะใช้วิธีนั้น ได้เขียนฟังก์ชัน manual loading สำหรับข้อมูล variable-length
    • hot part ทำ u128 load ซึ่งเป็น scalar load ขนาดใหญ่เท่าที่ทำได้ในลูป
    • LLVM ลด 16-byte chunk ลงเป็น XMM load
    • remainder ใช้ load แบบซ้อนทับกันด้วย u64, u32, u8
  • เมื่ออ่าน 15 ไบต์ จะอ่าน u64 ที่ p และ u64 ที่ p + 7 ให้ซ้อนทับกัน 1 ไบต์ แล้วรวมด้วย OR
  • สำหรับ 4~7 ไบต์ ใช้ u32 load ที่ซ้อนทับกัน
  • สำหรับ 1~3 ไบต์ อ่านจาก p, p + len/2, p + len - 1 ซึ่งอาจ load byte บางส่วนซ้ำ แต่ช่วยลดจำนวน branch
  • หลังใช้ loading code ใหม่ variance ลดลงมาก และแสดง ประสิทธิภาพ 2 เท่า เมื่อเทียบกับ baseline ในแทบทุกช่วง

encoding และ web-safe base64

  • ฟังก์ชัน encoding แค่ต้อง implement encode_hot() ที่ทำการคำนวณของ decode_hot() แบบย้อนกลับ
  • perfect hash ที่ใช้ในการถอดรหัสไม่เหมาะกับ encoding จึงต้องใช้ hash ใหม่
  • โค้ด loading/storing รอบ encoder ก็แตกต่างจาก decoder เล็กน้อย
  • vb64 ยัง implement routine สำหรับ encoding ที่มีประสิทธิภาพด้วย
  • web-safe base64 เป็นรูปแบบดัดแปลงที่เปลี่ยน + และ / เป็น - และ _
  • การสร้าง perfect hash สำหรับ web-safe base64 ยุ่งยากกว่า และอาจต้องใช้วิธีอย่าง (byte >> 4) - (byte == '_' ? '_' : 0) เป็นต้น
  • vb64 ยังไม่รองรับ web-safe base64

สรุป

  • vb64 ระบุว่าไม่ได้เป็นไลบรารีที่พยายามแก้คอขวดสำคัญ และไม่ทราบว่าที่ใดมี base64 decoding เป็นคอขวดจริง ๆ
  • โค้ด branchless มักจะเกินความจำเป็น แต่ช่วยให้เข้าใจว่าคอมไพเลอร์ทำอะไรให้ได้และทำอะไรให้ไม่ได้
  • std::simd ของ Rust โดยรวมถือว่าดีและสร้างโค้ดที่ยอดเยี่ยม
  • แม้จะมี rough edge บางอย่างที่อยากให้แก้เพื่อทำให้โค้ด SIMD ง่ายขึ้น แต่ประเมินว่าพอใจกับผลลัพธ์ของงานในปัจจุบัน
  • SIMD และการปรับประสิทธิภาพเป็นหัวข้อซับซ้อนที่ต้องใช้ทริกและความรู้ด้านฮาร์ดแวร์จำนวนมาก และหลายส่วนในนั้นไม่ได้ถูกจัดทำเป็นเอกสาร

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-11-29
ความคิดเห็นจาก Hacker News

  • เห็นการใช้งาน portable SIMD จริง ๆ แล้วน่าสนใจ และพอลองทำเบนช์มาร์กซ้ำบนระบบ Zen 3 ก็ได้ความเร็วเพิ่มขึ้นเท่าเดิม
    บน M1 MacBook Pro เมื่อความยาวอินพุต 110 ไบต์ ประสิทธิภาพเริ่มดีขึ้น 1.4 เท่าแล้วค่อย ๆ เพิ่มไปถึง 2 เท่า แม้จะต่ำกว่า x86_64 แต่ก็ดูเหมือนบรรลุเป้าหมายแล้ว
    อย่างไรก็ตาม เมื่อดูโค้ดแล้ว ก็ยืนยันประสบการณ์ของผมว่า Rust มี ergonomics ที่ค่อนข้างแย่ ในงานที่เกี่ยวกับ SIMD และ pointer รวมถึง performance engineering ในภาพกว้าง

    • ในฐานะวิศวกร Rust ผมเห็นด้วยในระดับหนึ่ง แต่ pointer และงานกับหน่วยความจำดิบถูกจำกัดไว้เยอะโดยเจตนาเพราะเรื่องความปลอดภัย และมีแง่ที่ต้องการบังคับให้เราคิดจริง ๆ ว่าภาษากำลังทำอะไรอยู่
      ถึงอย่างนั้น portable SIMD ของ Rust ก็ยังไม่ใช่เรื่องที่น่าพูดถึงนักเมื่อเทียบกับ C++ และถ้าจะลงไปทำงานกับพื้นที่ไบต์ดิบ pointer และการจัดการบัฟเฟอร์ ก็ต้องคุ้นกับ Pin, MaybeUninit เป็นต้น
      portable_simd และ allocator_api อยู่ในสถานะไม่เสถียรมาหลายปีแล้ว แถมกำแพงในการเริ่มใช้ก็สูงและยังดูขัดมือกว่าเดิม ซึ่งส่วนใหญ่เป็นการออกแบบโดยตั้งใจ
      แต่ก็ไม่มีอะไรห้ามไม่ให้สร้าง abstraction ที่ใช้ง่ายขึ้นภายในโปรแกรมของตัวเอง หรือใช้ crate จากบุคคลที่สาม
    • ผมไม่เห็นด้วยว่า ergonomics แย่
      SSE intrinsic ของ C++ แย่กว่ามาก ทั้ง underscore ก็ดูรกตา และชื่อก็จำยาก

  • ผมเคยพยายามทำ implementation แบบ C++ คลาสสิกให้ดีที่สุดแล้ว แต่พอมีคนทำเวอร์ชัน SIMD มาให้ที่ เร็วกว่า 10 เท่าขึ้นไป บางครั้งก็น่าทึ่งจริง ๆ
    แต่โค้ดแบบนี้ portability ต่ำกว่า
    อยากให้ auto-vectorization ของคอมไพเลอร์ดีขึ้นกว่านี้ และอยากให้มีการรองรับระดับภาษา เช่น annotation ที่อนุญาตให้จัดลำดับบาง operation ใหม่ได้เฉพาะจุด

    • โค้ด SIMD ที่ดีต้องพิจารณาอย่างละเอียดว่าข้อมูลถูกวางในหน่วยความจำอย่างไร
      คอมไพเลอร์ไม่สามารถแก้ข้อมูลแทนเราได้นอกบริบทที่เฉพาะจุดมาก ๆ ทำให้ auto-vectorization ยากจริง ๆ
    • แม้คอมไพเลอร์จะ optimize ได้สมบูรณ์แบบ ก็ยังมีการรับประกันแบบลำดับที่หลีกเลี่ยงไม่ได้อยู่มาก
      เช่นใน for(double v: vec) sum+=v การบวก floating point ไม่เป็น associative ดังนั้นการบวกค่าตามลำดับ กับวิธี SIMD ที่บวกทีละช่วงห่าง 8 ค่าแล้วค่อยรวมส่วนที่เหลือ จึงไม่เหมือนกัน
      จากมุมมองคอมไพเลอร์ อาจดูเหมือนเป็น optimization ที่ชัดเจน แต่ตราบใดที่เราไม่ได้บอกให้ผ่อนปรนการรับประกันบางอย่าง มันก็จะให้ความสำคัญกับ การรับประกัน semantics แบบลำดับ มากกว่า optimization
      เลยยุ่งเหยิงขึ้น และอย่างที่ janwas ว่า สำหรับ hot path ผมคิดว่าควรใช้ไลบรารี โดยเฉพาะอย่าง Google Highway หรือ Intel ISPC จะดีกว่า
    • นั่นเป็นหนึ่งในประเด็นของ ภาษาโปรแกรมมิงระบบ อย่าง C++
      คือพยายามให้มีประสิทธิภาพและ portable เท่าที่ทำได้ แต่เมื่อจำเป็นก็ทำให้การเขียนโปรแกรมเฉพาะ target ทำได้ง่าย
      auto-vectorization นั้นคอมไพเลอร์ FORTRAN ทำได้ดีกว่าอย่างชัดเจน เพราะไม่อนุญาต aliasing
      C++ ถูกถ่วงไว้เพราะต้องตาม memory model ของ C
    • จะใช้ CUDA เฉย ๆ ก็ได้
      CUDA คือ C++ ที่ออกแบบมาสำหรับ GPU ซึ่งเป็นเครื่อง SIMD ขั้นสุดของยุคนี้ และ ROCm ก็แทบจะเป็น CUDA สำหรับ AMD
      ส่วนตัวผมชอบ C++AMP ของ Microsoft เพราะคิดว่าเริ่มต้นได้ง่ายที่สุด
      แต่น่าเสียดายที่ท้ายที่สุดมันไม่ได้ติดตลาด
    • เรื่องแบบนี้เกิดขึ้นบ่อยจากประสบการณ์ของผม
      อีกอย่าง ถ้าใช้ ไลบรารี wrapper สำหรับ SIMD จริง ๆ แล้วก็ทำให้ portable ได้ค่อนข้างดี

  • หมายเหตุเล็กน้อยคือ คอมไพเลอร์ไม่สามารถ optimize implementation ของ popcount นั้นให้เป็นคำสั่งเดียวได้ แต่ implementation แบบอื่นทำได้
    แน่นอนว่าค่อนข้างจุกจิก: https://godbolt.org/z/T69KxWWW8

  • มีการบอกว่า _mm256_cvtps_epu32 แทน operation ระดับต่ำของชุดคำสั่งเฉพาะ และอธิบายว่าเป็น float-to-int cast ของ AVX2 แต่คำสั่งนั้นอยู่ใน AVX-512
    AVX2 ไม่มี float-to-int cast และใน AVX1 ผลลัพธ์จำนวนเต็มเป็น signed โดยคำสั่งคือ _mm256_cvtps_epi32

  • อยากรู้ว่าจะเทียบกับ fastbase64[0] แล้วเป็นอย่างไร
    บทความยอดเยี่ยม และดีใจที่ได้เห็นเนื้อหาแบบนี้ออนไลน์ แต่คงยากที่จะเห็นด้วยกับความมองโลกในแง่ดีของผู้เขียนที่มีต่อ ไลบรารี portable SIMD
    [0]: https://github.com/lemire/fastbase64

  • ผมคิดว่า ISPC ดีกว่าการเอา SIMD ไปแปะเพิ่มให้ C++ หรือ Rust เฉย ๆ
    มันรองรับ dynamic dispatch ด้วย ซึ่งเป็นฟีเจอร์ที่ถ้าต้อง implement เองจะเจ็บปวดมาก

    • ถ้าเป็นเครื่องมือที่ทำให้คนใช้ SIMD มากขึ้น โดยทั่วไปก็น่าจะเป็นเรื่องดี แต่ส่วนตัวผมชอบให้ SIMD ผสานอยู่ใน toolchain เดียวกันมากกว่า
      แบบนั้นจึงจะเรียกกลับไปยัง C++ แบบ inline ได้ ใช้ template และ class ในโค้ด SIMD ได้ และ inline โค้ด SIMD หลายส่วนเข้าด้วยกันได้
      ผมเห็นด้วยว่า implementation ของ dynamic dispatch ทำยาก แต่ Highway จัดการส่วนนั้นให้แล้ว
    • อยากรู้ว่าใน subroutine เล็ก ๆ แบบในบทความ C++ หรือ Rust จะเรียก ISPC ได้ง่ายแค่ไหน

  • เป็นบทความที่ยอดเยี่ยม และทำให้รู้สึกแรงมากว่า “ฉันคงไม่มีทางฉลาดได้ขนาดนี้”

    • ก็แค่มันไม่ใช่สายงานของคุณเท่านั้นเอง
      คล้ายกับที่คนทั่วไปไม่ได้เป็น software engineer หรือนักฟิสิกส์
      ถ้าตั้งใจศึกษาอย่างจริงจังสักไม่กี่เดือน ก็น่าจะทำได้ในระดับใกล้เคียงกัน
    • ถ้ามีโอกาสเจอนายจ้างหรือโปรเจกต์ที่ต้องการเรื่องแบบนี้ คุณก็น่าจะ “ฉลาดได้ขนาดนั้น”
      สุดท้ายมันเป็นเรื่องของความสนใจและความจำเป็น
      ผมเองก็สลับไปทำ performance optimization หรือ bare-metal engineering ที่ใกล้ระบบมากขึ้นในโปรเจกต์ส่วนตัวอยู่บ้าง แต่ก็อยากให้งานประจำต้องใช้มากกว่านี้
      เพียงแต่สิ่งที่งานส่วนใหญ่ในอุตสาหกรรมต้องการไม่ใช่ด้านนั้น
    • ลองทำ AoC '23 ด้วย APL/j/k, BQN, Python/numpy, CUDA ฯลฯ ก็น่าจะดี
      ไม่ใช่ Python แบบ idiomatic แต่เป็นการแก้ทุกอย่างด้วย numpy
      สนุกและเรียนรู้ความฉลาดแบบนี้ได้ และหลายส่วนของบทความจะรู้สึกเป็นธรรมชาติมากในวิธีคิดเพื่อแก้ปัญหาด้วยภาษาเหล่านั้น
      เมื่อเวลาผ่านไป คุณจะเริ่มมองปัญหาในรูปแบบนั้น
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • เป็นบทความที่น่าสนใจ
    ในตัวอย่างแรกช่วงต้น ผู้เขียนบอกว่าการใช้งาน popcnt ที่ไม่ได้ทำเวกเตอร์ไรซ์จะสร้าง “โค้ดที่แย่จนน่าขันอย่างตรงไปตรงมา” แต่ถ้าใช้โหมด release กับ CPU เป้าหมายแบบ native ดูเหมือนว่าฟังก์ชันนั้นจะถูก เวกเตอร์ไรซ์ ได้ค่อนข้างดี
    https://godbolt.org/z/WE1Eq65jY

    • โค้ดด้านล่างควรให้ผลลัพธ์เทียบเท่ากัน
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      ซึ่งคอมไพล์เป็น popcnt eax, edi; ret
      สำหรับบิตเวกเตอร์ขนาดใหญ่ การใช้งาน AVX2 อาจเร็วกว่า POPCNT
      ดู “Faster Population Counts Using AVX2 Instructions”: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32 บิตยังไม่ใหญ่พอ และโค้ดที่ Rust สร้างขึ้นนั้นแย่จนน่าขันจริง ๆ
    • ตามอุดมคติแล้ว นี่น่าจะถูกลดระดับลงเป็น คำสั่ง popcnt
    • การทำเวกเตอร์ไรซ์อัตโนมัติมีทั้งกรณีที่ทำได้และทำไม่ได้
      เมื่อไม่นานมานี้ผมเขียนโค้ดที่ต้องนับจำนวนบิตในมาสก์ของผลลัพธ์จากการคำนวณแบบเวกเตอร์ และกรณีนี้ถูกแปลงเป็น popcnt ได้ดี
      https://godbolt.org/z/zT9Whcnco

  • เพราะมีส่วนอย่าง “นี่เหมือนคำถามหลอกนะ… ก็แค่ add ไม่ใช่เหรอ?” เลยทำให้โดยทั่วไปเราอยากกำหนดเป้าหมายเป็น ตัวแทนเวกเตอร์ระดับกลาง แล้วปล่อยให้คอมไพเลอร์ตัดสินรายละเอียดเอง
    ตัวอย่างเช่น ชิป Haswell มีหน่วยประมวลผลทศนิยมลอยตัวหลายตัวต่อคอร์ และ CPU สามารถรันการคำนวณทศนิยมลอยตัวแบบไปป์ไลน์ได้พร้อมกันมากกว่าหนึ่งรายการ แต่ในบรรดานั้น คำสั่ง add ทำได้เพียงตัวเดียว
    ถ้ามีการบวกจำนวนมากที่ไม่ขึ้นกับผลลัพธ์ก่อนหน้าและสามารถหลีกเลี่ยง latency ได้ ก็สามารถส่งคำสั่ง fused multiply-add ที่มีเทอมการคูณเป็น 1 ไปพร้อมกัน เพื่อเพิ่ม throughput ของการบวกเป็นสองเท่าได้
    คำสั่งนั้นสามารถรันพร้อมกับการบวกทศนิยมลอยตัวแบบเวกเตอร์ทั่วไปได้