ฟังก์ชัน `tolower()` ที่ใช้ AVX-512

 (dotat.at)
1 คะแนน โดย GN⁺ 2024-07-30 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

  • เมื่อหลายปีก่อน ผู้เขียนเคยเขียนบทความเกี่ยวกับวิธีทำให้ tolower() ทำงานได้เร็วขึ้นด้วยเทคนิค SWAR ไม่กี่วันก่อน ได้สนใจบทความของ Olivier Giniaux ที่อธิบายวิธีเพิ่มประสิทธิภาพการประมวลผลสตริงสั้นด้วยคำสั่ง SIMD วิธีนี้ถูกใช้ในฟังก์ชันแฮชความเร็วสูงที่เขียนด้วย Rust

  • คำสั่ง SIMD สามารถจัดการสตริงสั้นได้ง่าย แต่สิ่งที่ทำให้รู้สึกติดขัดมาตลอดคือการย้ายข้อมูลระหว่างหน่วยความจำกับเวกเตอร์รีจิสเตอร์ บทความของ Olivier นำเสนอวิธีที่น่าสนใจในการแก้ปัญหานี้

สัญญาณแห่งความหวัง

  • ชุดคำสั่ง SIMD บางชุดมีความสามารถโหลดและจัดเก็บแบบ masked ที่มีประโยชน์สำหรับการประมวลผลสตริง โดยทำงานในระดับไบต์

    • ARM SVE: ใช้ได้บนคอร์ ARM Neoverse รุ่นใหญ่รุ่นใหม่ เช่น Amazon Graviton แต่ใช้ไม่ได้บน Apple Silicon
    • AVX-512-BW: ใช้ได้บนโปรเซสเซอร์ AMD Zen รุ่นใหม่ AVX-512 เป็นชุดส่วนขยายที่ซับซ้อน และบน Intel การรองรับค่อนข้างไม่แน่นอน

  • ผู้เขียนมีเครื่อง AMD Zen 4 อยู่ จึงตัดสินใจลองใช้ AVX-512-BW

tolower64()

  • ผู้เขียนใช้คู่มือ intrinsics ของ Intel เพื่อเขียนฟังก์ชัน tolower() พื้นฐานที่ประมวลผลได้ครั้งละ 64 ไบต์
    • ใช้ * เป็น wildcard เพื่อค้นหา mm512*epi8 และหาฟังก์ชัน AVX-512 ระดับไบต์
    • เติมหลายรีจิสเตอร์ด้วยไบต์ที่มีประโยชน์ 64 ตัว
    • กำหนดค่าตัวเลขที่จำเป็นสำหรับแปลงตัวพิมพ์ใหญ่เป็นตัวพิมพ์เล็ก
    • เปรียบเทียบอักขระขาเข้ากับ A และ Z เพื่อตรวจว่าเป็นตัวพิมพ์ใหญ่หรือไม่
    • ใช้ mask เพื่อแปลงเป็นตัวพิมพ์เล็กเมื่อเป็นตัวพิมพ์ใหญ่

การโหลดและจัดเก็บแบบจำนวนมาก

  • ต้องห่อ kernel tolower64() ด้วยฟังก์ชันที่ใช้งานสะดวกขึ้น เช่น ฟังก์ชันที่คัดลอกสตริงพร้อมแปลงเป็นตัวพิมพ์เล็กไปด้วย
    • สำหรับสตริงยาว จะใช้คำสั่งโหลดและจัดเก็บเวกเตอร์แบบไม่ต้องจัดแนว

การโหลดและจัดเก็บแบบ masked

  • สำหรับสตริงสั้นและช่วงท้ายของสตริงยาว จะใช้การโหลดและจัดเก็บแบบไม่ต้องจัดแนวที่มี mask
    • mask จะตั้งค่าบิต len ตัวแรกไว้
    • การโหลดและจัดเก็บจะคล้ายกับเวอร์ชันความกว้างเต็มที่เพิ่ม mask เข้าไป

การทำเบนช์มาร์ก

  • มีการทำเบนช์มาร์กเปรียบเทียบประสิทธิภาพของฟังก์ชันคล้ายกันหลายตัว

    • คอมไพล์ด้วย Clang 16 และรันบน AMD Ryzen 9 7950X
    • แต่ละฟังก์ชันคอมไพล์แยกกันเพื่อหลีกเลี่ยงผลรบกวนจาก inlining และการย้ายโค้ด

  • ผลลัพธ์:

    • tolower64 เร็วที่สุดในบรรดาฟังก์ชันทั้งหมดที่ทดสอบ
    • copybytes64 ใช้ AVX-512 ในลักษณะคล้าย tolower64 แต่ไม่ได้เร็วกว่าอย่างมาก
    • copybytes1 ทำ memcpy ทีละไบต์ และแสดงให้เห็นว่า auto-vectorization ของ Clang 11 ค่อนข้างไม่ดี
    • tolower() มาตรฐานช้าที่สุด
    • tolower1 คือ tolower() แบบทีละไบต์ที่คอมไพล์ด้วย Clang 16 ซึ่ง auto-vectorization ดีขึ้น แต่ก็ยังช้าอยู่
    • tolower8 คือ SWAR tolower() จากบล็อกโพสต์ก่อนหน้า โดย Clang พยายามทำ auto-vectorization แต่ผลลัพธ์ไม่ดี
    • memcpy ช่วงแรกเร็ว แต่หลังจากนั้นความเร็วลดลงเหลือครึ่งหนึ่งของ copybytes64

บทสรุป

  • AVX-512-BW มีประโยชน์มาก โดยเฉพาะเมื่อต้องจัดการสตริงสั้น

  • บน Zen 4 มันเร็วมาก และ built-in functions ก็ใช้งานง่าย

  • ประสิทธิภาพของ AVX-512-BW ลื่นไหลมาก

  • ผู้เขียนไม่มีเครื่องที่รองรับ ARM SVE จึงยังตรวจสอบเชิงลึกไม่ได้ แต่สงสัยว่า SVE จะทำงานกับสตริงสั้นได้ดีแค่ไหน

  • ผู้เขียนหวังว่าการขยายชุดคำสั่งเหล่านี้จะถูกใช้อย่างแพร่หลายมากขึ้น เพราะจะช่วยเพิ่มประสิทธิภาพการประมวลผลสตริงได้มาก

  • โค้ดของบล็อกโพสต์นี้สามารถดูได้บนเว็บไซต์ของผู้เขียน

สรุปโดย GN⁺

  • บทความนี้อธิบายวิธีประมวลผลสตริงสั้นอย่างมีประสิทธิภาพด้วยคำสั่ง SIMD
  • แสดงให้เห็นว่าชุดคำสั่ง AVX-512-BW และ ARM SVE มีประโยชน์ต่อการประมวลผลสตริง
  • ผลการทำเบนช์มาร์กชี้ว่า AVX-512-BW ให้ประสิทธิภาพโดดเด่น โดยเฉพาะกับสตริงสั้น
  • บทความนี้น่าจะเป็นประโยชน์กับนักพัฒนาที่สนใจการเพิ่มประสิทธิภาพ

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

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

 
GN⁺ 2024-07-30
ความคิดเห็นจาก Hacker News

  • ในโมเดลหน่วยความจำของ Rust และ LLVM กลเม็ด "unsafe read beyond of death" ถือเป็นพฤติกรรมที่ไม่ถูกนิยาม

    • คอมไพเลอร์สามารถสมมติได้ว่าพฤติกรรมลักษณะนี้จะไม่เกิดขึ้นเพื่อใช้ในการเพิ่มประสิทธิภาพ
    • หากต้องการหลีกเลี่ยง ต้องใช้อินไลน์แอสเซมบลี

  • ทำให้อยากรู้เกี่ยวกับการใช้งาน AVX512 ของ AMD และการแข่งขันกับ AVX10 ของ Intel

    • AVX10 มีไว้เพื่อแก้ปัญหา P core กับ E core ของ Intel
    • AMD ใช้ความกว้างเต็มของ Zen5 หรือใช้ 256 บิตแบบ double pump บน Zen4 และ Zen5 mobile ตามความเหมาะสม
    • การเพิ่มประสิทธิภาพขนาดใหญ่เกิดขึ้นบนคอร์ Zen4

  • การปรับแต่ง SWAR มีประโยชน์เฉพาะกับสตริงที่จัดแนวกับแอดเดรส 8 ไบต์เท่านั้น

    • หากนำไปใช้กับสตริงที่ไม่จัดแนว จะช้ากว่าอัลกอริทึมเดิม
    • หากแยกอัลกอริทึมออกเป็นสามส่วน จะต้องใช้คำสั่งมากขึ้น

  • การเพิ่ม mask ดูเรียบร้อยดี

    • อยากให้มีวิธีจัดการ mask register ของ AVX512 ได้โดยตรงในฟีเจอร์ built-in ของ .NET

  • หากใช้ Clang จะได้ผลลัพธ์ที่ดีกว่า

    • ให้การเลือกคำสั่งที่ดีกว่าและผลลัพธ์ที่คลี่ออกมาอย่างเหมาะสม

  • ลูปหลักสำหรับสตริงความยาวสั้นมีคำสั่งน้อยกว่าอยู่หนึ่งคำสั่ง

    • การประมวลผลสตริงสั้นให้รวดเร็วเป็นเรื่องสำคัญ

  • เคยเขียน implementation คล้ายกันใน C# สำหรับแปลงตัวพิมพ์ใหญ่/เล็กของ ASCII เป็น UTF-8

    • เนื่องจากสตริงสั้นครองสัดส่วนส่วนใหญ่ของโค้ดเบส การประมวลผลให้เร็วจึงสำคัญ

  • มีตัวอย่างการใช้ SIMD เพื่อแปลงข้อความให้เป็น uwu โดยใช้ AVX512

  • ถ้าคำนึงถึงการแปลงอักขระ Unicode ด้วยจะยิ่งน่าประทับใจกว่านี้

    • โปรแกรมเมอร์ส่วนใหญ่มักสนใจแค่ ASCII แต่โลกนี้ยังมีอีกมากนอกเหนือจากชุดอักขระมาตรฐาน

  • เคยมีประสบการณ์เพิ่มขอบสีดำรอบภาพเพื่อหลีกเลี่ยงปัญหา SIMD ของบัฟเฟอร์

    • บางครั้งก็ไม่สามารถควบคุมอินพุตได้ทั้งหมด