Оптимальная сериализация примитивных типов

Question

Мы начинаем развертывать все больше развертываний WAN нашего продукта (.NET-клиент с хостингом IIS Remoting backend). Из-за этого мы пытаемся уменьшить размер данных на проводе.

Мы переопределили сериализацию по умолчанию, реализовав ISerializable (аналогично this), и мы видим от 12% до 50% прибыли. Большинство наших усилий сосредоточено на оптимизации массивов примитивных типов. Есть ли причудливый способ сериализации примитивных типов, помимо очевидных?

К примеру, сегодня мы сериализовать массив целых чисел следующим образом:

[4 байта (длина массива)] [4-байт] [4-байт]

Может кто-то делает значительно лучше?

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

Примечание: Сохранение 7 бит на bool может показаться пустой тратой времени, но когда вы имеете дело с большими величинами данных (что мы и есть), оно складывается очень быстро.

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

Answer 1

(относится к сообщениям/классы, а не только примитивы)

Google спроектированные «буферы протокола» для этого типа сценария (они смещаются огромное количество данных вокруг) - их формат компактен (используя такие вещи, как основы -128), но расширяемость и допустимость версий (поэтому клиенты и серверы могут легко обновляться).

В мире .NET, я могу порекомендовать 2 протокола буферов реализации:

• protobuf-net (мной)
• dotnet-protobufs (Джон Скит)

Для информации, Protobuf-нетто имеет прямую поддержку для ISerializable и удаляет (это часть unit tests). Показатели производительности/размера here.

И, самое главное, все, что вы делаете, это добавить несколько атрибутов к вашим классам.

Предостережение: оно не претендует на то, чтобы быть теоретическим лучшим - но прагматичным и простым в праве - это компромисс между производительностью, мобильностью и простотой.

Answer 2

Проверьте тип base-128 varint, используемый в буферах протокола Google; это может быть то, что вы ищете.

(Там целый ряд .NET реализаций буферов протоколов, доступных, если вы будете искать в Интернете, который, в зависимости от их лицензии, вы можете быть в состоянии ползать код с!)

Answer 3

Если вы знаете, какие значения Int более распространены, вы можете кодировать эти значения в меньшем количестве бит (и кодировать менее общие значения, используя соответственно большее количество бит): это называется кодировкой/кодированием/сжатием «Хаффман».

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

Answer 4

Для целого числа, если у вас обычно есть небольшие числа (до 127 или 32768), вы можете кодировать число, используя MSB в качестве флага, чтобы определить, является ли это последним байтом или нет. Немного похож на UTF-8, но бит флага фактически впустую (который не в случае с UTF-8)

Пример (большой обратный порядок байт):

125 which is usually encoded as 00 00 00 7D 
Could be encoded as 7D 

270 which is usually encoded as 00 00 01 0E 
Could be encoded as 82 0E 

Основным ограничением является что эффективный диапазон 32-битного значения уменьшается до 28 бит. Но для небольших ценностей вы обычно выигрываете много.

Этот метод фактически используется в старых форматах, таких как MIDI, потому что для старой электроники нужны очень эффективные и простые методы кодирования.

Answer 5

Перед тем, как внедрить ISerializable, вы, вероятно, использовали XmlSerializer или форматер SOAP в веб-службе. Учитывая, что у вас есть все толстые клиенты, все из которых работают .NET, вы можете попробовать использовать BinaryFormatter.

Answer 6

Если ваши массивы можно отсортировать, вы можете выполнить простое RLE, чтобы сэкономить место. Даже если они не отсортированы, RLE может быть полезен. Он быстро реализуется как для записи, так и для чтения.

Answer 7

Вот трюк я использовал один раз для кодирования массивов чисел:

1. Группа элементов массива в группах 4.
2. перед каждой группы с байтом (назовем его длина маски), что указывает длину из следующих 4 элементов. Маска длины - это битовая маска, состоящая из дибитов, которые указывают, как долго соответствует соответствующий элемент (00 - 1 байт, 01 - 2 байта, 10 - 3 байта, 11 - 4 байта).
3. Выпишите элементы как можно короче.

Например, для представления целых чисел без знака 0x0000017B, 0x000000A9, 0xC247E8AD и 0x00032A64, можно было бы написать (предполагая, что мало-Endian): B1, 7b, 01, А9, AD, Е8, 47, С2, 64, 2A , 03.

Это может сэкономить до 68,75% (11/16) места в лучшем случае. В худшем случае вы фактически будете тратить дополнительные 6,25% (1/16).

Answer 8

Да, есть причудливый способ сериализации примитивных типов. В качестве бонуса он также намного быстрее (обычно 20-40 раз).

Библиотека с открытым исходным кодом Саймона Хьюитта, см. Optimizing Serialization in .NET - part 2, использует различные трюки. Например, если известно, что массив содержит малые целые числа, тогда меньшее число выводится на сериализованный вывод. Это подробно описано in part 1 of the article. Например:

...Так, Int32, что меньше, чем 128 могут быть сохранены в одном байте (с использованием 7-битного кодирования ) ....

Полное и размер оптимизированы целые числа, что могут быть смешаны и подобраны. Это может показаться очевидным, но есть и другие вещи; например, происходят особые вещи для целочисленного значения 0 - оптимизация для хранения числового типа и нулевого значения.

Часть 1 гласит:

... Если вы когда-либо использовали .NET Remoting для больших объемов данных, вы обнаружили, что есть проблемы с масштабируемостью. Для небольших объемов данных он работает достаточно хорошо, но большие объемы занимают много центрального процессора и памяти, генерируют огромное количество данных для передачи и могут выходить из строя с исключениями Out Of Memory. Существует также большая проблема с временем, затраченным на самом деле выполнить сериализацию - большие объемы данных могут сделать невозможный для использования в приложениях ....

Я использовал эту библиотеку с большим успехом в my application.

Чтобы убедиться, что .NET сериализации никогда не используется Погружает ASSERT 0, Debug.WriteLine() или подобное в место в коде библиотеки, где она падает обратно на .NET сериализации. Это в конце функции WriteObject() в файле FastSerializer.cs, рядом с createBinaryFormatter().Serialize(BaseStream, value);.

Answer 9

Если вы хотите самостоятельно управлять форматом сериализации, используя только библиотечную помощь для компактного целочисленного хранения, выведите класс из BinaryWriter, который использует Write7BitEncodedInt. Аналогично для BinaryReader.Read7BitEncodedInt.