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. Хотя, последний трюк не на каждом наборе входных данных повторишь столь же эффектно.

Много комментариев (4) к заметке “pbzip2”

  1. http://mdf-i.blogspot.com/:

    Насколько представляю себе — сжатие bzip состоит из двух этапов. сперва идет преобразование Броуза-Уиллера, после чего идет сжатие по Хаффмену. Честно говоря не вижу причин, почему бы эти этапы на несколько ядер не разнести.

    Хотя архиваторы не мой профиль, могу что-то и путать 🙂

  2. Роман:

    В том-то и дело, что это, так сказать, подход _конвееризации_, который нормально не реализуем в современных системах (пару потоков нарисуешь — дальше что? как масштабироваться на 4 ядра? где пилить на этапы конвеера? как решать вопросы с запуском на 2, 4, 8 и далее ядрах, гонять всё возможное количество потоков или пихать кучу вариантов распила конвеера? :)). Реализован, соответственно, существенно более примитивный подход.

  3. http://mdf-i.blogspot.com/:

    Весь парадокс еще в том, что нормальная многоядерность заведомо победит у любой оптимизации. 🙂 Но юникс мир во многом существует еще по старинке таксказать. Многие утилиты практически неизменными дошли до нас с прошлого века. 🙂

  4. http://mdf-i.blogspot.com/:

    И еще… по правильному надо оперировать не потоками. А данными.

    Типа того — что есть входной поток… который можно поделить на 10 блоков для алгоритма BWT, 10 ядер сделают это быстрее чем одно — однозначно.

    Не знаю точно как там реализован Хаффмен, но если таблица у каждого блока своя — то абсолютно те же яйца, вид сбоку.

    Сколько для этого всего потребуется памяти — вопрос второй. Память нынче дешовая.

    Но если оперировать потоками — то это автоматически сужает рамки нашего вображения. Этот поток на BWT, этот поток на хаффмена? чем же загрузить 30 ядер — не понятно… 🙂

    Реальность наверное еще страшнее. Паралельно с обработкой BWT строится дерево для хаффмена и в результате разделить это на два ядра становится практически невозможно!

Закомментировать

Вам бы, по-хорошему, зарегистрироваться сначала надобно, прежде чем комментарии оставлять. Но, в порядке исключения, можете попробовать с OpenID проскочить, вдруг.