Krep - เครื่องมือค้นหาสตริงที่เร็วกว่า grep 5 เท่า

• เครื่องมือค้นหาสตริงความเร็วสูงพิเศษที่เขียนด้วย C สำหรับแอปพลิเคชันที่ต้องการประสิทธิภาพสูง
• เลือกอัลกอริทึมที่เหมาะสมที่สุดแบบไดนามิกตามลักษณะของแพตเทิร์นและฮาร์ดแวร์
• ใช้ประโยชน์จากฮาร์ดแวร์อย่าง SSE4.2/AVX2 เพื่อมอบ throughput สูงสุด
• แบ่งไฟล์เป็นชังก์เพื่อรองรับข้อมูลขนาดใหญ่ และประมวลผลแบบขนานด้วยมัลติเธรด
• ใช้อัลกอริทึมการค้นหาที่เหมาะสมที่สุดตามแพตเทิร์น
  • Boyer-Moore-Horspool: เหมาะกับการจับคู่แพตเทิร์นทั่วไป
  • อัลกอริทึม Knuth-Morris-Pratt (KMP): ปรับให้เหมาะกับแพตเทิร์นสั้น
  • Rabin-Karp: มีประสิทธิภาพกับแพตเทิร์นยาว
  • การเร่งความเร็วด้วย SIMD: เพิ่มประสิทธิภาพบนฮาร์ดแวร์ที่รองรับ SSE4.2 และ AVX2
• ใช้memory-mapped file I/O เพื่อลด system call ให้เหลือน้อยที่สุดและเพิ่ม throughput สูงสุด
• ตัวเลือกการค้นหาที่ยืดหยุ่น
  • ค้นหาแบบแยกหรือไม่แยกตัวพิมพ์เล็ก-ใหญ่
  • ค้นหาในสตริงโดยตรงได้ นอกเหนือจากการค้นหาในไฟล์
  • มีโหมดสำหรับแสดงเฉพาะจำนวนครั้งที่ตรงกัน

วิธีใช้งาน

krep [OPTIONS] PATTERN [FILE]  

• ค้นหา “error” ในไฟล์ล็อก: krep "error" system.log
• ค้นหาโดยไม่แยกตัวพิมพ์เล็ก-ใหญ่ พร้อมใช้ 8 เธรด: krep -i -t 8 "ERROR" large_logfile.log
• แสดงจำนวนครั้งที่ตรงกัน (ไม่แสดงบรรทัดที่แมตช์): krep -c "TODO" *.c
• ค้นหาโดยตรงจากสตริงแทนไฟล์: krep -s "Hello" "Hello world"

ตัวเลือกบรรทัดคำสั่ง

• -i : ค้นหาแบบไม่แยกตัวพิมพ์เล็ก-ใหญ่
• -c : แสดงเฉพาะจำนวนครั้งที่ตรงกันโดยไม่พิมพ์บรรทัดที่แมตช์
• -t NUM : ใช้เธรดจำนวน NUM (ค่าเริ่มต้น: 4)
• -s STRING : ค้นหาในสตริงแทนไฟล์
• -v : แสดงข้อมูลเวอร์ชัน
• -h : แสดงวิธีใช้

เบนช์มาร์ก

• ประสิทธิภาพของ krep โดดเด่นมากเมื่อเทียบกับเครื่องมือค้นหาสตริงทั่วไป
  • krep ใช้เวลา 0.78 วินาที ในการค้นหาแพตเทิร์นทั่วไปในไฟล์ข้อความขนาด 1GB คิดเป็นความเร็ว 1,282MB ต่อวินาที
  • grep ใช้เวลา 2.95 วินาที สำหรับงานเดียวกัน และทำความเร็วได้ 339MB ต่อวินาที
  • ripgrep ใช้เวลา 1.48 วินาที และทำความเร็วได้ 676MB ต่อวินาที
• → krep เร็วกว่า grep ประมาณ 3.8 เท่า และเร็วกว่า ripgrep ประมาณ 1.9 เท่า (ประสิทธิภาพอาจแตกต่างกันตามฮาร์ดแวร์และลักษณะของไฟล์)

ที่มาของชื่อ

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

[clickin]

ถ้าตัดการรองรับ regex ออกไปแล้ว แต่ยังเร็วกว่า ripgrep ได้แค่ 2 เท่า ก็ดูจะมีประโยชน์ใช้งานค่อนข้างน้อยนะครับ
ส่วนผมคงจะใช้ ripgrep ที่รองรับ regex ต่อไปเหมือนเดิมครับ

[GN⁺]

ความคิดเห็นจาก Hacker News

• ฟีเจอร์ของ CPU (เช่น AVX2) ควรถูกตรวจจับตอนรันไทม์

  • ifdef ตรวจจับได้แค่ว่าคอมไพเลอร์รองรับหรือไม่ในช่วงบิลด์ไทม์
  • โปรแกรมจะถูกคอมไพล์ได้ก็ต่อเมื่อคอมไพเลอร์รองรับ AVX2 เท่านั้น
  • ต้องตรวจสอบตอนรันไทม์ว่า CPU รองรับ AVX2 หรือไม่
  • ในโปรเจ็กต์มีส่วนที่ระบุว่า "ตรวจจับในช่วงเวลาคอนฟิกผ่านแฟลก CPUID และการทดสอบรันคำสั่งจริง"
  • สามารถใช้คำสั่ง SSE4.2 และ AVX2 ได้โดยอัตโนมัติ

• แนะนำบล็อกโพสต์เกี่ยวกับโปรเจ็กต์ krep

  • ในหน้าโฮมเพจระบุว่าเร็วกว่า ripgrep
  • อยากเห็นการเปรียบเทียบกับชุดเบนช์มาร์กของ ripgrep แบบเต็ม
  • เกิดข้อผิดพลาดเกี่ยวกับ madvise(), ต้องเพิ่ม -D_GNU_SOURCE ใน CFLAGS ของ Makefile

• ความสำคัญของเคสทดสอบ

  • ปัญหาขอบเขตของชังก์ในการค้นหาไฟล์แบบมัลติเธรดชวนให้กังวล
  • เพิ่ม edge case ใหม่ให้กับการค้นหาแบบธรรมดา
  • ถ้าเพิ่มตัวอักษรหนึ่งตัวในไฟล์ อาจทำให้การแมตช์พังได้

• ผลเบนช์มาร์กหลังแก้ปัญหาการบิลด์

  • การลองรันเบนช์มาร์กครั้งแรกช้า
  • ripgrep เร็วกว่า krep 1.52 เท่า

• การลองเบนช์มาร์กที่มีความถี่การแมตช์สูง

  • krep เร็วกว่า ripgrep 3.40 เท่า
  • จำนวนแมตช์แตกต่างกันมาก
  • krep อาจให้ผลลัพธ์ที่ไม่ถูกต้อง

• การลองเบนช์มาร์กเพิ่มเติม

  • ripgrep เร็วกว่าในการค้นหาแพตเทิร์นบางแบบ
  • krep หาแมตช์ไม่เจอ

• อัลกอริทึมของ ripgrep และการใช้ memory map

  • ripgrep ใช้อัลกอริทึมค้นหา substring ขั้นสูง
  • ใช้ memory map และการประมวลผลแบบขนาน
  • krep ก็ใช้การประมวลผลแบบขนานเช่นกัน และใช้มัลติเธรดเมื่อค้นหาไฟล์เดี่ยว

• ข้อสงสัยเกี่ยวกับผลเบนช์มาร์ก

  • เป็นเรื่องแปลกที่ ripgrep ใช้เวลามากกว่า 40 วินาทีในการค้นหาแพตเทิร์นในไฟล์ขนาด 5GB
  • ขอให้ OP อธิบายวิธีทำเบนช์มาร์กซ้ำเพื่อให้ได้ผลแบบเดียวกัน

• ความเห็นเกี่ยวกับชื่อ krep

  • "re" ใน grep หมายถึง regular expression
  • krep ไม่ได้ใช้ regular expression ดังนั้นชื่อนี้อาจไม่เหมาะ