pbzip2
31.01.2009 22:56:35Читая тов. Федорчука наткнулся на:
Правда, существует реализация механизма bzip2, оптимизированная для SMP-систем — Parallel BZIP2 (pbzip2), которая теоретически умеет это делать. В репозиториях Zenwalk’а её нет, собирать мне её было лениво, а по наблюдениям из FreeBSD — никакого выигрыша в скорости по сравнению с обычным bzip2 она не даёт, напротив, обеспечивая еле заметный, но всё-таки проигрыш.
И не поверил своим глазам. AFAIK, задачи сжатия должны очень даже неплохо параллелиться, так что решил проверить, благо, в Debian pbzip2 имеется в репозитории.
За три запуска средние времена сжатия 80-мегабайтного архива tar:
$ time bzip2 -c t2-trunk.tar > /dev/null real 0m12.763s user 0m12.508s sys 0m0.062s $ time pbzip2 -c t2-trunk.tar > /dev/null real 0m6.327s user 0m12.224s sys 0m0.204s
Разжатие даёт порядка 1.7 против 1.1 секунды, опять же, в пользу pbzip2.
Камушек Core 2 Duo T7200, ядро — 2.6.28, ФС — XFS поверх шифрованного раздела на LVM, который, в свою очередь, лежит на RAID0. Впрочем, в данном случае 80 Мб явно брались из кэшей и явно я их никуда не записывал, сравнивая чисто алгоритмы. Но и задержки, вносимые записью, такие разрывы ни коим образом не выравнивают.
Алексею спасибо за наводку на полезную штуку. 
Странно, кстати, что она механизм альтернатив Debian не использует, надо бы заместить штатный медленный bzip2.
P.S. Ложка дёгтя. Оборотная сторона этого дела в размерах получающихся архивов. А именно 5,28 Мб супротив 5,55, уже не в пользу pbzip2. Впрочем, это и при 7,77 на тех же данных у gzip, но с сопоставимой скоростью.
P.P.S. Да, и распаковка ускоряется только если файл сжат pbzip2. В принципе, я покопался в памяти и действительно вспомнил, что не так всё просто именно со сжатием. Покопался в мануале pbzip2 и, действительно, он вход тупо делит на несколько независимых частей, каждая из которых сжимается самостоятельно. Как результат, именно, что степень сжатия страдает, да. Но, скорость. Но, размеры.
P.P.P.S. Однако, если покрутить ручками настройки, то можно таки и рыбку съесть, и это самое:
$ time pbzip2 -b30k -f t2-trunk.tar real 0m7.628s user 0m13.859s sys 0m0.215s $ ls -lh t2-trunk.tar.bz2 -rw-r--r-- 1 rik rik 5,2M Янв 31 22:39 t2-trunk.tar.bz2
И сжатие быстрее, и размер таки меньше.
P.P.P.P.S. Хотя, последний трюк не на каждом наборе входных данных повторишь столь же эффектно.
31.01.2009 23:42:56
Насколько представляю себе — сжатие bzip состоит из двух этапов. сперва идет преобразование Броуза-Уиллера, после чего идет сжатие по Хаффмену. Честно говоря не вижу причин, почему бы эти этапы на несколько ядер не разнести.
Хотя архиваторы не мой профиль, могу что-то и путать
31.01.2009 23:51:12
В том-то и дело, что это, так сказать, подход _конвееризации_, который нормально не реализуем в современных системах (пару потоков нарисуешь — дальше что? как масштабироваться на 4 ядра? где пилить на этапы конвеера? как решать вопросы с запуском на 2, 4, 8 и далее ядрах, гонять всё возможное количество потоков или пихать кучу вариантов распила конвеера? :)). Реализован, соответственно, существенно более примитивный подход.
02.02.2009 10:13:40
Весь парадокс еще в том, что нормальная многоядерность заведомо победит у любой оптимизации.
Но юникс мир во многом существует еще по старинке таксказать. Многие утилиты практически неизменными дошли до нас с прошлого века. 
02.02.2009 11:03:21
И еще… по правильному надо оперировать не потоками. А данными.
Типа того — что есть входной поток… который можно поделить на 10 блоков для алгоритма BWT, 10 ядер сделают это быстрее чем одно — однозначно.
Не знаю точно как там реализован Хаффмен, но если таблица у каждого блока своя — то абсолютно те же яйца, вид сбоку.
Сколько для этого всего потребуется памяти — вопрос второй. Память нынче дешовая.
Но если оперировать потоками — то это автоматически сужает рамки нашего вображения. Этот поток на BWT, этот поток на хаффмена? чем же загрузить 30 ядер — не понятно…
Реальность наверное еще страшнее. Паралельно с обработкой BWT строится дерево для хаффмена и в результате разделить это на два ядра становится практически невозможно!