19

Why is the wc utility so slow?

When I run it on a large file, it takes about 20 times longer than md5sum:

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

It's not just a weird edge condition cause by the file being full of nulls, I see the same difference in performance even if the file is filled with random data or is a text file.

(this is on Ubuntu 13.04, 64 bit)

Improve this question
1
  • Note for those who only care about line count: wc -l <filename> is much faster on very large files.
    – E L
    Oct 29, 2018 at 16:36

2 Answers 2

Reset to default
30

So I went to the source, and it looks like the slowness is in handling double byte characters. Essentially, for every character read in, it needs to call mbrtowc() to try to convert it to a wide character, then that wide character is tested to see if it's a word separator, line separator, etc.

Indeed, if I change my locale LANG variable from the default en_US.UTF-8 (UTF-8 is a multibyte character set) and set it to "C" (simple single byte character set), wc is able to use single-byte optimizations, which speeds it up considerably, taking only about a quarter as long as before.

Additionally, it only has to check each character if it's doing word (-w), line length (-L) or character (-m) counts. If it's only doing byte and/or line counts, it can skip the wide character handling and then it runs extremely quickly -- faster than md5sum.

I ran it through gprof, and the functions that are used to handle the multibyte characters (mymbsinit(), mymbrtowc(), myiswprint(), etc) are taking up about 30% of the execution time alone, and the code that steps through the buffer is much more complex because it has to handle variable sized steps through the buffer for variable sized characters, as well as stuffing any partially completed characters that span the buffer back to the beginning of the buffer so it can be handled the next time around.

Now that I know what to look for, I found a few posts mentioning the utf-8 slowness with some utilities:

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/

Improve this answer
10
  • 2
    Oh, just realized you are OP. :p
    – Ivan Chau
    Oct 18, 2013 at 7:35
  • 2
    Although this is the most upvoted answer, it is irrelevant. md5sum will never allow you to count the word number and wc will not compute the md5 hash of the file! It's like asking why is my car so slow compared to my typewriter when writing text.
    – user49468
    Oct 18, 2013 at 9:46
  • 7
    @user49468: It's reasonable to assume that both are IO-bound, as both have to read each and every byte of the input file. This answer proves that wc in fact is CPU-bound, when processing multi-byte characters.
    – MSalters
    Oct 18, 2013 at 11:26
  • 2
    @user49468: wc and md5sum may do different things, but both read a file and do a relatively simple computation, one calculates a checksum, one counts bytes, word separators and newlines. Well, I thought it was simple, but hadn't factored in the extra complexity of multibyte character sets. It's more like asking "Why is my car 20 times faster at going to the store than my minivan?" You would expect some difference between the two, but not a 20X difference.
    – Johnny
    Oct 18, 2013 at 15:14
  • 1
    @Johnny you car/minivan comparison lacks the aspect that both are designed to transport you to the store. So a speed comparison is in place. Comparing your car to the stripe painting vehicle is more suitable. Just because both use the streets their speeds is not relevant as the stripe painter is not suited to go shopping and vice-versa.
    – user49468
    Oct 21, 2013 at 8:09
1

Just a guess but you're kind of comparing apples to oranges with respect to what wc is doing vs what md5sum is doing.

md5sum's task

When md5sum processes a file it simply opens the file as a stream and then starts running the stream through the MD5 checksum function which needs very little memory. It essentially CPU & disk I/O bound.

wc's task

When wc runs it is doing a lot more then just parsing the file a character at a time. It has to actually analyze the structure of the file, lines at a time making determinations as to where boundaries between characters are and whether it's a word boundary or not.

Example

Think of the following strings and how each of the algorithms would have to move through them as they parse them:

“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow     \n\n\n    great”
“it was a man-eating shark.”

For MD5, it trivially moves through these strings a character at a time. For wc it has to decide what's a word & line boundary and keep track of the number of occurrences that it sees.

Additional wc discussions

I found this coding challenge from 2006 that discusses implementing wc in .NET. The difficulties are pretty obvious as you look at some of the pseudo code, so this might help to begin to shed light on why wc appears to be so much slower than other operations.

Improve this answer
6
  • 2
    You're describing something different than the standard Unix wc command (at least, not the one that comes with Ubuntu). That wc doesn't count unique words, just words, so "hello hello world" is 3 words, not 2.
    – Johnny
    Oct 18, 2013 at 3:18
  • Based on this theory it sounds like a simpler task, like counting lines, would go more quickly. Does changing 'wc' to specify a line count modify the results substantially? 'wc -l'
    – Joshua Miller
    Oct 18, 2013 at 3:50
  • @Johnny - I never said it counts unique words you said that. wc counts multiple things as it parses the file. It counts the number of words, lines, and bytes as it parses the file. Read the man page!
    – slm ♦
    Oct 18, 2013 at 4:04
  • @JoshuaMiller - Unclear whether telling wc to only count lines limits it's internal parsing so that it only counts these things or just only reports the lines results, even though it still counted everything.
    – slm ♦
    Oct 18, 2013 at 4:05
  • @slm You did say it counts unique words, your example says “Hello! Greg” results in Hello 1, Greg 1, i.e. counts for each word. And the .Net project you linked to says "One of its main tasks is to go through a set of data and count the number of repetitions of a given word. For instance given the sentence “Hello, yes hello” it would tell you that the word Hello was used twice and that the word yes was used once." While in reality the result of echo "Hello, yes hello" | wc --words, is "3", not "Hello: 2, Yes: 1"
    – Johnny
    Oct 18, 2013 at 4:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .