GNU Grep이 이토록 빠른 이유는?

mr.lee의 이미지

아직 grep의 소스를 보지 않은 상태라서 여러분의 생각이 궁금합니다...

17M Byte 짜리 로그파일 30개가 있는데...(약 500M Byte 에 해당하는군요)

grep 'LocationCache' allLogFiles 를 했을때.. 약 5초만에 결과가 나와버립니다.

서버는 Sun Fire v440 운영체제는 솔라리스구요.

머 그렇게 성능이 높은 머신은 아니죠.

mmap를 사용해서 바로 읽어낸다 하더라도, 500M 분량인데..어떻게 이다지도 빨리 search 해버릴 수 가 있는건지...

어떠한 알고리즘이나 기법이 동원되었을까요?

vacancy의 이미지

디스크 읽는 속도에 관해선 논외로 하고,

길이 n인 string에서 길이 m인 string을 search하는게 ;
( 전부 다 찾는게요. )
O(m+n) 의 complexity 를 가집니다.
한마디로 쭉 스캔하면 끝난다는거죠. ;;

결국은 디스크 읽는 속도가 문제죠. ^^a

mr.lee의 이미지

헌데 디스크 읽는속도보다 훨씬 빠르니깐요..

복사했을때 읽고, 쓰고 2배걸린다 쳐도 복사해보면 몇배는 더 걸리거든요.

게다가 비교를 해가며 읽어야 하니 한꺼번에 죽 읽을수도 없을테고..

mmap로 읽으면 버퍼에 다 읽어놓고 엑세스하는것과 시간이 거의 비슷한가요?

최소한 mmap >= loaded buffer 일텐데 ( = 가 될수 있나요?)

ganadist의 이미지

디스크 캐시 또는 파일시스템 캐시를 무시하시면 안됩니다 -0-

----
데스크탑 프로그래머를 꿈꾸는 임베디드 삽질러

elien의 이미지

복사했을 때에는 읽기의 2배 이상이 걸리는 것이 맞습니다.
동일한 하드디스크에서의 복사는 대략 자료를 읽고, 버퍼에 쓰고, flush 하는 구분동작의 반복으로 이루어집니다.
기계장치인 디스크 '헤더' (및 기타 등등)의 이동을 잊지 마세요 :)

훗, 못 믿겠나?

byung82의 이미지

위에 답변이 달려있지만..

쓰기보다는 읽기가 빠릅니다 ^^:

그럼

elien의 이미지

Quote:
쓰기보다는 읽기가 빠릅니다 ^^:

딴지같아서 죄송합니다만;;
디스크 밖에서 바라볼 때는 읽기보다 쓰기가 훨씬 빠릅니다.
(물론 버퍼의 현재 상태에 따라 조금은 차이가 있겠지만요)
그 이유는 보통 램으로 만들어져있는 디스크의 버퍼 때문인데요,
호스트 사이드에서는 보통 버퍼에 파일 및 커맨드를 기록하는 선에서 쓰기작업을 끝낸다고 보기 때문입니다.
디스크 내에서의 기계적인 읽기/쓰기의 속도는 잘 모르겠네요 :)

결국 grep 은 저 멀리 숲으로 가고... OTL

훗, 못 믿겠나?

pjs0919의 이미지

디스크가 빠르다고해도...좀더 효율적 처리를 위해
기존의 Boyer-Moore알고리즘이나 KMP알고리즘을 쓰지 않았을까요?...

\(´∇`)ノ.大韓兒 朴鐘緖人

warpdory의 이미지

elien wrote:
Quote:
쓰기보다는 읽기가 빠릅니다 ^^:

딴지같아서 죄송합니다만;;
디스크 밖에서 바라볼 때는 읽기보다 쓰기가 훨씬 빠릅니다.
(물론 버퍼의 현재 상태에 따라 조금은 차이가 있겠지만요)
그 이유는 보통 램으로 만들어져있는 디스크의 버퍼 때문인데요,
호스트 사이드에서는 보통 버퍼에 파일 및 커맨드를 기록하는 선에서 쓰기작업을 끝낸다고 보기 때문입니다.
디스크 내에서의 기계적인 읽기/쓰기의 속도는 잘 모르겠네요 :)

결국 grep 은 저 멀리 숲으로 가고... OTL

디스크 내에서는 쓰기 작업이 읽기 작업보다 빨라도 2배 이상, 보통 5 배 쯤 느립니다. ... 읽기 작업은 지금 있는 자성의 상태만 읽어 들이면 되지만, 쓰기 작업은 디스크 헤드의 자기장을 바꾸고 디스크에 쓰고 다시 읽어서 제대로 기록되었는지 확인하고 ... 이런 작업이 있기 때문입니다.
그래서 결국 아무리 디스크 밖에서 쓰기 작업이 읽기보다 빠르다고 해도 결국 전체적인 시간을 따지면 읽기 작업이 쓰기 작업보다 2,3 배 쯤 빠르게 됩니다.


---------
귓가에 햇살을 받으며 석양까지 행복한 여행을...
웃으며 떠나갔던 것처럼 미소를 띠고 돌아와 마침내 평안하기를...
- 엘프의 인사, 드래곤 라자, 이영도

즐겁게 놀아보자.

recypace의 이미지

복사는 변수가 많으니

cat xxx > /dev/null

같은거랑 비교해야 하지 않을까요?

음.. 이것도 뭔가 overhead가 있나 모르겠네요.

achrom의 이미지

HDD의 읽기 쓰기 캐쉬는 동작이 조금 다릅니다.
읽기 캐쉬는 요청을 조금해도 많이 읽어두고, 나중에 미리 읽어둔 곳에 대한 요청이 올 것을 기대(CACHE HIT)하는 것이고, 쓰기 캐쉬는 쓰라는 요청이 올 경우에 실제 쓰지 않고 캐쉬에 넣어두고, 나중에 쓸만한 여유가 생기거나, 쓰기 캐쉬가 FULL되어 더이상 캐쉬가 불가능할 때 쓰는 방식으로 동작합니다.
그리고, 요즘은 헤드가 디스크 위를 한번 휙 지나갈 때 모두 읽거나 쓰므로, 실제의 읽기 쓰기 시간은 동일합니다. 다만 읽기 캐쉬와 쓰기 캐쉬의 특성상, 소스 코드가 디스크상에서 인접한 위치에 있다고 가정한다면(대부분 그럴 것입니다), 현실적으로는 읽기가 쓰기보다 더 빠를 수 밖에 없지요.

mr.lee의 이미지

음 제가 올린 토론의 주제는...

GNU Grep에서 파일 IO 및 탐색에 사용되는 알고리즘이 어떤것일까?

라는 것이었는데 oTL

vacancy의 이미지

I/O 쪽은 cache와 read ahead 때문이라고밖에 생각하기 어렵네요 ..

어쨌든 읽기는 할테니까 .. ;;

체스맨의 이미지

위에서 이미 말씀하셨듯이 디스크 쓰기 속도가 읽기보다 현저히
느린 이유 등으로 애초에 속도 비교가 잘 못 됐습니다.

저도 소스를 살피진 않았지만, grep은 대개 입력된 정규 표현식을
regex 함수들로 미리 파싱해놓은뒤 스트림으로부터 순차적으로
읽어 처리합니다.

그래서 grep 성능은 regex 성능에 달려있지요.
복잡하지 않은 정규 표현, 특히 단순한 문자열을 비교하는데는
패턴 비교에 필요한 오버헤드가 거의 없다고 봐야겠죠.

Orion Project : http://orionids.org

sh.의 이미지

제가 가진 오렐리의 '정규표현식 완전 해부와 실습'에 보면 grep 에서 사용하는 정규표현식 엔진은 '전통적인 NFA'형이라고 나와 있네요. GNU grep/egrep의 경우에는 NFA/DFA 혼합형이라고 하고요...

에 또 참고로...

Quote:
헨리 스펜서가 1986년에 공개한 정규 표현식 루틴 버전 8은 거의 1,900줄에 달하는 C코드로 작성되었으며 톰 로드가 1992년에 발표한 POSIX NFA 패키지 rx(GNU sed 등에서 쓰임)는 무료 4,500행을 넘어간다.

NFA와 DFA를 모두 활용하기 위해 GNU grep 버전 2.4.2에서는 완벽하게 작동하는 두 개의 엔진을 사용(코드 분량은 약 8,900행)하며 Tcl의 DFA/NFA 복합 엔진의 코드는 약 9,500행에 달한다.

그리고

Quote:
GNU grep 에서는 간단하면서도 효율적인 방법을 택하고 있다. 보통은 DFA를 쓰지만 백레퍼런스를 쓸 때는 NFA로 바꾸는 것이다. ...

이런 내용들이 언급되어 있네요.

그런데 단순히 grep 'LocationCache' allLogFiles 같은걸 했을때는 다른 분들이 말씀하신 것처럼 읽는 속도에 달린것 같고.. 좀 더 복잡한 패턴을 매치했을 때를 비교해봐야 할것 같네요. 그런데 어차피 grep 은 한줄씩만 비교를 하니까 극도로 복잡한 패턴을 찾거나 한 라인이 엄청 길지 않은 바에는 별로 많은 차이는 없을것 같습니다.

enterid의 이미지

검색 할 문자가 7글자라고 할 때

앞에 있는 첫문자를 비교해서 다를 경우

나머지 6문자는 무시하고

그 다음 부터 검색하는 방식으로 하면 (다를 경우 바로 바로 건너 뛰는거죠)

최소한 3~4배는 빨라 질것 같은데요..

최종호의 이미지

bs0048 wrote:
그런데 단순히 grep 'LocationCache' allLogFiles 같은걸 했을때는 다른 분들이 말씀하신 것처럼 읽는 속도에 달린것 같고.. 좀 더 복잡한 패턴을 매치했을 때를 비교해봐야 할것 같네요. 그런데 어차피 grep 은 한줄씩만 비교를 하니까 극도로 복잡한 패턴을 찾거나 한 라인이 엄청 길지 않은 바에는 별로 많은 차이는 없을것 같습니다.

패턴이 엄청나게 복잡하다고 해서 처리에 더 많은 시간이 걸리지는 않습니다.
초기 nfa/dfa를 구성하는 시간이 조금 더 걸릴 수는 있지만 일단 nfa/dfa가 구성되어 있다면 그때부터는 동일합니다.
'LocationCache' 와 같은 경우는 nfa/dfa를 구성 안하고 그대로 부분문자열 찾는 알고리즘을 적용시킬 수 있을텐데,
속도는 nfa/dfa를 썼을 때보다 빠를지는 모르겠습니다.

mr.lee의 이미지

최종호 wrote:

패턴이 엄청나게 복잡하다고 해서 처리에 더 많은 시간이 걸리지는 않습니다.

네.. 말씀하신대로 nfa/dfa 트리를 추적해 나가는 과정이야 패턴이 복잡하던 단순하던 똑같은 시간이 걸리겠지만 트리의 길이(깊이)에 따라 일치함이 판정되기까지는 트리탐색을 더 해가야 하므로 분명 시간은 더 걸리겠지요.

헌데 file read는 어떤식으로 하고 있을까요?

mmap 에서 한라인씩 사용한다면. 라인을 검증하기 위해 '\n'에 대한 비교도 해야 할터인데. 헌데 mmap의 성능이 어느정도일가요? 다른 기법을 쓰고 있을것 같기도 하네요..

sh.의 이미지

최종호 wrote:
bs0048 wrote:
그런데 단순히 grep 'LocationCache' allLogFiles 같은걸 했을때는 다른 분들이 말씀하신 것처럼 읽는 속도에 달린것 같고.. 좀 더 복잡한 패턴을 매치했을 때를 비교해봐야 할것 같네요. 그런데 어차피 grep 은 한줄씩만 비교를 하니까 극도로 복잡한 패턴을 찾거나 한 라인이 엄청 길지 않은 바에는 별로 많은 차이는 없을것 같습니다.

패턴이 엄청나게 복잡하다고 해서 처리에 더 많은 시간이 걸리지는 않습니다.

그렇군요. 책보고 아는척 하다가 딱걸렸습니다 :o
혹시 nfa/dfa에 대해서 좀 더 자세히 설명해 주신다면 감사하겠습니다 --) __) 꾸벅

vacancy의 이미지

사실 NFA/DFA 생성 때문에 grep 속도가 좌우되진 않죠.
보통 pattern은 전체 text에 비해 훨씬 짧으니까요.
대부분은 text에서 linear scan할 때 드는 시간입니다.
그중에서도 많은 비중을 차지하는 건 디스크에서 읽는 시간이겠죠.

많은 운영체제들이 섹터 n을 읽으라고 하면
달랑 섹터 n만 읽지는 않습니다.
그 다음 섹터라거나 해서 몇개를 미리 읽어놓죠. ( read ahead )
물론 DMA를 쓰기 때문에 첫 섹터를 읽는 시간을 제외하고는
CPU가 일을 하는 동안 읽을 것이기 때문에 성능을 극대화할 수 있습니다.

다른 이유는 잘 모르겠네요.

최종호의 이미지

SaNha wrote:
최종호 wrote:

패턴이 엄청나게 복잡하다고 해서 처리에 더 많은 시간이 걸리지는 않습니다.

네.. 말씀하신대로 nfa/dfa 트리를 추적해 나가는 과정이야 패턴이 복잡하던 단순하던 똑같은 시간이 걸리겠지만 트리의 길이(깊이)에 따라 일치함이 판정되기까지는 트리탐색을 더 해가야 하므로 분명 시간은 더 걸리겠지요.

제 생각으로는 dfa 구현은 알파벳과 스테이트로 구성된 테이블
(또는 효율을 높이기 위한 변형된 테이블. 예를 들어, 일반 텍스트파일에서
'ab*' 라는 식을 찾기 위해서 256개의 알파벳에 대한 전이를 모두 구축한다는 것은 낭비겠죠?
심볼정규화나 변형된 테이블검색알고리즘을 쓸 듯 합니다.)을 사용할 것 같습니다.
구현자의 마음이겠지만 구현 자료구조로 트리를 사용하지는 않을 것이란 생각이 듭니다.

혹시, 말씀하신 트리탐색이 dfa를 그래프(트리)로 상정하시고,
일치함이 판정될 때까지의 그래프의 워크(walk) 의 길이가,
패턴이 복잡한 경우에 일반적으로 길 수 있기 때문에 시간이 더 걸린다는 말씀이라면,
패턴의 복잡도와 워크의 길이는 상관관계가 그리 크지 않다는게 제 생각입니다.
'a' 라는 아주 단순한 패턴도 패턴이 일치, 불일치함을 결정하기 위해 소모되는 문자열의 길이는 전체 입력문자열의 길이만큼 될 수 있고,
'^( ([^t] | $) | t ( [^o] | $ ) | to ([^p] | $ ) )'
와 같은 다소 복잡해 보이는 패턴도 일치, 불일치를 위해 소모되는 문자열은 최대 3개죠.

사실, 일치, 불일치가 결정되어도 줄끝까지 출력하기 위해서
나머지 부분을 모두 스캔해야 하긴 하겠죠.

bs0048 wrote:
그렇군요. 책보고 아는척 하다가 딱걸렸습니다
혹시 nfa/dfa에 대해서 좀 더 자세히 설명해 주신다면 감사하겠습니다 --) __) 꾸벅

헛.. 이런 가혹한 답글을 다시다니... :?
오토마타 책이나 구굴님을 먼저 살펴주신 후 같이 얘기하고자 하시는 부분을 좁혀 주심이... :cry: