Почему туалет такой медленный?

Почему утилита wc такая медленная?

Когда я запускаю его для большого файла, это занимает примерно в 20 раз больше времени, чем 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

Это не просто странное граничное условие, вызванное тем, что файл заполнен нулями, я вижу такую ​​же разницу в производительности, даже если файл заполнен случайными данными или является текстовым файлом.

(это на Ubuntu 13.04, 64 бит)

Итак, я пошел к источнику, и похоже, что медлительность заключается в обработке двухбайтовых символов. По сути, для каждого прочитанного символа необходимо вызвать его, mbrtowc()чтобы попытаться преобразовать его в широкий символ, затем этот широкий символ проверяется, чтобы определить, является ли он разделителем слов, разделителем строк и т. Д.

Действительно, если я изменю свою LANGпеременную локали по умолчанию en_US.UTF-8(UTF-8 является многобайтовым набором символов) и установлю ее на " C" (простой однобайтовый набор символов), wcона сможет использовать однобайтовую оптимизацию, что значительно ускоряет ее, займет всего около четверти, как и раньше.

Кроме того, он должен только проверять каждый символ, если он выполняет подсчет слов ( -w), длины строки ( -L) или символа ( -m). Если он выполняет только подсчет байтов и / или строк, он может пропустить обработку широких символов, а затем он работает очень быстро - быстрее, чем md5sum.

Я побежал через gprof, и функции, которые используются для обработки символов мультибайтные ( mymbsinit(), mymbrtowc(), myiswprint(), и т.д.) занимают около 30% только во время выполнения, а также код , который шаги через буфер является гораздо более сложным , поскольку он должен обрабатывать шаги переменного размера через буфер для символов переменного размера, а также вставлять любые частично завершенные символы, которые охватывают буфер, обратно в начало буфера, чтобы его можно было обработать в следующий раз.

Теперь, когда я знаю, что искать, я нашел несколько постов, в которых упоминается медлительность utf-8 с некоторыми утилитами:

/programming/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08 / 2000x эффективность выигрыша /

Просто предположение, но вы сравниваете яблоки с апельсинами в отношении того, что wcделает с тем, что md5sumделает.

задание md5sum

Когда md5sumобрабатывает файл, он просто открывает файл как поток, а затем начинает запускать поток через функцию контрольной суммы MD5, которая требует очень мало памяти. По сути это связано с процессором и дисковым вводом / выводом.

Задача туалета

При 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он должен решить, что такое граница слова и линии, и отслеживать количество вхождений, которые он видит.

Дополнительные wc обсуждения

Я нашел эту проблему кодирования с 2006 года, которая обсуждает реализацию wcв .NET. Трудности довольно очевидны, когда вы смотрите на некоторые псевдокоды, так что это может помочь пролить свет на то, почему wcэто происходит намного медленнее, чем другие операции.