Я решил использовать преимущества нескольких ядер в реализации алгоритма DEFLATE . MArc Adler сделал нечто похожее в коде C с PIGZ (параллельный gzip). Я поставил философский эквивалент, но в библиотеке управляемого кода, в DotNetZip v1.9 . Это не порт PIGZ, а похожая идея, реализованная независимо.
Идея DEFLATE состоит в том, чтобы сканировать блок данных, искать повторяющиеся последовательности, создавать «словарь», который отображает короткий «код» для каждой из этих повторяющихся последовательностей, а затем генерировать поток байтов, где каждый экземпляр одного из повторяющиеся последовательности заменены на «код» из словаря.
Поскольку сборка словаря требует значительных ресурсов процессора, DEFLATE является идеальным кандидатом для распараллеливания. Я использовал подход типа Map + Reduce, где я делю входящий несжатый bytestreeam на набор меньших блоков (map), скажем, по 64 КБ каждый, а затем сжимаю их независимо. Затем я объединяю полученные блоки вместе (уменьшаю). Каждый 64-килобайтный блок сжимается независимо, в своем собственном потоке, без учета других блоков.
На двухъядерной машине этот подход сжимает примерно 54% времени традиционного последовательного подхода. На компьютерах серверного класса, с большим количеством доступных ядер, он может потенциально обеспечить еще лучшие результаты; без сервера я лично не проверял, но люди говорят, что это быстро.
Существуют накладные расходы времени выполнения (ЦП), связанные с управлением несколькими потоками, накладные расходы памяти времени выполнения, связанные с буферами для каждой команды, и накладные расходы данных, связанные с объединением блоков. Таким образом, этот подход окупается только для больших потоков. В моих тестах выше 512к, это может окупиться. Ниже этого лучше использовать последовательный подход.
DotNetZip поставляется в виде библиотеки. Моей целью было сделать все это прозрачным. Таким образом, библиотека автоматически использует дополнительные потоки, когда размер буфера превышает 512 КБ. Приложение не должно ничего делать, чтобы использовать потоки. Это просто работает, и когда потоки используются, это волшебно быстрее. Я думаю, что это разумный подход для большинства библиотек, используемых приложениями.
Было бы неплохо, если бы компьютер умел автоматически и динамически использовать ресурсы на парализуемых алгоритмах, но сегодня реальность такова, что разработчики приложений должны явно кодировать параллелизацию.