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

 (0x80.pl)
1 คะแนน โดย GN⁺ 2025-06-15 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เป็นหัวข้อเกี่ยวกับ อัลกอริทึมการค้นหาสตริงย่อย ที่ เป็นมิตรกับ SIMD
  • นำเสนอแนวทางเชิงเทคนิคสำหรับ การค้นหาสตริงอย่างรวดเร็ว
  • เป็นแนวทาง ปรับปรุง ประสิทธิภาพเมื่อเทียบกับวิธีเดิมโดยใช้ การประมวลผลแบบขนาน
  • ได้รับความสนใจในฐานะ เคล็ดลับด้านประสิทธิภาพที่มีประโยชน์ สำหรับนักพัฒนาและผู้เชี่ยวชาญด้าน IT
  • อัลกอริทึมนี้มีความเกี่ยวข้องกับ การเพิ่มประสิทธิภาพสำหรับฮาร์ดแวร์สมัยใหม่

ภาพรวม

  • เอกสารนี้แนะนำ อัลกอริทึมการค้นหาสตริงย่อย ที่ปรับให้เหมาะกับชุดคำสั่ง SIMD (Single Instruction, Multiple Data)
  • ในสภาพแวดล้อม IT ปัจจุบันที่ ความเร็วในการประมวลผลสตริง มีความสำคัญมากขึ้น จึงกล่าวถึง แนวทางการประมวลผลแบบขนาน เพื่อชดเชยข้อจำกัดของวิธีค้นหาแบบลำดับเดิม
  • การใช้ SIMD ทำให้สามารถเปรียบเทียบข้อมูลหลายชุดพร้อมกันได้ในครั้งเดียว จึงคาดหวังผลลัพธ์ด้านประสิทธิภาพที่ดีขึ้นอย่างมีนัยสำคัญในการ ค้นหาสตริงปริมาณมาก

เนื้อหาหลัก

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

ข้อดีสำหรับนักพัฒนาและวิศวกร

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

บทสรุป

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

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

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

 
GN⁺ 2025-06-15
ความเห็นจาก Hacker News

  • มีคำอธิบายว่าวิธีเร่งความเร็วของ ripgrep ใช้แนวทาง AVX2 (generic) ผ่าน crate regex ของ Rust ยกตัวอย่างว่าแม้จะเป็น regular expression อย่าง \w+\s+Sherlock\s+\w+ ก็ยังแยกเอา Sherlock ออกมาค้นหาแบบรวดเร็วได้ โดยดูการใช้งานจริงได้ที่นี่ นอกจากนี้ยังกล่าวว่าความต่างหลักจากอัลกอริทึมในบทความนี้คือ แทนที่จะใช้ไบต์แรก/ไบต์สุดท้ายของ needle จะใช้ฮิวริสติกที่อาศัยการกระจายพื้นหลังเพื่อเลือกค้นหาด้วย 2 ไบต์ที่พบได้น้อยกว่า พร้อมยกผลเบนช์มาร์กว่าเร็วกว่าแบบ Two-Way ธรรมดาหรือ memmem ของ GNU libc มาก และยังเน้นข้อจำกัดเชิง API ของเบนช์มาร์ก prebuilt ด้วยว่า รูทีนตระกูล memmem ไม่มีประสิทธิภาพนักเพราะต้องสร้างสถานะใหม่ซ้ำทุกครั้งเมื่อ needle ถูกกำหนดตายตัว

    • มีข้อสังเกตว่าจะรู้การกระจายพื้นหลังของไบต์ได้อย่างไร และถ้าต้องสแกน haystack เพื่อหาการกระจายนั้นทีละรอบ จะยิ่งกระทบประสิทธิภาพหรือไม่

  • มีการแชร์ประสบการณ์จากการลองทำ SIMD optimization ให้ Wasm/WASI libc แล้วได้ลงมือพัฒนาอัลกอริทึมค้นหาสตริงลักษณะนี้ โดยมองว่าถ้าความยาวของ haystack ทราบแน่ชัดและ needle มีขนาดใหญ่พอ การผสานกับ Quick Search จะมีประโยชน์ พร้อมแนบโค้ดที่เกี่ยวข้อง และลิงก์อธิบายอัลกอริทึม

  • มีการแชร์ว่าใน C# ก็มีการใช้ SIMD กับ IndexOf เช่นกัน โดยดูรายละเอียดได้ที่นี่

  • อีกความเห็นหนึ่งเล่าว่าตนเองก็เคยใช้แนวทาง SIMD เพื่อเขียนอัลกอริทึมหลายแบบสำหรับการค้นหาสตริงและการ split ด้วยตัวเอง พร้อมเปิดเผยซอร์ส conversion.cxx ของ tamgu และบอกว่าใช้อัลกอริทึมที่ต่างจากวิธีที่บทความกล่าวถึง

    • มีคนขอให้ช่วยสรุปอัลกอริทึมของเจ้าตัวแบบสั้น ๆ โดยยกตัวอย่างประกอบว่า อัลกอริทึมที่ 1 ในต้นฉบับเทียบตัวอักษรตัวแรก/ตัวสุดท้าย ส่วนอัลกอริทึมที่ 2 เปรียบเทียบ 4 ตัวอักษรแรกพร้อมกันและตรวจหลายตำแหน่งที่เป็นไปได้ในคราวเดียว

    • มีการแชร์ประสบการณ์ว่าเมื่อหลายปีก่อนเคยพยายามทำเวอร์ชันดัดแปลงสำหรับ LZ77 window search โดยใช้ generic SIMD ของ Zig และดูรายละเอียดที่เกี่ยวข้องได้ที่นี่

  • มีความเห็นว่าทำให้นึกถึงโปรเจกต์ hparse ที่ใช้อัลกอริทึม SIMD เพื่อทำ HTTP parsing แบบรวดเร็ว

  • มีการกล่าวถึงว่าอัลกอริทึม swar มี UB (undefined behavior) เพราะ cast ข้อมูลที่จัดแนวแบบ 1 ไบต์ให้เป็นหน่วย 8 ไบต์ และอาจมีปัญหาด้านประสิทธิภาพจาก unaligned load ได้ด้วย

    • อีกความเห็นบอกว่าตนมักมองโค้ดแบบนี้เป็นอัลกอริทึมในอุดมคติหรือ pseudocode เพื่อให้อ่านง่ายมากกว่า พร้อมชี้ว่าไม่ได้ใช้ mempcy และการตรวจขอบเขตก็ไม่แม่นยำ โดยมี UB ถึง 3 จุด เช่น สมมติว่า haystack ยาวเป็นจำนวนเท่าของ 8 หรือถ้า needle ว่างจะเกิด unsigned integer overflow จนนำไปสู่ out-of-bounds และจากประสบการณ์ก็มักเห็นว่าโค้ดเดโม SIMD สนใจแค่การใช้เวกเตอร์ที่น่าสนใจ ส่วนเงื่อนไขขอบเขตมักถูกละไว้

  • มีการย้ำว่าเป็นเรื่องที่รู้กันอยู่แล้วว่า strstr ของ libc ช้า แต่ musl นั้นเร็วและใช้อัลกอริทึมสมัยใหม่ ดังนั้นถ้าตั้งชื่อได้แล้วก็น่าจะเพิ่มเข้า smart shootout ได้ และก็น่าสงสัยว่าจะเป็นอย่างไรเมื่อเทียบกับอัลกอริทึม SIMD ที่ดีที่สุด

    • มีการแนะนำเบนช์มาร์กอ้างอิงที่เปรียบเทียบ Two-Way ของ musl กับอัลกอริทึม libc ที่ผู้แสดงความเห็นแชร์ซึ่งปรับแต่งด้วย SIMD โดยอิงวิธีเบนช์มาร์กจากโค้ดนี้ และดูส่วนปรับปรุงด้วย SIMD ได้จากตารางนี้ พร้อมประเมินอย่างตรงไปตรงมาว่าไม่ถึงขั้นยอดเยี่ยมแต่ก็ปรับปรุงได้ค่อนข้างดี ทั้งยังกล่าวว่า musl เน้นกับสตริงความยาวคงที่ (memmem) ส่วนตนเองในสภาพแวดล้อม Wasm สามารถทดลองทำ optimization ได้หลากหลายกว่ากับสตริงความยาวไม่ทราบแน่ (strstr) และสตริงที่จบด้วย NUL ก็ทำให้อัลกอริทึมดี ๆ หลายแบบใช้งานลำบาก

    • มีการบอกว่าอยากให้ smart มีอัลกอริทึม SIMD มากกว่านี้ และถ้ามีเวลาก็อยากลองทดสอบเอง

  • มีคำถามว่าในการเปรียบเทียบ SIMD สำหรับการค้นหาสตริงนั้น เวอร์ชันปี 2018 ตกหล่นไปหรือไม่

  • มีคำถามว่าสำหรับขนาดสตริงต่าง ๆ กัน จุดคุ้มทุนที่ SIMD เริ่มมีประสิทธิภาพจริงอยู่ตรงไหน โดยเน้นว่าปกติแล้วกับสตริงสั้น ๆ overhead จากการตั้งค่า SIMD เช่น การจัดแนวหรือการคำนวณความยาว อาจทำให้ช้ากว่าการค้นหาแบบอิงไบต์ธรรมดา และผลก็อาจต่างกันมากตามสถาปัตยกรรมฮาร์ดแวร์

    • อีกความเห็นบอกว่าจากประสบการณ์ของตนกลับตรงกันข้าม เพราะอัลกอริทึมลักษณะนี้แทบไม่ต้องมีการตั้งค่าที่สิ้นเปลืองและเกือบเป็น brute force ดังนั้นกับ needle ที่ยาวและซ้ำ ๆ ความซับซ้อนเชิงเวลาจะย่ำแย่ ขณะที่อัลกอริทึมค้นหาสตริงขั้นสูงที่ป้องกันปัญหา quadratic หรือทำงานแบบ sublinear จำเป็นต้องมีขั้นตอนเตรียมการที่มีต้นทุนสูงกว่าเพราะต้องวิเคราะห์โครงสร้างของ needle ลึกขึ้น

  • มีคนบอกว่าอยากให้ใน Python สามารถใช้ SIMD ได้โดยตรงโดยไม่ต้องเรียกภาษาอื่น

    • มีการอ้างถึงบล็อกของ Austin และบทความรวมของเขา (story on vowels detection ลิงก์) แล้วถามต่อว่า "ใช้ SIMD โดยตรงโดยไม่ต้องเรียกภาษาอื่น" หมายถึงอะไรอย่างเจาะจง พร้อมแซวว่าจริง ๆ แล้ว Assembly ก็เป็น “อีกภาษา” เหมือนกัน จากนั้นอธิบายว่าระบบนิเวศด้าน Python กับ SIMD มีตัวเลือกกว้างมาก ตั้งแต่ PeachPy (เขียน x86 assembly จาก Python), Mojo (ภาษาใหม่สไตล์ Python) ไปจนถึงไลบรารี SIMD ที่มี CPython binding แบบบาง ๆ พร้อมถามว่าต้องการแนวทางแบบไหน และถ้าจัดการข้อมูล ASCII ก็แนะนำฟังก์ชัน find_first_of ของ StringZilla ด้วย (โค้ด)

    • มีคนตั้งคำถามว่าทำไมต้องทำใน Python โดยตรงด้วย ถ้ากำลังกังวลเรื่องขีดจำกัดด้านประสิทธิภาพ การเปลี่ยนภาษาเพียงอย่างเดียวก็อาจเพิ่มประสิทธิภาพได้มากกว่า 20~50 เท่า