Why GNU grep is fast 페이지의 소스 보기

내용출력
로그인[l]
수정할 수 없습니다: Why_GNU_grep_is_fast 는 읽기 전용 페이지입니다.
= why GNU grep is fast =
= GNU grep이 빠른 이유 =

* 원문 : [http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html 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"<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를 얻을 수 있습니다.

빠르게 검색할 수 있게 되었다면, 그 다음은 빠르게 입력받는 방법이 필요하다는 것을 알게 될 것입니다.

GNU grep은 저수준(raw) 유닉스 입력 시스템 콜을 사용하여, 데이타를 읽은 후 복사하는 것을 방지합니다.

게다가, GNU grep은 '''입력을 행 단위로 끊지 않습니다'''. 개행문자를 찾는 것은 grep의 속도를 몇 배로 느려지게 하는데, 그 이유는 개행문자를 찾기 위해서는 결국 모든 바이트를 살펴보아야 하기 때문입니다!

GNU grep은 그래서 행 단위의 입력을 사용하지 않고, 원(raw) 데이타를 큰 버퍼에 읽어들이고, 버퍼 안에서 Boyer-Moore 알고리즘을 사용하여 검색을 한 후, 매치되는 부분을 찾았을 때만 그 부분의 경계가 되는 개행문자를 찾아봅니다. (-n 과 같은 몇몇 명령행 옵션들을 쓰면 이 최적화를 하지 못하게 됩니다.)

마지막으로, 제가 GNU grep의 마지막 메인테이너였을 때(15년도 더 이전에...), GNU grep은 또한 여러 가지 세팅을 사용하여 *커널* '''역시''' 입력된 모든 바이트를 다루지 않아도 되도록 열심히 노력했습니다. 파일을 읽을 때 read() 대신 mmap()을 사용하는 식으로 말이죠. 당시에, read()를 쓰면 대부분의 Unix 버전에서는 추가의 복사 과정이 수행되었습니다<footnote(커널 버퍼에서 사용자 버퍼로 복사되는 것 얘기일 듯)>. 제가 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<footnote(뭔지 모르겠는데 아마도 Wikipedia:MH_Message_Handling_System 이거?)> 메일 폴더이고 41000개의 메시지가 들어있습니다]

따라서 현재도, --mmap을 사용하면 20%이상의 속도 향상을 얻을 수 있습니다.

요약하면:

- Boyer-Moore 알고리즘을 사용하세요 (그리고 내부 루프를 몇 차례 푸세요).

- 저수준(raw) 시스템 콜을 사용하여 버퍼를 쓰지 않고 입력을 받아 처리하세요. 검색하기 전에 입력 데이타를 복사하는과정을 피하세요. (하지만, *출력*은 버퍼를 사용하세요. 일반적인 grep 시나리오는 입력에 비해 출력되는 양이 작고, 따라서 출력 버퍼에 복사하는 오버헤드는 작은 반면에, 작은 양을 버퍼없이 빈번하게 출력하는 일을 피함으로써 얻는 이득은 클 수 있습니다.)

- 매치되는 부분을 찾기 전에는 개행문자를 검색하지 마세요.

- 여러 가지 설정(버퍼를 페이지에 맞추기(page-aligned buffer), 입력 덩어리의 크기를 페이지 크기로 하기(page-szied read chunks), 선택적으로는 mmap 사용하기)을 통하여 커널 '''역시도''' 바이트들을 복사하는 것을 피할 수 있습니다.

프로그램을 빠르게 만드는 열쇠는 프로그램이 사실상 아무 일도 하지 않게 만드는 것이죠. ;-)

감사합니다,

Mike

----

<div class="comments">
<longcomments(100)>
</div>
----
[[컴퓨터분류]]
Why GNU grep is fast 페이지로 돌아가기 | 다른 수정본 보기