![[첫화면으로]](/raymundo_logo.jpg){kind=logo}
Why GNU grep is fastWhy GNU grep is fast| -20,7 +20,7 |
| GNU grep은 잘 알려진 Boyer-Moore 알고리즘을 사용합니다. 이 알고리즘은 타겟 스트링의 마지막 글자를 먼저 찾고, 매치되지 않는 글자를 발견할 때마다 입력을 얼마나 건너뛸 수 있는지 알 수 있도록 룩업테이블을 사용합니다. |
| GNU grep은 또한 Boyer-Moore 알고리즘의 안쪽 루프를 풀어서(unroll) 최적화하고, Boyer-Moore 델타 테이블을 세팅하여 unroll된 모든 단계에서 루트 종료 검사를 할 필요가 없도록 하였습니다. 그 결과, 한도 내에서 GNU grep은 (많은 입력 바이트를 건너뛰고) 실제로 살펴보는 바이트 각각에 대해 평균 3개 미만의 x86 인스트럭션을 수행합니다. |
| GNU grep은 또한 Boyer-Moore 알고리즘의 안쪽 루프를 풀어서(unroll) 최적화하고, Boyer-Moore 델타 테이블을 세팅하여 unroll된 모든 단계에서 루프 종료 검사를 할 필요가 없도록 하였습니다. 그 결과, 한도 내에서 GNU grep은 (많은 입력 바이트를 건너뛰고) 실제로 살펴보는 바이트 각각에 대해 평균 3개 미만의 x86 인스트럭션을 수행합니다. |
| "Software: Practice & Experience" 저널 1991년 11월호에 있는, Andrew Hume과 Daniel Sunday가 쓴 "Fast String Searching"<footnote([http://onlinelibrary.wiley.com/doi/10.1002/spe.4380211105/abstract Fast string searching - Hume - 2006 - Software: Practice and Experience - Wiley Online Library])>을 보시면 Boyer-Moore 알고리즘 구현 기교들에 관한 좋은 논의들이 있습니다. 온라인에서 무료로 PDF를 얻을 수 있습니다. |
비결 #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"1을 보시면 Boyer-Moore 알고리즘 구현 기교들에 관한 좋은 논의들이 있습니다. 온라인에서 무료로 PDF를 얻을 수 있습니다. 빠르게 검색할 수 있게 되었다면, 그 다음은 빠르게 입력받는 방법이 필요하다는 것을 알게 될 것입니다. GNU grep은 저수준(raw) 유닉스 입력 시스템 콜을 사용하여, 데이타를 읽은 후 복사하는 것을 방지합니다. 게다가, GNU grep은 입력을 행 단위로 끊지 않습니다. 개행문자를 찾는 것은 grep의 속도를 몇 배로 느려지게 하는데, 그 이유는 개행문자를 찾기 위해서는 결국 모든 바이트를 살펴보아야 하기 때문입니다! GNU grep은 그래서 행 단위의 입력을 사용하지 않고, 원(raw) 데이타를 큰 버퍼에 읽어들이고, 버퍼 안에서 Boyer-Moore 알고리즘을 사용하여 검색을 한 후, 매치되는 부분을 찾았을 때만 그 부분의 경계가 되는 개행문자를 찾아봅니다. (-n 과 같은 몇몇 명령행 옵션들을 쓰면 이 최적화를 하지 못하게 됩니다.) 마지막으로, 제가 GNU grep의 마지막 메인테이너였을 때(15년도 더 이전에...), GNU grep은 또한 여러 가지 세팅을 사용하여 *커널* 역시 입력된 모든 바이트를 다루지 않아도 되도록 열심히 노력했습니다. 파일을 읽을 때 read() 대신 mmap()을 사용하는 식으로 말이죠. 당시에, read()를 쓰면 대부분의 Unix 버전에서는 추가의 복사 과정이 수행되었습니다2. 제가 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메가바이트짜리 MH3 메일 폴더이고 41000개의 메시지가 들어있습니다] 따라서 현재도, --mmap을 사용하면 20%이상의 속도 향상을 얻을 수 있습니다. 요약하면: - Boyer-Moore 알고리즘을 사용하세요 (그리고 내부 루프를 몇 차례 푸세요). - 저수준(raw) 시스템 콜을 사용하여 버퍼를 쓰지 않고 입력을 받아 처리하세요. 검색하기 전에 입력 데이타를 복사하는과정을 피하세요. (하지만, *출력*은 버퍼를 사용하세요. 일반적인 grep 시나리오는 입력에 비해 출력되는 양이 작고, 따라서 출력 버퍼에 복사하는 오버헤드는 작은 반면에, 작은 양을 버퍼없이 빈번하게 출력하는 일을 피함으로써 얻는 이득은 클 수 있습니다.) - 매치되는 부분을 찾기 전에는 개행문자를 검색하지 마세요. - 여러 가지 설정(버퍼를 페이지에 맞추기(page-aligned buffer), 입력 덩어리의 크기를 페이지 크기로 하기(page-szied read chunks), 선택적으로는 mmap 사용하기)을 통하여 커널 역시도 바이트들을 복사하는 것을 피할 수 있습니다. 프로그램을 빠르게 만드는 열쇠는 프로그램이 사실상 아무 일도 하지 않게 만드는 것이죠. ;-) 감사합니다, Mike
MH_Message_Handling_System 이거?