Krep - Công cụ tìm kiếm chuỗi nhanh hơn grep 5 lần

 (davidesantangelo.github.io)
10 điểm bởi GN⁺ 2025-03-13 | 2 bình luận | Chia sẻ qua WhatsApp
  • Công cụ tìm kiếm chuỗi siêu tốc được viết bằng C dành cho các ứng dụng coi trọng hiệu năng
  • Tự động chọn thuật toán tối ưu một cách động tùy theo đặc tính của mẫu và phần cứng
  • Tận dụng phần cứng như SSE4.2/AVX2 để cung cấp thông lượng tối đa
  • Chia tệp thành các chunk để hỗ trợ dung lượng lớn và xử lý song song đa luồng
  • Sử dụng thuật toán tìm kiếm phù hợp nhất tùy theo mẫu
    • Boyer-Moore-Horspool: phù hợp cho khớp mẫu thông thường
    • Thuật toán Knuth-Morris-Pratt (KMP): tối ưu cho mẫu ngắn
    • Rabin-Karp: hiệu quả với mẫu dài
    • Tăng tốc SIMD: cải thiện hiệu năng trên phần cứng hỗ trợ SSE4.2, AVX2
  • Sử dụng memory-mapped file I/O để giảm thiểu system call và tối đa hóa thông lượng
  • Tùy chọn tìm kiếm linh hoạt
    • Tìm kiếm phân biệt chữ hoa chữ thường và không phân biệt
    • Có thể tìm trực tiếp trong chuỗi ngoài việc tìm trong tệp
    • Cung cấp chế độ chỉ in số lần khớp

Cách sử dụng

krep [OPTIONS] PATTERN [FILE]
  • Tìm “error” trong tệp log: krep "error" system.log
  • Tìm kiếm không phân biệt hoa thường với 8 luồng: krep -i -t 8 "ERROR" large_logfile.log
  • In số lần khớp (không in các dòng đã khớp): krep -c "TODO" *.c
  • Tìm trực tiếp trong chuỗi thay vì trong tệp: krep -s "Hello" "Hello world"

Tùy chọn dòng lệnh

  • -i : tìm kiếm không phân biệt chữ hoa chữ thường
  • -c : chỉ in số lần khớp mà không in các dòng đã khớp
  • -t NUM : sử dụng NUM luồng (mặc định: 4)
  • -s STRING : tìm trong chuỗi thay vì trong tệp
  • -v : in thông tin phiên bản
  • -h : in trợ giúp

Benchmark

  • Hiệu năng của krep vượt trội rõ rệt so với các công cụ tìm kiếm chuỗi thông dụng.
    • krep mất 0,78 giây để tìm một mẫu thông thường trong tệp văn bản 1GB, tương đương tốc độ 1.282MB/giây
    • grep mất 2,95 giây cho cùng tác vụ, đạt tốc độ 339MB/giây
    • ripgrep mất 1,48 giây, đạt tốc độ 676MB/giây
  • → krep nhanh hơn grep khoảng 3,8 lần và nhanh hơn ripgrep khoảng 1,9 lần (hiệu năng có thể thay đổi tùy phần cứng và đặc tính tệp)

Nguồn gốc tên gọi

  • “krep” bắt nguồn từ từ tiếng Iceland “kreppan”
  • Có nghĩa là “chộp lấy thật nhanh”
  • Tượng trưng cho khả năng nhận diện mẫu hiệu quả
  • Là một lệnh ngắn gọn, súc tích và dễ gõ

Bài viết liên quan

2 bình luận

 
clickin 2025-03-13

Nếu bỏ hỗ trợ biểu thức chính quy mà cũng chỉ nhanh hơn ripgrep khoảng 2 lần thì độ hữu dụng đúng là hơi thấp.
Có lẽ tôi sẽ cứ tiếp tục dùng ripgrep vì nó hỗ trợ biểu thức chính quy.
 
GN⁺ 2025-03-13
Ý kiến trên Hacker News

  • Tính năng CPU (ví dụ: AVX2) cần được phát hiện ở thời gian chạy

    • ifdef chỉ phát hiện ở thời điểm build liệu trình biên dịch có hỗ trợ hay không
    • Chương trình chỉ được biên dịch khi trình biên dịch hỗ trợ AVX2
    • Cần kiểm tra ở thời gian chạy xem CPU có hỗ trợ AVX2 hay không
    • Trong dự án có đoạn "phát hiện ở thời điểm cấu hình bằng cờ CPUID và kiểm tra thực thi lệnh thực tế"
    • Có thể tự động tận dụng các lệnh SSE4.2 và AVX2

  • Giới thiệu bài đăng blog về dự án krep

    • Trên trang chủ nói rằng nó nhanh hơn ripgrep
    • Muốn so sánh với toàn bộ benchmark của ripgrep
    • Phát sinh lỗi liên quan đến madvise(), cần thêm '-D_GNU_SOURCE' vào CFLAGS của Makefile

  • Tầm quan trọng của test case

    • Vấn đề ranh giới chunk trong tìm kiếm tệp đa luồng là điều đáng lo
    • Đưa thêm edge case mới vào một tác vụ tìm kiếm đơn giản
    • Chỉ cần thêm một ký tự vào tệp là kết quả khớp có thể bị hỏng

  • Kết quả benchmark sau khi khắc phục vấn đề build

    • Ở lần thử benchmark đầu tiên, tốc độ chậm
    • ripgrep nhanh hơn krep 1.52 lần

  • Thử benchmark với tần suất khớp cao

    • krep nhanh hơn ripgrep 3.40 lần
    • Số lượng kết quả khớp chênh lệch rất lớn
    • krep có thể không cung cấp kết quả chính xác

  • Các lần thử benchmark bổ sung

    • ripgrep nhanh hơn trong việc tìm một số mẫu cụ thể
    • krep không tìm ra kết quả khớp

  • Thuật toán của ripgrep và việc dùng memory map

    • ripgrep sử dụng thuật toán tìm kiếm chuỗi con nâng cao
    • Sử dụng memory map và xử lý song song
    • krep cũng dùng xử lý song song, sử dụng đa luồng khi tìm trong một tệp đơn

  • Nghi vấn về kết quả benchmark

    • Việc ripgrep mất hơn 40 giây để tìm mẫu trong tệp 5GB là điều bất thường
    • Yêu cầu OP chia sẻ cách tái hiện benchmark

  • Ý kiến về tên gọi krep

    • "re" trong grep có nghĩa là regular expression
    • krep không dùng regular expression nên có thể đây là một cái tên chưa phù hợp