Krep - grep 보다 5배 빠른 문자열 검색 도구

• 성능이 중요한 애플리케이션을 위해 C로 작성된 초고속 문자열 검색 도구
• 패턴 특성과 하드웨어에 따라 최적의 알고리듬을 동적으로 선택
• SSE4.2/AVX2 같은 하드웨어를 활용하여 최대 처리량을 제공
• 대용량 지원을 위해 파일을 청크로 나눠 멀티스레딩 병렬 처리
• 패턴에 따라 가장 적합한 검색 알고리듬 사용
  • Boyer-Moore-Horspool: 일반적인 패턴 매칭에 적합
  • Knuth-Morris-Pratt (KMP) 알고리즘: 짧은 패턴에 최적화
  • Rabin-Karp: 긴 패턴에 효과적
  • SIMD 가속: SSE4.2, AVX2 지원 하드웨어에서 성능 향상
• 메모리 매핑 파일 I/O 사용으로 시스템 호출을 최소화해 처리량 극대화
• 유연한 검색 옵션
  • 대소문자 구분 및 구분 없는 검색
  • 파일 검색 외에 직접 문자열 검색 가능
  • 일치 횟수만 출력하는 모드 제공

사용 방법

• 로그 파일에서 “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은 1GB 텍스트 파일에서 일반적인 패턴을 검색하는 데 0.78초가 걸렸으며, 이는 초당 1,282MB의 속도를 의미함
  • grep은 같은 작업에 2.95초가 걸렸으며, 초당 339MB의 속도를 기록함
  • ripgrep은 1.48초가 걸렸으며, 초당 676MB의 속도를 보임
• → krep은 grep보다 약 3.8배 빠르고, ripgrep보다 약 1.9배 빠름 (하드웨어 및 파일 특성에 따라 성능이 달라질 수 있음)

이름의 유래

• “krep” 은 아이슬란드어 **“kreppan”**에서 유래함
• “빠르게 움켜잡다”는 뜻을 가짐
• 효율적인 패턴 인식을 상징함
• 짧고 간결한 명령어로 타이핑이 용이함