MCP

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

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

пятница, 13 июня 2014 г.

LeapMotion первые впечатления

Мне подарили LeapMotion, и я хочу поделиться первыми впечатлениями.
Не буду пересказывать существующие отзывы, просто несколько пунктов от меня.

  • Выглядит всё очень круто, упаковка в стиле Apple, ничего лишнего, зато два кабеля USB (короткий и длинный)
  • Софт симпатичный и просто работает (а на случай проблем есть куча диагностики)
  • Всё очень красиво, плавает и летает
  • На первый взгляд, очень хорошее API и SDK (можно получить хоть сырую информацию, хоть жесты — т.е. API само занимается математикой, чтобы вручную не вычислять)
  • Распознаются руки с пальцами: включая ориентацию ладони и фаланги (хотя точность их распознавания очень неважная), а также тыкательные предметы типа ручки (причём он понимает, что это не палец и у ручки нет ладони.
  • По факту — ладонь должна быть повёрнута вниз, пальцы растопырены, иначе не определяет. Т.е. боком ладонь нельзя использовать (или очень хорошо обрабатывать исчезающие и появляющиеся пальцы.
  • Дрожание в принципе очень хорошо сглаживается стандартным софтом.
  • Он умный и у него большой угол обзора, т.е. не надо держать руку прямо над ним, я положил под монитор и он вполне понимает мои руки, находящиеся перед
  • Идеально (имхо) положить его на место клавиатуры, но, естественно, это не получится. Перед клавиатурой — будет мешаться, так что остаётся место за клавиатурой или где-нибудь сбоку для одной руки
  • Есть программа для управления компьютером, но она так себе. Не очень удобно попадать по углам, да и резкое неправильное движение приводит к тому, что курсор прыгает и кликает в самых неожиданных местах. Её поведение — следит за пальцем (как курсор), при пересечении виртуальной границы проходит клик. Ладонью скролл. Как-то правая кнопка работает и прочие хитрости, ещё не разобрался. 
  • На весу управлять — руки быстро устают, и кроме того, сам рукой закрываешь экран (поэтому, возможно лучше где-то сбоку подцепить)
  • В магазине есть много игрушек и приложений. Но, имхо, на побаловаться. Кроме того, везде управление слегка отличается.
  • Google Earth управлением руками выглядит красиво, но постоянно куда-то крутится и двигается
  • Вообще, управление компьютером с помощью него выглядит как использование некого виртуального тачскрина.
  • В реальности, мышку заменить можно, но не нужно, если всё в порядке с руками.
В общем, не буду дальше разводить писанину, возможно, дополню пост после более длительного использования. Пока у меня планы не управлять курсором, а управлять окнами (свернуть, развернуть, закрыть, назад, вперёд, изменить громкость, и т.д.). Но стандартного софта не нашёл (во всяком случае бесплатного), поэтому попробую написать сам, именно так, как я хочу.

Если будут конкретные вопросы, пишите, отвечу.