MCP
Показаны сообщения с ярлыком сжатие. Показать все сообщения
Показаны сообщения с ярлыком сжатие. Показать все сообщения

воскресенье, 28 августа 2016 г.

Моя месть node_modules

К node.js у меня странные чувства. С одной стороны, это простая и очень быстрая среда для разработки приложений, которая работает на всём, что шевелится. С другой, большинство библиотек написаны на таком уровне, что программисты на C# и прочих серьёзных языках хренеют от ужаса. Впрочем, об этом другой раз.

Один из больших, бесящих пунктов у ноды, это папка node_modules. С зависимостями зависимостей и зависимостями зависимостей зависимостей. И эти файлы ещё любят вылезать за 255 символов, что приводит винду в истерику (да, в npm3 это таки пофиксили). И кроме всего прочего, этот миллиард мелких файлов ещё дофига копируется. А копируется он часто, обычно каждый билд. Т.е. тупое перемалывание толпы файлов.

Мне надоело с этим мириться, и я пошёл мучать исходники ноды, чтобы сделать одну подлую вещь. Оказалось, что мелким хаком обойтись не получилось, надо взять костыль побольше, но для node это вполне нормально, и после этого можно избавиться от этой долбаной папки.

В общем, нарисовал я проект с гениальным называнием nmisf (node modules in single file). Не буду переписывать его документацию, просто скажу, что вам надо один раз запустить создание бандла и папка node_modules превратится в один файл, в котором будут только нужные файлы, да ещё и без дублей (а с учётом зависимостей зависимостей зависимостей, это актуально). Ну и рядышком ещё один файл для индекса. В итоге, два файла вместо толпы. Что положительно сказывается на времени копирования, ну и количестве хлама на диске.

Ну а после того, как вы сделали эти файлы, удаляйте node_modules, и загружайте модуль nmisf в своё приложение. Он подменит лоадер для ноды, и всё будет шоколадно (правда нативные модули будут распаковываться всё равно, есть технические ограничения).

В общем, вэлкам на тестирование данной библиотеки. На мой взгляд, весьма интересная вещь, и стоит её попробовать. В понедельник заюзаю на боевом проекте (пока никто не видит) и посмотрю на время билдов и запуска. Думаю, результат всех порадует.

воскресенье, 7 августа 2016 г.

Мегафичи моего архиватора

Я тут всё хвастаюсь, что делаю свой архиватор (и уже конкретно задолбал всех окружающих), а он всё делается, правда как-то весьма не спеша. В общем, решил рассказать про пару фич, которые на мой взгляд относительно уникальны для подобной задачи.

Полное шифрование без раскрытия информации

Т.е. вообще ничего не говорим. Даже что это архив нужного типа. Безопасность и красота. Есть рандомный набор байт, а является ли он архивом, или ещё чем-то — науке неизвестно. При этом оставлено обычное шифрование, которое можно оптимизировать в плане скорости, но оно раскрывает базовую информацию об архиве, что для обычных ситуаций не проблема, а наоборот удобство, но ведь надо периодически делать фичи и для параноиков.  

Управляющие блоки 

Вот с этим у других совсем грустно. Смысл в том, что у нас есть поток, который посылает много данных, мы их сжимаем, передаём дальше. Всё хорошо, но тут нам потребовалось послать дополнительную информацию, которая хоть и относится к этим данным, но по факту является метой. Что с этим можно сделать? Можно открыть другой поток, что решает все проблемы, но усложняет логику. Можно данные бить на блоке и в начале каждого блока ставить флажок о типе данных. Неплохое решение, но опять же, всё усложняет, плюс портит сжатие данных, т.к. данные разнородные.
В моём формате архиватора дофига места для подобных флагов, поэтому вы можете вместе с основными данными послать управляющие. Они не будут сжиматься, а пойдут сбоку, позволяя контролировать поток. Может быть (да и скорее всего), название выбрано неудачно, но смысл в том, что можно в один поток отправить два независимых набора данных, которые не очень сильно будут друг-другу мешать. При этом данные концептуально разные, так что у них есть логический смысл.

Восстановление данных (не сделано)

Мой архиватор по умолчанию использует CRC32C для проверки целостности, но хочется ещё и восстанавливать слегка повреждённые байты. И у меня есть прототип кода. Мало у кого есть подобное. У меня будет. Но пока не сделано, и это печально. Как будет сделано, буду хвалиться.


К чему я всё это написал? (Конечно же похвастаться!) К тому, что несовершенство мира раскрывается с каждой маленькой задачей. Вначале оказалась проблема с потоками и флашем, что привело к написанию моего архиватора, потом отсутствие управляющих последовательностей, восстановления данных... Что же будет дальше? Что ещё отсутствует из забавных фич в текущем наборе библиотек? Что ещё волшебного стоит мне добавить в архиватор?

воскресенье, 29 мая 2016 г.

Проблемы архиваторов, о которых никто не говорит

Я тут давно начал "писать" архиватор. Ну, т.е. как начал, сделал самое интересное, а допинать до конца терпения не хватило. Точнее почти хватило, но меня не устроили результаты, а, как известно, первая заповедь перфекциониста-прокрастинатора: лучше сделать хорошо, но никогда, чем плохо, но сейчас!

В общем, я полтора года не трогал свой архиватор, а тут решил, что всё-таки стоит пожертвовать 0.2% степени сжатия и 30МБ/c скорости, и выбрать простую и дубовую реализацию, так что. архиватор почти дописан, осталось сделать последний рывок и вычистить все баги, и добавить лоска. Впрочем, про сам мой алгоритм расскажу как-нибудь в другой раз.
Для начала расскажу про одну небольшую проблему, из-за которой, я начал писать архиватор, а не тупо взял готовый. Проблема весьма специфическая, но если вы в неё встрянете, то будет плохо, очень плохо.

В общем, вкратце, проблема называется Flush. Т.е. нормальная поддержка архиватором данной команды. Что это значит? А то, что большинство реализаций архиваторов внутри работают с блоками определённой длины (самой любимой) независимо! Т.е. команда Flush приводит к тому, что внутренний буфер отправляется в нижележащий стрим. И если в буфере много данных, то и проблем нет, а если мало, то результат становится очень неприятным с точки зрения качества сжатия.

Но ситуация может быть ещё хуже, архиваторы могут тупо проглатывать команду Flush (передаю привает реализации GZip в .NET, да она проглатывает Flush)! Что это значит? Это значит, что в некоторых задачах вы в принципе не можете использовать данную реализацию.

Собственно, про задачи-то я и забыл рассказать. Представьте, у вас есть TCP канал, в котором вы обмениваетесь сообщениями, например JSON'ом (так сейчас модно). Сообщения вам надо проталкивать на другую сторону и очень хочется их сжимать. А поскольку сообщения зависимые и похожие, то и сжимать зависимо. Проталкивать их надо командой Flush, что очевидно, а сообщения у вас небольшие. Что получается? Смотрите картинку:

В качестве тестовых данных, дамп википедии в 100 Мб (один из стандартных шаблонов для сжатия). По оси X - размер блока, который флушится, по оси Y - степень сжатия.
Что видно? ЧТо на блоке в 16 байт накладные расходны на заголовок превысили все ожидания (только GZip рулит за счёт мелкого заголовка). В дальнейшем, всё становится лучше, но до блока в 16Кб счастья особого нет. Т.е. сжимается, что уже неплохо, но могло быть и лучше.

Вот, если для примера взять бекап какой-нить базы (какой уже не помню, но это настоящая продуктовая база была). Особенность бекапа базы — очень выражена периодичность на 64Кб, да и вообще много похожести. Хотя флушить бекап базы не очень логично, но для примера пойдёт:

Результаты те же, только более явно выражены. И эта явность как раз и намекет, что 64Кб — это таки нашё всё. А лучше больше. Тот же график, но у него подрезано начала, чтобы был лучше виден масштаб:

Тут видно, что LZ4 за счёт максимального блока в 262Кб (по дефолту у данной реализации), вполне неплохо идёт дальше, но такой размер блока уже как-то лучше подходит для статичных данных, а там можно и более серьёзные аргументы, начинающиеся на цифру 7 применить.

В общем, цель моего архиватора: сделать так, чтобы Flush'и не оказывали серьёзного влияния, чтобы вы могли использовать архиватор не особо парясь. И как видите, всё вроде бы получается (мой - красненький). 1024 байта уже позволяют его весьма эффективно использовать.

Правда на блок уходит 8 лишних байт... и это меня бесит... Ждите следующий пост через пару лет...

воскресенье, 15 июня 2014 г.

Использование быстрых алгоритмов сжатия в потоковом режиме

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

Начнём по-порядку.
  • zlibnet — считает метод Flush сигналом для записи финального блока, что приводит к некорректному поведению. Надо чинить (а лучше переписать самому, где там мой блокнотик?)
  • SharpCompress — любитель вызывать метод записи с длиной в 0 байт, что, имхо, весьма неаккуратно. Может на некоторые потоки создавать бессмысленную нагрузку
  • SharpZipLib — никаких нареканий
  • Встроенный GZip — буфер в 8Кб, полностью игнорируется Flush, оказывается для потоков его использовать нельзя.
  • Snappy — блочный алгоритм, блоки с префиксом и контрольной суммой, что накладывает отпечаток на возможностях
  • Snappy for .NET — нет реализации стримов, пропускаем
  • Snappy.NET — блок прибит гвоздями в 64Кб, Flush вызывает запись независимого блока. Т.е. частый флуш приведёт к потере сжатия и увеличению объёма
  • LZ4 — тоже блочный, при уменьшении блока резко падает степень сжатия, поведение аналогично Snappy. В реализациях (lz4-net и LZ4.NET) проблем не обнаружил (кроме самого факта с проблемами потока). Из хороших новостей — потоковое API для LZ4 разрабатывается (прямо в тот момент, как я пишу этот текст). Оно ещё не стандартизировано, но шансы есть, что будет всё круто.
  • LZF — я его достал с дальнего ящика и смотрю на него. Его особенность, что сжатие позволяет писать данные хоть по байту (и читать сжатые по байту). Правда исходные данные пока выглядят блочными, но думаю это можно будет поправить, если поисследовать алгоритм. 

суббота, 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 сидит где-то посередине и при своей скорости подходит для всего мало-мальски сжимаемого.

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