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

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

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

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

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

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

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

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

에 또 참고로...

그리고

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

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

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

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

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

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

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