why GNU grep is fast
GNU grep이 빠른 이유
- 원문 : [why GNU grep is fast] by Mike Haertel
- 인상 깊은 글이라 주인장이 번역해보았습니다만, GNU grep 소스를 알고 번역한 게 아니라 오역이 있을 수 있습니다. 각주들은 원문에 없이 제가 참고로 달아둔 것입니다.
안녕하세요 Gabor씨,
저는 GNU grep의 원 개발자입니다. 저는 또한 FreeBSD 사용자이기도 하지요, 비록 -stable(과 그 이전) 버전을 쓰고 -current 버전에는 거의 관심을 두고 있지 않지만요.
그러나, 다른 일로 -current 메일링 리스트를 검색하다가 BSD grep과 GNU grep의 성능 비교에 관한 논쟁을 보게 되었습니다. 당신도 그 토론을 보셨을지 모르겠습니다.
어쨌거나, 참고하십사 하여, GNU grep이 어떻게 빠른 속도로 실행되는지에 관한 간단한 요약을 해드립니다. 희망컨대 당신이 이 아이디어들을 BSD grep에 옮길 수도 있을 것입니다.
비결 #1: GNU grep은 모든 입력 바이트를 전부 살펴보지는 않기 때문에 빠릅니다.
비결 #2: GNU grep은 *살펴보는* 바이트마다 매우 적은 인스트럭션만 수행하기 때문에 빠릅니다.
GNU grep은 잘 알려진 Boyer-Moore 알고리즘을 사용합니다. 이 알고리즘은 타겟 스트링의 마지막 글자를 먼저 찾고, 매치되지 않는 글자를 발견할 때마다 입력을 얼마나 건너뛸 수 있는지 알 수 있도록 룩업테이블을 사용합니다.
GNU grep은 또한 Boyer-Moore 알고리즘의 안쪽 루프를 풀어서(unroll) 최적화하고, Boyer-Moore 델타 테이블을 세팅하여 unroll된 모든 단계에서 루프 종료 검사를 할 필요가 없도록 하였습니다. 그 결과, 한도 내에서 GNU grep은 (많은 입력 바이트를 건너뛰고) 실제로 살펴보는 바이트 각각에 대해 평균 3개 미만의 x86 인스트럭션을 수행합니다.
"Software: Practice & Experience" 저널 1991년 11월호에 있는, Andrew Hume과 Daniel Sunday가 쓴 "Fast String Searching"을 보시면 Boyer-Moore 알고리즘 구현 기교들에 관한 좋은 논의들이 있습니다. 온라인에서 무료로 PDF를 얻을 수 있습니다.
빠르게 검색할 수 있게 되었다면, 그 다음은 빠르게 입력받는 방법이 필요하다는 것을 알게 될 것입니다.
GNU grep은 저수준(raw) 유닉스 입력 시스템 콜을 사용하여, 데이타를 읽은 후 복사하는 것을 방지합니다.
게다가, GNU grep은 입력을 행 단위로 끊지 않습니다. 개행문자를 찾는 것은 grep의 속도를 몇 배로 느려지게 하는데, 그 이유는 개행문자를 찾기 위해서는 결국 모든 바이트를 살펴보아야 하기 때문입니다!
GNU grep은 그래서 행 단위의 입력을 사용하지 않고, 원(raw) 데이타를 큰 버퍼에 읽어들이고, 버퍼 안에서 Boyer-Moore 알고리즘을 사용하여 검색을 한 후, 매치되는 부분을 찾았을 때만 그 부분의 경계가 되는 개행문자를 찾아봅니다. (-n 과 같은 몇몇 명령행 옵션들을 쓰면 이 최적화를 하지 못하게 됩니다.)
마지막으로, 제가 GNU grep의 마지막 메인테이너였을 때(15년도 더 이전에...), GNU grep은 또한 여러 가지 세팅을 사용하여 *커널* 역시 입력된 모든 바이트를 다루지 않아도 되도록 열심히 노력했습니다. 파일을 읽을 때 read() 대신 mmap()을 사용하는 식으로 말이죠. 당시에, read()를 쓰면 대부분의 Unix 버전에서는 추가의 복사 과정이 수행되었습니다. 제가 GNU grep 관리에서 손을 땐 후에, mmap을 사용하는 게 기본 방식이 아니게 된 것 같습니다만, 여전히 --mmap 옵션을 사용하여 그렇게 동작하게 할 수 있습니다. 그리고 최소한, 데이타가 이미 파일 시스템 버퍼 캐시에 있는 경우에는, mmap은 여전히 더 빠릅니다:
$ time sh -c 'find . -type f -print | xargs grep -l 123456789abcdef'
real 0m1.530s
user 0m0.230s
sys 0m1.357s
$ time sh -c 'find . -type f -print | xargs grep --mmap -l 123456789abcdef'
real 0m1.201s
user 0m0.330s
sys 0m0.929s
[테스트 대상은 648메가바이트짜리 MH 메일 폴더이고 41000개의 메시지가 들어있습니다]
따라서 현재도, --mmap을 사용하면 20%이상의 속도 향상을 얻을 수 있습니다.
요약하면:
- Boyer-Moore 알고리즘을 사용하세요 (그리고 내부 루프를 몇 차례 푸세요).
- 저수준(raw) 시스템 콜을 사용하여 버퍼를 쓰지 않고 입력을 받아 처리하세요. 검색하기 전에 입력 데이타를 복사하는과정을 피하세요. (하지만, *출력*은 버퍼를 사용하세요. 일반적인 grep 시나리오는 입력에 비해 출력되는 양이 작고, 따라서 출력 버퍼에 복사하는 오버헤드는 작은 반면에, 작은 양을 버퍼없이 빈번하게 출력하는 일을 피함으로써 얻는 이득은 클 수 있습니다.)
- 매치되는 부분을 찾기 전에는 개행문자를 검색하지 마세요.
- 여러 가지 설정(버퍼를 페이지에 맞추기(page-aligned buffer), 입력 덩어리의 크기를 페이지 크기로 하기(page-szied read chunks), 선택적으로는 mmap 사용하기)을 통하여 커널 역시도 바이트들을 복사하는 것을 피할 수 있습니다.
프로그램을 빠르게 만드는 열쇠는 프로그램이 사실상 아무 일도 하지 않게 만드는 것이죠. ;-)
감사합니다,
Mike
컴퓨터분류
![[첫화면으로]](/raymundo_logo.jpg){kind=logo}
Why GNU grep is fast
MH_Message_Handling_System 이거?