MCP

суббота, 14 июня 2014 г.

Выбор быстрых алгоритмов сжатия под .NET

Для начала, пара таблиц для привлечения внимания:

Быстрый компьютер:
MemCopy:         1561.050       1709.7218        100.000%
GZipStd:           66.736        221.6318          6.335%
#ZipLib.Gzip:      52.800        136.0018          6.358%
zlibnet:          100.572        466.2888          6.500%
SharpComp.GZip:    52.568        154.7598          6.501%
Snappy.Net:       970.382        944.8468         13.312%
SnappyforNet:     997.337       1795.2078         14.499%
lz4net/CC:        485.191       1122.0048         10.740%
lz4net/MM:        997.337       1158.1988         10.740%
lz4net/N:         535.883       1122.0048         10.740%
lz4net/S:         386.066        690.4648         10.740%
lz4net/HC:         42.794       1282.2918          7.751%
LZ4.Net:          997.337       1158.1988         10.896%
QuickLZ:          460.310        528.0028          8.032%
LZO_1X   :       1683.082       1561.0508         11.824%
LZF     :         272.001        398.9358         13.882%
Медленный компьютер:
MemCopy:          394,551        394,5518        100,000%
GZipStd:           18,006         50,4278          8,738%
#ZipLib.Gzip:      16,137         45,2198          6,358%
zlibnet:           31,086        105,6008          6,500%
SharpComp.GZip:    18,356         46,6898          6,501%
Fail Snappy.Net: Инициализатор типа "Crc32C.NativeProxy" выдал исключение.
SnappyforNet:     260,175        432,5808         14,499%
Fail lz4net/CC: Ссылка на объект не указывает на экземпляр объекта.
Fail lz4net/MM: Ссылка на объект не указывает на экземпляр объекта.
lz4net/N:         218,928        228,6898         10,740%
lz4net/S:         120,484        141,9148         10,740%
Fail lz4net/HC: Ссылка на объект не указывает на экземпляр объекта.
LZ4.Net:          234,668        274,0778         10,896%
QuickLZ:           60,445         65,0448          8,032%
LZO_1X   :        374,001        505,6928         11,827%
LZF     :          44,880         60,3438         13,882%

Это я тестировал различные реализации алгоритмов сжатия и их скорости. Столбцы: скорость сжатия в MB/s, скорость декомпрессии, процент сжатого текста, относительно исходного материала.

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

Собственно, поэтому сразу же выкину из дальнейшего рассмотрения следующие алгоритмы:

  • QuickLZ — проблемы с лицензией,
  • LZO — работает через P/Invoke, мутный враппер, какие-то косяки с дебагом, проблемы с 64 битами не ясно дальнейшее развитие, собственно, его высокие показатели в тестах отчасти связаны с ограниченностью функционала, из-за которого, тест оказался в более выгодном положении относительно некоторых других (я даже не уверен, что он стабильно работает, хотя то что работает хотя бы один раз, это точно, я проверил)
  • LZF — хорош как вариант микро-компрессора (собственно, весь код можно зафигачить в 200 строчек не сильно экономя, при этом результат вполне сносный. Но, если вы не специалист по алгоритмам, не очень рекомендую заниматься этим делом. Хотя, возможно идея довести код до ума, вполне неплохая (надо записать себе в блокнот "обязательно сделать в следующей жизни").
Также в алгоритме не приняли участие: BZip2, LZMA и PPMd (степень сжатия отличная, скорость настолько низкая, что даже ради научного интереса их тут не стоит использовать.

Некоторые алгоритмы вида классического LZ77, не были найдены под .NET, поэтому тоже их пропускаем.

Теперь детально разберу оставшиеся GZip, LZ4, Snappy.

Gzip

Собственно, самый известный алгоритм сжатия, использующийся поголовно везде (хотя правильнее сказать, что алгоритм — Deflate, а GZip — поток с дополнительной метаинформацией). Если вы будете использовать его — у вас не будет никаких проблем с совместимостью, так что он очень хорош в плане требования по памяти и работы в потоковом режиме.
Но с выбором реализации есть некоторые проблемы — если вы сравните две верхних таблицы, то увидите что GZipStd (я так обозвал встроенный в .NET) даёт абсолютно разные варианты. Хитрость в том, что до .NET4.5, реализация GZip в .NET была ужасная, и её использовать стоило только в одном случае — никогда. Сейчас всё изменилось, и если вы пишите под 4.5, то вполне стоит использовать этот вариант, если нет критичного требования по скорости.

Если нужна максимальная скорость, то используйте zlibnet, это P/Invoke wrapper, поэтому он работает весьма шустро. Если у вас нет желания использовать P/Invoke (чуть сложнее деплой и требуется больше прав приложению), используйте SharpCompress, он мне показался чуть более удобным, быстрым и функциональным относительно классического SharpZipLib. Есть ещё библиотека SevenZipLib — P/Invoke wrapper к 7zip, но по внешниему интерфейсу я не очень понял, как работать с GZip, хотя в описании указано.

Snappy

Алгоритм от Гугла, ориентированный на максимальную скорость. Для .NET есть 2 реализации P/Invoke с оригинальными названиями: Snappy for .NET и Snappy.Net. Есть Safe-реализация Snappy.Sharp, но я её даже не пробовал, т.к. судя по всему работы ещё дофига, она полузаброшена, ничего особо не протестировано. Опять же, если есть желание — берите сами и дописывайте, иначе не советую использовать (записал второй пункт в блокнот).

Сам алгоритм очень шустрый (судя по всему, разработка велась с учётом особенностей процессоров и их кеширвоания), но сжатие у него так себе. Также у обоих реализаций есть проблемы. Snappy.Net не работает в 32х битах из-за какой-то ошибки в реализации библиотеки, вычисляющей CRC32 (третий пункт в блокнот — написать автору, что он лох и надо поправить). Snappy for .NET — требует VS2010 runtime, о чём надо помнить (я для тестов подложил нужные dll'ки на тестовый компьютер).
В общем, пока следует использовать с осторожностью, это не Production-решение

LZ4

Один из моих фаворитов, благо скорость отличная, но надо выбрать реализацию. Их две и обе хорошие. lz4-net — P/Invoke wrapper и LZ4.NET, флакон от автора с четырьмя разными реализациями, которые выбираются по приоритету и доступности: Mixed Mode, C++/CLI (требуется установленный VS2010 runtime, проверка идёт по наличию пакета в реестре, а не по DLL), Unsafe, Safe. Также, автор, возможно будет пилить дальше и улучшать свой код.

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

Качество сжатия алгоритма зависит от дополнительного буфера на словарь, который в разных реализациях по дефолту 1Мб и 256Кб, в реальности, 64Кб дают пристойный результат, но и 1Мб не очень жалко для объёмных данных. Имейте в виду.

Заключение

Я, пока в раздумьях по поводу алгоритма и реализации, склоняюсь к GZip в P/Invoke исполнении и LZ4 в комплектном. Надо заранее определиться, какая скорость вам требуется: если вы передаёте огромные данные по сети со скоростью 1МБ/c, то GZip'а вам хватит за глаза, а сжатие будет активно помогать уменьшить объёмы. Если же сеть в гигабит, а данных немного, то со сжатием связываться вообще не стоит. LZ4 сидит где-то посередине и при своей скорости подходит для всего мало-мальски сжимаемого.

Решайте сами, я пока думаю, решение напишу позднее, когда потестирую всё это в продакшене (т.е. возможно, спустя длительное время).

Комментариев нет:

Отправить комментарий