Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

들어가며 — "빠르다"는 말로는 부족하다
정규식 엔진 — 백트래킹을 버리다
SIMD memchr — 바이트를 한 번에 여러 개씩
병렬 디렉터리 순회 — 코어를 놀리지 않는다
.gitignore 존중 — 안 읽는 것이 가장 빠르다
스마트 케이스 — 사람의 의도를 추론한다
바이너리 파일 건너뛰기 — 쓸모없는 데이터를 피한다
mmap — 파일을 통째로 메모리에 매핑
조각들을 합치면 — 파이프라인 전체 그림
빠른 도구를 만드는 교훈
마치며
참고 자료

들어가며 — "빠르다"는 말로는 부족하다

ripgrep(명령어 이름은 rg)을 처음 써 본 사람의 반응은 대개 비슷합니다. "이게 왜 이렇게 빠르지?" 수십만 개 파일이 든 저장소에서 문자열 하나를 찾는데, 결과가 거의 즉시 나옵니다. grep -r이나 ack, git grep에 익숙하던 사람에게는 체감 속도가 다른 차원입니다.

흔한 오해는 "Rust로 짜서 빠르다"는 설명입니다. 언어는 거들 뿐입니다. Rust로 느린 프로그램을 짜는 것도 얼마든지 가능합니다. ripgrep의 속도는 단일 비법이 아니라, 정규식 엔진 선택부터 파일 시스템 순회 전략, 바이트 단위 최적화까지 수십 개의 결정이 겹겹이 쌓인 결과입니다. 이 글은 그 결정들을 하나씩 풀어헤쳐, 빠른 명령줄 도구가 실제로 무엇을 다르게 하는지 살펴봅니다.

정규식 엔진 — 백트래킹을 버리다

ripgrep의 심장은 Rust로 작성된 regex 크레이트입니다. 그리고 이 엔진의 가장 중요한 설계 선택은 백트래킹을 하지 않는다는 것입니다.

Perl, Python, PCRE 계열의 전통적인 정규식 엔진 대부분은 백트래킹 방식입니다. 이 방식은 강력합니다. 역참조(backreference)나 룩어라운드 같은 표현력 높은 기능을 지원합니다. 하지만 대가가 있습니다. 어떤 패턴은 입력 길이에 대해 지수 시간으로 폭발합니다. 이른바 "치명적 백트래킹(catastrophic backtracking)"입니다. (a+)+$ 같은 패턴에 적당한 입력을 주면 CPU가 몇 초, 몇 분씩 매달립니다. 이것이 ReDoS(정규식 서비스 거부) 공격의 원리이기도 합니다.

ripgrep의 엔진은 다른 길을 갑니다. 정규식을 **유한 오토마타(finite automata)**로 컴파일합니다. 이론적으로 말하면, 역참조가 없는 정규 표현식은 유한 오토마타로 표현할 수 있고, 유한 오토마타는 입력을 딱 한 번, 문자 하나당 상수 시간에 훑으면서 매칭 여부를 판정합니다. 즉 **입력 길이에 선형(linear)**입니다. 최악의 경우에도 폭발하지 않습니다.

두 방식의 차이를 정리하면 이렇습니다.

구분	백트래킹 엔진	유한 오토마타 엔진
대표 예	PCRE, Perl, Python `re`	RE2, Rust `regex`
최악 시간 복잡도	지수 (폭발 가능)	선형 (입력 길이에 비례)
역참조/룩어라운드	지원	미지원 (의도적 배제)
ReDoS 취약성	있음	없음

여기서 핵심은 트레이드오프입니다. ripgrep은 역참조 같은 일부 기능을 일부러 포기했습니다. 그 대가로 어떤 입력에도 폭발하지 않는 선형 성능 보장을 얻었습니다. 검색 도구에게 이것은 옳은 선택입니다. 사용자가 실수로 던진 패턴 하나가 도구를 멈춰 세우면 안 되니까요.

내부적으로 이 엔진은 하나의 오토마타만 쓰지 않습니다. 상황에 따라 여러 전략을 섞습니다. 짧은 리터럴은 전용 리터럴 검색으로, 복잡한 패턴은 지연 DFA(lazy DFA)로 처리하고, 문자열의 접두사에서 뽑아낸 리터럴로 후보 위치를 빠르게 좁힙니다. "정규식을 만나면 무조건 오토마타를 하나 돌린다"가 아니라, "가능한 한 값싼 방법으로 먼저 걸러낸다"가 실제 동작에 가깝습니다.

SIMD memchr — 바이트를 한 번에 여러 개씩

정규식 매칭 이전에, 더 근본적인 병목이 있습니다. 바로 "이 큰 텍스트 어디에 후보가 있는가"를 찾는 일입니다. ripgrep은 이걸 memchr로 해결합니다.

memchr는 이름 그대로 "메모리에서 특정 바이트를 찾는" 연산입니다. 순진하게 구현하면 바이트를 하나씩 비교하는 루프입니다. 하지만 현대 CPU에는 SIMD(Single Instruction, Multiple Data) 명령이 있습니다. x86의 SSE2/AVX2, ARM의 NEON 같은 것들입니다. 이 명령은 한 번에 16바이트, 32바이트, 심지어 64바이트를 동시에 비교합니다.

핵심 아이디어는 이렇습니다. 정규식이든 리터럴이든, 검색하려는 패턴에는 대개 "반드시 등장해야 하는 바이트"가 있습니다. 예를 들어 function을 찾는다면 f가 없는 곳에는 매칭이 없습니다. 그래서 ripgrep은 먼저 SIMD memchr로 f가 나오는 위치를 초고속으로 훑어 후보를 찾고, 그 근처에서만 실제 정규식 매칭을 시도합니다. 대부분의 텍스트는 후보조차 아니므로, 값비싼 매칭 로직을 아예 건너뜁니다.

  큰 텍스트 버퍼
  ├─ (1) SIMD memchr로 필수 바이트 위치를 초고속 스캔
  │       → 대부분의 영역은 여기서 즉시 탈락
  ├─ (2) 후보 위치 근처에서만
  │       → 실제 정규식/리터럴 매칭 수행
  └─ 결과

이 "값싼 필터로 먼저 거르고, 비싼 검사는 최소한만" 전략은 ripgrep 전체를 관통하는 철학입니다. memchr는 그 첫 번째 관문입니다. 참고로 이 memchr 크레이트는 워낙 잘 만들어져서 Rust 생태계 곳곳에서 독립적으로 널리 쓰입니다.

병렬 디렉터리 순회 — 코어를 놀리지 않는다

파일 하나를 빠르게 뒤지는 것과, 저장소 전체를 빠르게 뒤지는 것은 다른 문제입니다. 수십만 개 파일을 훑을 때는 "얼마나 병렬로 처리하느냐"가 결정적입니다.

전통적인 grep -r은 기본적으로 단일 스레드로 디렉터리를 훑습니다. 반면 ripgrep은 여러 스레드를 띄워 디렉터리 트리를 병렬로 순회합니다. 워커 스레드들이 작업 큐를 공유하면서, 발견한 하위 디렉터리를 큐에 넣고, 파일이 나오면 검색합니다. 코어가 8개라면 8개의 파일을 동시에 뒤질 수 있습니다.

여기서 미묘하지만 중요한 설계가 나옵니다. 바로 출력 순서입니다. 병렬로 검색하면 결과가 뒤죽박죽 순서로 나올 수 있습니다. ripgrep은 기본적으로는 성능을 위해 순서를 보장하지 않지만, --sort path 같은 옵션을 주면 결정론적 순서로 정렬해 냅니다. 즉 병렬성과 재현성 사이의 선택권을 사용자에게 줍니다.

병렬화는 공짜가 아닙니다. 스레드 간 조율 비용, 파일 시스템 자체의 병목(특히 네트워크 파일 시스템이나 느린 디스크)이 있습니다. 그래서 ripgrep은 워커 수를 논리 코어 수에 맞춰 자동 조정하고, --threads로 직접 제어할 수도 있게 합니다. 병렬화의 교훈은 "무조건 스레드를 많이 띄우면 빠르다"가 아니라 "일감을 균형 있게 나누고 조율 비용을 최소화한다"는 것입니다.

.gitignore 존중 — 안 읽는 것이 가장 빠르다

ripgrep 속도의 절반은 "빠르게 읽는 것"이 아니라 **"읽지 않는 것"**에서 나옵니다. 이것이 ripgrep의 가장 실용적인 통찰입니다.

grep -r은 순진합니다. 시키면 node_modules, .git, 빌드 산출물, 로그 디렉터리까지 전부 뒤집니다. 정작 사용자가 찾는 소스 코드는 전체의 극히 일부인데, 나머지 거대한 쓰레기 더미를 다 훑느라 시간을 씁니다.

ripgrep은 기본적으로 .gitignore를 존중합니다. 무시 규칙에 걸린 파일과 디렉터리는 아예 읽지 않고 건너뜁니다. 실제 프로젝트에서 .gitignore에 등록된 것들(의존성, 빌드 캐시, 산출물)은 보통 저장소 용량의 대부분을 차지합니다. 그걸 통째로 건너뛰면 검색해야 할 데이터 양 자체가 극적으로 줄어듭니다.

ripgrep이 참고하는 무시 규칙은 여러 겹입니다.

.gitignore — 각 디렉터리마다 계층적으로 적용
.ignore — ripgrep과 다른 도구들이 공유하는 범용 무시 파일
.rgignore — ripgrep 전용 무시 파일
전역 gitignore와 .git/info/exclude

.gitignore 문법 자체가 만만치 않습니다. 글로브 패턴, 부정(!), 디렉터리 한정, 계층별 오버라이드까지 정확히 구현해야 합니다. ripgrep은 이 규칙 매칭을 별도의 잘 최적화된 라이브러리로 처리합니다. 예를 들어 아래 같은 .gitignore가 있다면:

# 의존성과 빌드 산출물은 검색 대상에서 제외
node_modules/
dist/
*.log
build/

# 단, 이 로그는 추적한다
!important.log

ripgrep은 이 규칙을 정확히 해석해 node_modules/, dist/, build/와 모든 *.log를 건너뛰되 important.log만은 검색합니다. 물론 무시 규칙을 끄고 정말 모든 것을 뒤지고 싶으면 rg -uuu로 무시를 단계적으로 해제할 수 있습니다.

이 설계에는 사고방식의 전환이 담겨 있습니다. grep은 "모든 것을 검색하는 것이 기본, 제외는 예외"입니다. ripgrep은 "의미 있는 소스만 검색하는 것이 기본, 전체 검색은 예외"입니다. 개발자가 실제로 원하는 것에 기본값을 맞춘 것입니다.

스마트 케이스 — 사람의 의도를 추론한다

smart case는 속도보다는 사용성 최적화지만, ripgrep의 "사람이 원하는 것을 기본값으로"라는 철학을 잘 보여줍니다.

규칙은 단순합니다.

검색어가 전부 소문자이면 → 대소문자를 구분하지 않고 검색(case-insensitive)
검색어에 대문자가 하나라도 있으면 → 대소문자를 정확히 구분해 검색(case-sensitive)

예를 들어 rg error는 error, Error, ERROR를 모두 찾습니다. 소문자만 쳤으니 "아무거나 다 보여줘"라는 의도로 해석합니다. 반면 rg Error는 정확히 Error만 찾습니다. 대문자를 일부러 쳤으니 "정확히 이 형태"를 원한다고 해석합니다.

이 동작은 개발자의 실제 습관과 놀랍도록 잘 맞습니다. 대충 찾을 때는 소문자로 대충 치고, 특정 심볼(MyClass, HTTPError)을 찾을 때는 정확히 칩니다. 그 습관을 도구가 읽어냅니다. 명시적으로 강제하고 싶으면 -s(대소문자 구분)나 -i(무시) 플래그로 덮어쓸 수 있습니다.

바이너리 파일 건너뛰기 — 쓸모없는 데이터를 피한다

또 하나의 "읽지 않는" 최적화입니다. ripgrep은 기본적으로 바이너리 파일을 감지해 건너뜁니다.

이미지, 실행 파일, 압축 파일 안에서 텍스트를 정규식으로 찾는 것은 대개 의미가 없습니다. 그런데 이런 바이너리는 종종 크기가 큽니다. 그걸 다 훑으면 시간 낭비일 뿐 아니라, 터미널에 제어 문자가 쏟아져 화면이 깨지기도 합니다.

ripgrep의 감지 방식은 실용적입니다. 파일 앞부분을 조금 읽어 NUL 바이트(\0)가 있는지 봅니다. 텍스트 파일에는 보통 NUL 바이트가 없고, 바이너리에는 흔합니다. NUL이 발견되면 그 파일은 바이너리로 간주하고 처리를 멈춥니다. 완벽한 판별은 아니지만, 실전에서 대단히 잘 작동하는 값싼 휴리스틱입니다.

물론 필요하면 강제할 수 있습니다. rg -a(또는 --text)는 바이너리도 텍스트처럼 취급해 뒤지고, --binary는 바이너리에서도 매칭을 보고합니다. 기본값이 "건너뛰기"인 것은, 그것이 개발자가 원하는 경우가 압도적으로 많기 때문입니다.

mmap — 파일을 통째로 메모리에 매핑

파일을 읽는 방식에도 최적화가 있습니다. ripgrep은 상황에 따라 mmap(메모리 맵)을 씁니다.

일반적인 파일 읽기는 read() 시스템 콜로 커널 버퍼에서 사용자 공간 버퍼로 데이터를 복사합니다. 반면 mmap은 파일을 프로세스의 가상 주소 공간에 직접 매핑합니다. 그러면 파일 내용을 마치 거대한 바이트 배열처럼 접근할 수 있고, 실제 디스크 읽기는 페이지 폴트를 통해 필요할 때 게으르게(lazily) 일어납니다. 데이터 복사 한 단계가 줄어드는 셈입니다.

mmap이 유리한 경우는 주로 하나의 큰 파일을 검색할 때입니다. 매핑 오버헤드를 큰 파일 전체에 걸쳐 상각(amortize)할 수 있기 때문입니다. 반대로 수많은 작은 파일을 검색할 때는 각 파일마다 매핑을 만들고 해제하는 비용이 오히려 커서, 일반적인 버퍼 읽기가 더 빠릅니다.

그래서 ripgrep은 하나만 고집하지 않습니다. 파일 개수와 크기를 보고 mmap과 일반 읽기 중 유리한 쪽을 경험적으로 선택합니다. 필요하면 --mmap이나 --no-mmap으로 직접 강제할 수도 있습니다. 이 대목의 교훈은 "mmap이 항상 빠르다"가 아니라 "상황에 맞는 I/O 전략을 고른다"입니다. 만능 해법은 없습니다.

조각들을 합치면 — 파이프라인 전체 그림

지금까지의 최적화를 하나의 흐름으로 그리면 이렇습니다.

  rg PATTERN 실행
        │
        ▼
  [1] 병렬 워커로 디렉터리 순회 시작
        │
        ▼
  [2] .gitignore / .ignore 규칙으로
      읽을 필요 없는 경로를 통째로 제외
        │
        ▼
  [3] 남은 파일마다: 바이너리인지 검사(NUL 바이트)
        │           바이너리면 건너뜀
        ▼
  [4] 텍스트 파일: mmap 또는 버퍼 읽기로 로드
        │
        ▼
  [5] SIMD memchr로 필수 바이트 후보 위치를 초고속 스캔
        │
        ▼
  [6] 후보 근처에서만 유한 오토마타 정규식 매칭
        │
        ▼
      매칭 결과 출력

각 단계가 다음 단계로 넘어가는 데이터 양을 줄인다는 점에 주목하세요. .gitignore가 파일 수를 줄이고, 바이너리 감지가 또 줄이고, memchr가 매칭을 시도할 위치를 줄입니다. 값비싼 연산(정규식 매칭)에 도달할 때쯤이면 처리할 데이터가 이미 최소한으로 걸러져 있습니다.

빠른 도구를 만드는 교훈

ripgrep을 뜯어보면, 특정 도메인을 넘어서는 일반적인 성능 원칙이 보입니다.

가장 빠른 작업은 하지 않는 작업이다. .gitignore 존중과 바이너리 건너뛰기가 준 이득이, 정교한 매칭 알고리즘이 준 이득보다 클 때가 많습니다. 무엇을 처리하지 않을지를 먼저 설계하세요.
값싼 필터로 먼저 거르고, 비싼 검사는 최소한만. SIMD memchr로 후보를 좁힌 뒤에야 정규식을 돌립니다. 대부분의 데이터가 비싼 경로에 도달하지 못하게 하는 것이 핵심입니다.
최악의 경우를 보장하라. 유한 오토마타로 선형 시간을 보장한 선택은, 평균 성능보다 "어떤 입력에도 폭발하지 않음"을 우선한 결정입니다. 도구는 최악의 순간에 신뢰를 잃습니다.
좋은 기본값이 곧 기능이다. 스마트 케이스, .gitignore 존중, 바이너리 건너뛰기는 모두 "사용자가 대개 원하는 것"을 기본으로 삼았습니다. 설정 없이도 옳게 동작하는 것이 진짜 사용성입니다.
하나의 전략을 고집하지 마라. mmap 대 버퍼 읽기처럼, 상황에 따라 유리한 쪽을 고르는 적응적 선택이 단일 해법보다 낫습니다.
언어는 바닥을 깔아줄 뿐이다. Rust는 제로 코스트 추상화와 안전한 병렬성을 줬지만, 속도의 본질은 위의 알고리즘적·구조적 결정에 있습니다.

마지막 항목을 강조하고 싶습니다. "Rust로 짜서 빠르다"는 절반만 맞습니다. Rust는 무겁지 않은 추상화와 두려움 없는 동시성이라는 좋은 토대를 줬지만, ripgrep이 빠른 진짜 이유는 읽지 않을 것을 읽지 않고, 비싼 일을 최소한만 하고, 최악의 경우를 보장하는 설계에 있습니다. 이 원칙들은 명령줄 도구든, 웹 서버든, 데이터 파이프라인이든 어디에나 적용됩니다.

마치며

ripgrep의 속도는 단일 마법이 아니라 절제된 공학의 합입니다. 정규식 엔진에서는 표현력을 일부 포기하고 선형 시간을 얻었고, I/O에서는 읽지 않는 것을 기본으로 삼았고, CPU에서는 SIMD로 바이트를 한꺼번에 처리했고, 파일 시스템에서는 병렬로 순회했습니다. 각각은 작은 결정이지만 합쳐지면 체감이 완전히 다른 도구가 됩니다.

다음에 rg로 거대한 저장소를 순식간에 뒤질 때, 그 뒤에서 이 조각들이 어떻게 맞물리는지 떠올려 보세요. 그리고 여러분이 만드는 도구에도 같은 질문을 던져 보세요. "이 작업, 애초에 안 할 수는 없을까?"

참고 자료

ripgrep 저장소: https://github.com/BurntSushi/ripgrep
ripgrep은 어떻게 그렇게 빠른가 (저자 Andrew Gallant의 글): https://blog.burntsushi.net/ripgrep/
Rust regex 크레이트: https://docs.rs/regex/
memchr 크레이트: https://docs.rs/memchr/
RE2 (유한 오토마타 정규식 엔진): https://github.com/google/re2
정규식 매칭은 단순하고 빠를 수 있다 (Russ Cox): https://swtch.com/~rsc/regexp/regexp1.html