อัลกอริทึมค้นหาสตริงย่อยที่เหมาะกับ SIMD (2018)

 (0x80.pl)
1 คะแนน โดย GN⁺ 2025-06-15 | ยังไม่มีความคิดเห็น | แชร์ทาง WhatsApp
  • API อย่าง strstr และ std::string::find ตั้งอยู่บนสมมติฐานของการค้นหาสตริงย่อยแบบ ครั้งเดียว แต่บน CPU สมัยใหม่ ต้นทุนการเปรียบเทียบสตริงสั้นและเวกเตอร์ต่ำ ทำให้แนวทางแบบ SIMD อาจได้เปรียบ
  • แนวคิดหลักคือเปลี่ยนเงื่อนไขแฮชแบบอ่อนของ Karp-Rabin ให้เป็น เพรดิเคตเวกเตอร์ แล้วทำการเปรียบเทียบสตริงย่อยแบบถูกต้องเฉพาะตำแหน่งที่เป็นตัวเลือกเท่านั้น
  • อัลกอริทึม SIMD แบบทั่วไปจะเปรียบเทียบ อักขระแรกและอักขระสุดท้าย ของ needle แบบขนานเพื่อลดจำนวนตัวเลือก และตรวจสอบเฉพาะตำแหน่งที่มีโอกาสตรงกันด้วย memcmp
  • ยังเปรียบเทียบกับวิธี SSE4.1 MPSADBW และ SSE4.2 PCMPESTRM ด้วย แต่ผลการวัดพบว่า SIMD แบบทั่วไปเร็วกว่าอย่างเสถียรกว่า และ PCMPESTRM มักช้ากว่า MPSADBW ด้วยซ้ำ
  • SIMD แบบทั่วไปเร็วกว่า C strstr ในทุกแพลตฟอร์ม แต่สามารถอ่านนอกขอบเขตสตริงอินพุตได้จึง ไม่ปลอดภัย และเงื่อนไขการเปรียบเทียบก็ไม่เหมือนกันทั้งหมด เพราะรับข้อมูลความยาวไว้ล่วงหน้า

สมมติฐานด้านต้นทุนที่เปลี่ยนไปในการค้นหาสตริง

  • API อย่าง strstr ของ C, std::string::find ของ C++ และ pos, index ของสตริงใน Python ถูกออกแบบมาสำหรับการค้นหา แบบครั้งเดียว เพื่อหาสตริงย่อยในสตริงที่กำหนด
  • อัลกอริทึมเดิมแบ่งได้คร่าว ๆ เป็นสองกลุ่ม
    • วิธีที่อิง deterministic finite automata เช่น Knuth-Morris-Pratt และ Boyer Moore
    • วิธีที่อิงการเปรียบเทียบอย่างง่าย เช่น Karp-Rabin
  • อัลกอริทึมมาตรฐานตั้งสมมติฐานว่าการเปรียบเทียบอักขระทีละคู่ การค้นตารางช่วย และการ branch ตามเงื่อนไขมีราคาถูก ส่วนการเปรียบเทียบสตริงย่อยสองช่วงมีราคาแพง
  • บน CPU เดสก์ท็อปสมัยใหม่ สมมติฐานนี้อาจไม่ตรงนัก
    • บน CPU 64 บิต ต้นทุนการเปรียบเทียบ 1, 2, 4, 8 ไบต์ไม่ต่างกัน
    • หากรองรับคำสั่ง SIMD การเปรียบเทียบเวกเตอร์ขนาด 16, 32, 64 ไบต์ก็อาจถูกพอ ๆ กับการเปรียบเทียบไบต์เดียว
    • การค้นตารางมีต้นทุนการเข้าถึงหน่วยความจำระดับไปกลับของ L1 cache และการอ่านทีละอักขระก็มีต้นทุนใกล้เคียงกัน
    • branch ที่ทำนายผิดอาจมี penalty ประมาณ 10~20 cycles
    • สาย dependency สั้น ๆ ที่เรียงจากการอ่านอักขระ การเปรียบเทียบ ไปจนถึง branch ตามเงื่อนไข ทำให้ใช้ประโยชน์จาก out-of-order execution ของ CPU ได้ยาก

แนวทาง: ใช้เพรดิเคตเวกเตอร์แทนแฮชแบบอ่อน

  • Karp-Rabin จะทำการเปรียบเทียบแบบถูกต้องเฉพาะเมื่อ แฮชแบบอ่อน ของสตริงย่อยที่ต้องการค้นหาตรงกับแฮชของช่วงสตริงปัจจุบัน
  • แนวทาง SIMD แทนที่เงื่อนไขแฮชนี้ด้วย เพรดิเคตเวกเตอร์
    • เพรดิเคตถูกคำนวณแบบขนาน
    • ทำการเปรียบเทียบสตริงย่อยแบบถูกต้องเฉพาะแต่ละตำแหน่งที่เป็นจริงในเวกเตอร์เพรดิเคตเท่านั้น
  • การทำ specialization ตามความยาว ก็ใช้เพื่อปรับปรุงประสิทธิภาพเช่นกัน
    • implementation ทั่วไปจะเรียกฟังก์ชันอย่าง memcmp เพื่อเปรียบเทียบสตริงย่อย
    • หากรู้ความยาวของสตริงย่อยที่จะค้นหา ก็สามารถแทนที่การเรียกฟังก์ชันด้วยคำสั่ง CPU ไม่กี่คำสั่ง หรือในบางกรณีเพียงคำสั่งเดียว ให้เหมาะกับความยาวนั้น ๆ ได้
    • วิธีนี้ช่วยลดต้นทุนการเรียกฟังก์ชันและต้นทุนภายใน memcmp

อัลกอริทึม 1: SIMD แบบทั่วไป

  • อัลกอริทึม SIMD แบบทั่วไปสามารถใช้ได้กับชุดคำสั่ง SIMD โดยรวมและแนวทาง SWAR
  • เพรดิเคตพื้นฐานคือการตรวจสอบว่า อักขระแรก และ อักขระสุดท้าย ของ needle ตรงกันทั้งคู่หรือไม่
    • ใส่อักขระแรกลงในรีจิสเตอร์ F
    • ใส่อักขระสุดท้ายลงในรีจิสเตอร์ L
    • ในแต่ละรอบ อ่าน chunk A จาก offset ปัจจุบัน i ของ haystack และอ่าน chunk B จาก i + k - 1
    • คำนวณ F == A และ B == L แล้วรวมผลทั้งสองเพื่อสร้าง mask ของตำแหน่งตัวเลือก
    • ทำการเปรียบเทียบสตริงย่อยแบบถูกต้องเฉพาะตำแหน่งที่ mask เป็นจริงเท่านั้น
  • ในตัวอย่างการหา "cat" ใน "a_cat_tries" ตำแหน่งที่ทั้งอักขระแรก c และอักขระสุดท้าย t ตรงกันมีเพียง index 2 ดังนั้นจึงทำการเปรียบเทียบแบบถูกต้องเพียงครั้งเดียว
  • การเลือกอักขระแรกและอักขระสุดท้ายไม่ได้ดีเสมอไป
    • หากสตริงอินพุตส่วนใหญ่เป็น 'A' และ needle คือ "AjohndoeA" ก็อาจเกิดตัวเลือกจำนวนมาก
    • implementation สามารถเลือกอักขระที่อยู่ไกลที่สุดซึ่งต่างจากอักขระแรกแทนอักขระสุดท้ายได้
    • หากอักขระทั้งหมดใน needle เหมือนกัน ก็สามารถใช้ขั้นตอนพิเศษสำหรับ pattern อย่าง "AAAAA" ได้

ความแตกต่างระหว่าง implementation

  • implementation ของ SSE และ AVX2 มีโครงสร้างแทบเหมือนกัน และใช้จำนวนคำสั่งขั้นต่ำ
    • เนื่องจากรู้อยู่แล้วว่าอักขระแรกและอักขระสุดท้ายตรงกัน จึงไม่จำเป็นต้องเปรียบเทียบอักขระเหล่านี้ซ้ำใน memcmp
  • แนวทาง SWAR ใช้ข้อเท็จจริงที่ว่า หากผล XOR เป็น 0 แสดงว่าไบต์เท่ากัน
    • แทนที่จะ AND ผลลัพธ์ย่อยเหมือน SSE/AVX2 จะใช้ OR
    • ขั้นตอนการหาตำแหน่งไบต์ 0 ต้องใช้ งานมากกว่า
    • implementation C++ สำหรับเวกเตอร์ 64 บิตจะคำนวณ byte mask ที่ถูกต้อง
  • AVX512F ไม่มีการดำเนินการระดับไบต์ และรายการเวกเตอร์ที่เล็กที่สุดเป็น word 32 บิต จึงต้องใช้ เทคนิค SWAR
    • คำนวณ XOR สองครั้งและ OR ด้วยคำสั่ง AVX512F
    • หา element ขนาด 32 บิตที่มีไบต์ 0 อยู่
    • ตรวจสอบสตริงย่อยตัวเลือก 4 รายการต่อ element ขนาด 32 บิตนั้น
  • implementation ARM Neon 32 บิตใช้รีจิสเตอร์ SIMD ขนาด 128 บิต
    • การไปกลับระยะยาวจากหน่วย Neon กลับมาที่ CPU กลายเป็นคอขวด
    • จึงบันทึกผลการเปรียบเทียบลงหน่วยความจำเป็น word ขนาด 64 บิตแล้วประมวลผล
    • การ unroll inner loop 2 ลูปทำให้เร็วขึ้นประมาณ 1.2 เท่า
  • implementation AArch64 แทบเหมือนขั้นตอน ARM Neon แต่การอ่าน lane ของรีจิสเตอร์ SIMD โดยตรงทำได้เร็ว

อัลกอริทึม 2: SSE4.1 MPSADBW

  • MPSADBW ของ SSE4.1 และ AVX2 คำนวณ Manhattan distance ระหว่างเวกเตอร์ย่อย 4 ไบต์ของรีจิสเตอร์หนึ่งกับเวกเตอร์ย่อย 4 ไบต์ต่อเนื่อง 8 ชุดของอีกรีจิสเตอร์หนึ่ง
  • หากเวกเตอร์ย่อยสองชุดเหมือนกัน ระยะ L1 จะเป็น 0 จึงใช้สิ่งนี้ในการค้นหาตำแหน่งตัวเลือกได้
    • วิธีนี้ใช้ ความเท่ากันของ 4 อักขระแรก เป็นเพรดิเคต
  • เพราะเปรียบเทียบ 4 อักขระแรก จึงดูเหมือนแข็งแรงกว่าการเปรียบเทียบอักขระแรกและสุดท้าย แต่ในกรณีเลวร้ายที่สุดก็ยังเลี่ยงความซับซ้อนกำลังสองไม่ได้
    • หาก haystack เต็มไปด้วย "a" และ needle คือ "aaaabcde" เพรดิเคตจะเป็นจริงในทุกอักขระอินพุต
  • วิธี MPSADBW มีข้อจำกัดหลายอย่าง
    • โดยพื้นฐานไม่เหมาะกับสตริงย่อยที่ยาวน้อยกว่า 4
    • รองรับความยาว 3 ได้ แต่ต้องมีโค้ดเพิ่มเติม
    • SSE MPSADBW ประมวลผลได้ครั้งละ 8 ไบต์เท่านั้น
    • AVX2 MPSADBW ทำงานเป็นหน่วย lane 128 บิต ไม่ใช่ทั้ง 256 บิต จึงต้องมีโค้ดโหลดเพิ่มเติม
    • latency ของคำสั่งสูงที่ 5~7 cycles แล้วแต่ CPU แต่ throughput อยู่ที่ 1~2 cycles จึงสามารถซ่อน latency ได้ด้วยการ unroll loop
  • AVX512F ไม่มี MPSADBW แต่เพราะรองรับ element ขนาด 32 บิตแบบ native จึงสามารถเลียนแบบเพรดิเคตความเท่ากันของ prefix 4 ไบต์ได้
    • ในแต่ละรอบ สร้างเวกเตอร์ AVX512 4 ชุดที่บรรจุ prefix ขนาด 4 ไบต์ที่เป็นไปได้
    • การสร้างแต่ละเวกเตอร์ต้องใช้ shift 2 ครั้งและ OR 1 ครั้ง
    • ลูปเปรียบเทียบซับซ้อนขึ้น และต้องใช้ข้อมูล 4 ไบต์ถัดจากเวกเตอร์เพื่อเติม element สุดท้าย

อัลกอริทึม 3: SSE4.2 PCMPESTRM

  • SSE4.2 นำชุดคำสั่ง STNI เข้ามาโดยมุ่งเป็น building block สำหรับการดำเนินการกับสตริง
  • ต่อมา Intel แทบหยุดพัฒนา STNI ในโปรเซสเซอร์รุ่นหลัง และไม่ได้เพิ่มเวอร์ชัน AVX2 ด้วย อีกทั้งคำสั่งเหล่านี้ช้ามาก
    • latency 11 cycles ถูกประเมินว่ายอมรับได้ยาก
  • คำสั่ง PCMPxSTRx มี 4 แบบ ขึ้นกับวิธีกำหนดความยาวสตริงและวิธีเก็บผลลัพธ์
    • ความยาวอาจระบุอย่างชัดเจน หรือถือว่าไบต์ 0 ตัวแรกเป็นจุดสิ้นสุดเหมือนสตริง C แบบดั้งเดิม
    • ผลลัพธ์สามารถเก็บเป็น bit/byte mask หรือเป็นหมายเลขบิตที่ตั้งค่าไว้ตัวแรก/ตัวสุดท้ายของ mask
  • ที่นี่ใช้วิธีเปรียบเทียบแบบ range ordered
    • แม้ชื่อจะเป็นเช่นนั้น แต่จะค้นหาสตริงย่อยหรือ prefix ของมันในกรณีที่เกินความกว้างของรีจิสเตอร์
    • ในตัวอย่าง หากหา "ABCD" ใน "ABCD_ABC_ABCD_AB" suffix "AB" ก็อาจถูกถือว่าตรงกันด้วย
    • ดังนั้นสิ่งที่สมมติได้อย่างปลอดภัยมีเพียง อักขระแรกตรงกัน เท่านั้น ส่วนที่เหลือต้องตรวจสอบด้วย memcmp

สภาพแวดล้อมการวัดประสิทธิภาพ

  • วัดประสิทธิภาพของ implementation SIMD หลายแบบ และรวม runtime specialization สำหรับสตริงย่อยสั้น ๆ ด้วย
  • ใช้ C strstr เป็นตัวเปรียบเทียบ แต่ตัด std::string::find ออกจากตาราง x64 เพราะบั๊กด้านประสิทธิภาพใน GNU libc
  • การทดสอบรันแต่ละโปรแกรมสามครั้ง
  • สภาพแวดล้อมทดสอบ x64
    • Westmere i5 M540, GCC 6.2.0
    • Bulldozer FX-8150, GCC 4.8.4
    • Haswell i7 4470, GCC 5.4.1
    • Skylake i7 6700, GCC 5.4.1
    • Knights Landing 7210, GCC 5.3.0
  • สภาพแวดล้อมทดสอบ ARM
    • ARMv7 Raspberry Pi 3, โค้ด 32 บิต, GCC 4.9.2
    • ARMv8 ARM Cortex A57 / AMD Opteron A1100, โค้ด 64 บิต, Clang 3.8.0

ผลลัพธ์ x64

  • implementation SIMD ทั่วไปให้การเพิ่มความเร็วสูงสุดเมื่อเทียบกับ strstr บน x64
    • บน Westmere, SSE2 generic ใช้เวลา 0.74589 วินาที, strstr ใช้ 0.82246 วินาที
    • บน Haswell, AVX2 generic ใช้เวลา 0.38653 วินาที, strstr ใช้ 0.52786 วินาที
    • บน Skylake, AVX2 generic ใช้เวลา 0.36309 วินาที, strstr ใช้ 0.66148 วินาที
    • บน KNL, AVX512F generic ใช้เวลา 1.14057 วินาที, strstr ใช้ 4.94606 วินาที
  • การเพิ่มความเร็วสูงสุดคือ Westmere 1.10 เท่า, Haswell 1.37 เท่า, Skylake 1.82 เท่า, KNL 4.33 เท่า
  • ประสิทธิภาพ strstr ของ Bulldozer แย่มากที่ 9.37792 วินาที จึงใช้เป็นเกณฑ์อ้างอิงได้ยาก
  • วิธี MPSADBW โดยรวมไม่ดีนัก ยกเว้น Skylake และแย่เป็นพิเศษบน KNL
  • วิธี PCMPESTRM ให้ผลลัพธ์ช้ากว่า MPSADBW

ผลลัพธ์ ARM

  • บน ARMv7, std::strstr ใช้เวลา 7.30405 วินาที และ std::string::find ใช้ 4.17131 วินาที
  • บน ARMv7, ARM Neon 32-bit generic ใช้เวลา 1.29861 วินาที เร็วกว่า std::string::find ได้สูงสุด 3.1 เท่า
  • บน ARMv8, std::strstr ใช้เวลา 3.37546 วินาที และ std::string::find ใช้ 1.81368 วินาที
  • บน ARMv8, AArch64 64-bit generic ใช้เวลา 0.27897 วินาที เร็วกว่า std::string::find ได้สูงสุด 6.5 เท่า
  • บน ARMv8, SWAR 64-bit generic ใช้เวลา 0.46269 วินาที ซึ่งให้ประสิทธิภาพใกล้เคียงกับขั้นตอน SIMD 32 บิต

สรุปและข้อจำกัด

  • อัลกอริทึม SIMD ทั่วไปเร็วกว่า C strstr ในทุกแพลตฟอร์ม
  • implementation ควรเลือกเวอร์ชัน SIMD สูงสุดที่ใช้ได้บน CPU นั้น ๆ
  • MPSADBW มีประสิทธิภาพไม่ดี ยกเว้นกรณี Skylake และแย่มากบน Knights Landing
  • PCMPESTRM มีประสิทธิภาพต่ำกว่า MPSADBW
  • ประสิทธิภาพของ ARM Neon ดี รวมถึง implementation แบบ SWAR ด้วย
    • เวอร์ชัน SWAR เร็วกว่า string::find 1.7 เท่า
    • เวอร์ชัน SIMD เร็วกว่า string::find 3.1 เท่า
  • การเปรียบเทียบกับ strstr อาจไม่ยุติธรรมอย่างสมบูรณ์
    • strstr จัดการสตริงที่ไม่รู้ความยาว
    • implementation เหล่านี้รับความยาวเป็นอาร์กิวเมนต์และใช้ประโยชน์จากมัน
  • implementation ไม่ปลอดภัย
    • อาจอ่านข้อมูลนอกสตริงอินพุตได้
    • หากสตริงอยู่ก่อนหน้าหน่วยความจำที่ไม่ได้ map พอดี อาจเกิด access violation ได้
    • address sanitizer ก็อาจรายงานปัญหาได้
    • การทำให้ปลอดภัยเป็นไปได้ แต่ไม่ใช่เป้าหมาย
  • implementation และโปรแกรมทดสอบทั้งหมดอยู่ที่ GitHub

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

ยังไม่มีความคิดเห็น

ยังไม่มีความคิดเห็น