☰

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

tag-icon • tag-icon performance wc
Почему туалет такой медленный?

Почему утилита 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 бит)

решение1

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

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

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

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

Теперь, когда я знаю, на что обращать внимание, я нашел несколько сообщений, в которых упоминается медлительность 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которому нужно очень мало памяти. По сути, он привязан к процессору и дисковому вводу-выводу.

задача wc

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

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

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

Связанный контент