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 строится дерево для хаффмена и в результате разделить это на два ядра становится практически невозможно!