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

> Clean Markdown view of GeekNews topic #19713. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=19713](https://news.hada.io/topic?id=19713)
- GeekNews Markdown: [https://news.hada.io/topic/19713.md](https://news.hada.io/topic/19713.md)
- Type: GN+
- Author: [xguru](https://news.hada.io/@xguru)
- Published: 2025-03-13T09:22:24+09:00
- Updated: 2025-03-13T09:22:24+09:00
- Original source: [davidesantangelo.github.io](https://davidesantangelo.github.io/krep/)
- Points: 10
- Comments: 2

## Summary

Krep은 성능이 중요한 애플리케이션을 위해 C로 작성된 초고속 문자열 검색 도구로, 패턴 특성과 하드웨어에 따라 최적의 알고리즘을 동적으로 선택하여 최대 처리량을 제공합니다. 이 도구는 대용량 파일을 청크로 나누어 멀티스레딩 병렬 처리하며, 다양한 검색 알고리즘과 SIMD 가속을 통해 성능을 극대화합니다. 벤치마크 결과, Krep은 grep보다 약 3.8배, ripgrep보다 약 1.9배 빠른 성능을 보입니다.

## Topic Body

- 성능이 중요한 애플리케이션을 위해 **C로 작성**된 초고속 문자열 검색 도구  
- 패턴 특성과 하드웨어에 따라 최적의 알고리듬을 동적으로 선택  
- SSE4.2/AVX2 같은 하드웨어를 활용하여 최대 처리량을 제공  
- 대용량 지원을 위해 파일을 **청크**로 나눠 **멀티스레딩 병렬 처리**  
- 패턴에 따라 가장 적합한 **검색 알고리듬** 사용   
  - Boyer-Moore-Horspool: 일반적인 패턴 매칭에 적합  
  - Knuth-Morris-Pratt (KMP) 알고리즘: 짧은 패턴에 최적화  
  - Rabin-Karp: 긴 패턴에 효과적  
  - SIMD 가속: SSE4.2, AVX2 지원 하드웨어에서 성능 향상  
- **메모리 매핑 파일 I/O** 사용으로 시스템 호출을 최소화해 처리량 극대화  
- **유연한 검색 옵션**  
  - 대소문자 구분 및 구분 없는 검색  
  - 파일 검색 외에 직접 문자열 검색 가능  
  - 일치 횟수만 출력하는 모드 제공  
  
#### 사용 방법  
```bash  
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**은 1GB 텍스트 파일에서 일반적인 패턴을 검색하는 데 **0.78초**가 걸렸으며, 이는 초당 **1,282MB**의 속도를 의미함  
	- **grep**은 같은 작업에 **2.95초**가 걸렸으며, 초당 **339MB**의 속도를 기록함  
	- **ripgrep**은 **1.48초**가 걸렸으며, 초당 **676MB**의 속도를 보임  
- **→ `krep`은 `grep`보다 약 3.8배 빠르고, `ripgrep`보다 약 1.9배 빠름**  (하드웨어 및 파일 특성에 따라 성능이 달라질 수 있음)  
  
#### 이름의 유래  
- **“krep”** 은 아이슬란드어 **“kreppan”**에서 유래함  
- “빠르게 움켜잡다”는 뜻을 가짐  
- 효율적인 패턴 인식을 상징함  
- 짧고 간결한 명령어로 타이핑이 용이함

## Comments



### Comment 35824

- Author: clickin
- Created: 2025-03-13T14:02:44+09:00
- Points: 1

정규식 지원을 버리고서 ripgrep보다 2배밖에 빠르지 못하면 활용도가 좀 낮긴 하네요.  
저는 그냥 정규식 되는 ripgrep을 계속 쓸 것 같아요.

### Comment 35801

- Author: neo
- Created: 2025-03-13T09:22:24+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=43333946) 
* CPU 기능(예: AVX2)은 런타임에서 감지되어야 함
  - ifdef는 컴파일러가 지원하는지 빌드 타임에만 감지함
  - 프로그램은 컴파일러가 AVX2를 지원할 때만 컴파일됨
  - 런타임에서 CPU가 AVX2를 지원하는지 확인해야 함
  - 프로젝트에서 "구성 시간에 CPUID 플래그와 실제 명령어 실행 테스트를 통해 감지"라는 부분이 있음
  - SSE4.2와 AVX2 명령어를 자동으로 활용할 수 있음

* krep 프로젝트에 대한 블로그 게시물 소개
  - 홈페이지에서 ripgrep보다 빠르다고 나옴
  - 전체 ripgrep 벤치마크와 비교해보고 싶음
  - madvise() 관련 오류 발생, Makefile의 CFLAGS에 '-D_GNU_SOURCE' 추가 필요

* 테스트 케이스의 중요성
  - 멀티스레드 파일 검색에서 청크 경계 문제는 신경 쓰임
  - 단순 검색에 새로운 엣지 케이스를 도입함
  - 파일에 한 글자를 추가하면 매치가 깨질 수 있음

* 빌드 문제 해결 후 벤치마크 결과
  - 첫 번째 벤치마크 시도에서 속도가 느림
  - ripgrep이 krep보다 1.52배 빠름

* 매치 빈도가 높은 벤치마크 시도
  - krep이 ripgrep보다 3.40배 빠름
  - 매치 수가 크게 차이남
  - krep이 정확한 결과를 제공하지 않을 수 있음

* 추가 벤치마크 시도
  - ripgrep이 특정 패턴을 찾는 데 더 빠름
  - krep이 매치를 찾지 못함

* ripgrep의 알고리즘과 메모리 맵 사용
  - ripgrep은 고급 서브스트링 검색 알고리즘 사용
  - 메모리 맵과 병렬 처리 사용
  - krep도 병렬 처리 사용, 단일 파일 검색 시 멀티스레드 사용

* 벤치마크 결과에 대한 의문
  - ripgrep이 5GB 파일에서 패턴 검색 시 40초 이상 걸린다는 것은 이상함
  - OP에게 벤치마크 재현 방법 요청

* krep의 이름에 대한 의견
  - grep의 "re"는 정규 표현식을 의미함
  - krep은 정규 표현식을 사용하지 않으므로 이름이 잘못된 것일 수 있음