wc 유틸리티가 왜 그렇게 느린가요?
대용량 파일에서 실행하면 md5sum보다 약 20배 더 오래 걸립니다.
MyDesktop:/tmp$ dd if=/dev/zero bs=1024k count=1024 of=/tmp/bigfile
1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB) copied, 0.687094 s, 1.6 GB/s
MyDesktop:/tmp$ time wc /tmp/bigfile
0 0 1073741824 /tmp/bigfile
real 0m45.969s
user 0m45.424s
sys 0m0.424s
MyDesktop:/tmp$ time md5sum /tmp/bigfile
cd573cfaace07e7949bc0c46028904ff /tmp/bigfile
real 0m2.520s
user 0m2.196s
sys 0m0.316s
이는 파일이 null로 채워져 있기 때문에 발생하는 이상한 가장자리 조건이 아닙니다. 파일이 임의의 데이터로 채워져 있거나 텍스트 파일인 경우에도 동일한 성능 차이를 보았습니다.
(우분투 13.04, 64비트 기준)
답변1
그래서 소스 코드를 살펴보니 2바이트 문자를 처리하는 데 속도가 느린 것 같습니다. 기본적으로, 읽은 모든 문자에 대해 mbrtowc()
와이드 문자로 변환을 시도하는 함수를 호출 한 다음 해당 와이드 문자를 테스트하여 단어 구분 기호, 줄 구분 기호 등인지 확인해야 합니다.
실제로 LANG
기본 로캘 변수 (UTF-8은 다중 바이트 문자 집합)를 변경하고 " "(간단한 단일 바이트 문자 집합) en_US.UTF-8
로 설정하면 단일 바이트 최적화를 사용할 수 있어 속도가 크게 향상됩니다. 속도는 이전 시간의 약 1/4 정도만 소요됩니다.C
wc
또한 각 문자가 단어( -w
), 줄 길이( -L
) 또는 문자( -m
)로 계산되는지 간단히 확인합니다. 바이트 및/또는 줄 계산만 수행하는 경우 와이드 문자 처리를 건너뛰고 매우 빠르게 실행될 수 있습니다 md5sum
. 즉 .
실행했는데 멀티바이트 문자( , , 등) gprof
를 처리하는 함수는 실행 시간의 약 30%밖에 걸리지 않았고, 버퍼를 통과하는 코드는 가변 크기 문자를 처리해야 했기 때문에 훨씬 더 복잡했습니다. 버퍼의 단계를 수행하고 버퍼의 모든 부분에서 완료된 문자를 버퍼의 시작 부분으로 다시 채워 다음에 처리할 수 있도록 합니다.mymbsinit()
mymbrtowc()
myiswprint()
이제 무엇을 찾아야 할지 알았으니 UTF-8에서 일부 유틸리티가 느리다는 내용을 언급하는 몇 가지 게시물을 발견했습니다.
https://stackoverflow.com/questions/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08/2000x-performance-win/
답변2
단지 추측일 뿐입니다. 하지만 사과와 오렌지를 비교하고, wc
진행 중인 작업과 md5sum
진행 중인 작업을 비교하는 것입니다.
md5sum 작업
파일을 처리할 때 md5sum
파일을 스트림으로 열고 전달을 시작합니다.MD5 체크 기능메모리가 거의 필요하지 않습니다. 이는 본질적으로 CPU 및 디스크 I/O 제한입니다.
화장실 작업
실행 되면 wc
파일을 한 번에 한 문자씩 구문 분석하는 것 이상의 작업을 수행합니다. 실제로 파일의 구조를 한 번에 한 줄씩 분석하여 문자 간의 경계가 어디에 있는지, 단어 경계인지 여부를 확인해야 합니다.
예
다음 문자열과 이를 구문 분석할 때 각 알고리즘이 문자열을 통과하는 방법을 고려하세요.
“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow \n\n\n great”
“it was a man-eating shark.”
MD5의 경우 이러한 문자열을 통해 한 번에 한 문자씩 이동합니다. 왜냐하면 wc
어떤 단어와 줄 경계가 무엇인지 결정하고 얼마나 많은 항목이 나타나는지 추적해야 하기 때문입니다.
기타 화장실 토론
나는 이것을 찾았다코딩 챌린지 2006wc
.NET에서의 구현에 대해 논의합니다 . 일부 의사 코드를 보면 어려움이 매우 분명하므로 wc
이것이 다른 작업보다 훨씬 느린 이유를 설명하는 데 도움이 될 수 있습니다.