Какая библиотека сжатия лучше всего подходит для очень небольших объемов данных (3-4 кб?)

StackOverflow https://stackoverflow.com/questions/2279644

Вопрос

Я работаю над игровым движком, который является прямым потомком Quake 2, добавляя некоторые вещи, такие как скриптовые эффекты (позволяющие серверу подробно указывать специальные эффекты клиенту, вместо того, чтобы иметь только ограниченное количество жестко запрограммированных эффектов, на которые способен клиент.) Это компромисс между эффективностью сети и гибкостью.

Я наткнулся на интересный барьер.Видите ли, максимальный размер пакета составляет 2800 байт, и только один пакет может быть отправлен каждому клиенту за кадр.

Вот сценарий для создания эффекта "искры" (может быть полезен при попадании пули в искры, поражении электрическим током и т.д.) http://pastebin.com/m7acdf519 (Если вы этого не понимаете, не переживайте;это пользовательский синтаксис, который я создал и не имеет отношения к вопросу, который я задаю.)

Я сделал все возможное, чтобы уменьшить размер этого скрипта.Я даже сократил имена переменных до отдельных букв.Но результат равен ровно 405 байтам.Это означает, что на кадр может поместиться не более 6 таких изображений.Я также имею в виду несколько изменений на стороне сервера, которые могли бы сократить его еще на 12, и изменение протокола, которое могло бы сэкономить еще 6.Хотя экономия будет варьироваться в зависимости от того, с каким скриптом вы работаете.

Однако, по моим оценкам, из этих 387 байт только 41 был бы уникальным при многократном использовании эффекта.Другими словами, это главный кандидат на сжатие.

Так уж получилось, что R1Q2 (обратно совместимый движок Quake 2 с расширенным сетевым протоколом) имеет код сжатия Zlib.Я мог бы использовать этот код или, по крайней мере, внимательно следить за ним в качестве ссылки.

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

Требования:

  1. Должен быть очень быстрым (должно быть, очень небольшое снижение производительности при запуске более 100 раз в секунду).)
  2. Необходимо втиснуть как можно больше данных в 2800 байт
  3. Небольшой объем метаданных
  4. Совместимость с GPL

Zlib выглядит неплохо, но есть ли что-нибудь лучше?Имейте в виду, что ни один из этих кодов пока не объединяется, так что есть много возможностей для экспериментов.

Спасибо, -Макс

Редактировать:Спасибо тем, кто предложил скомпилировать скрипты в байт-код.Я должен был прояснить это - да, я делаю это.Если хотите, вы можете просмотреть соответствующий исходный код на моем веб-сайте, хотя он все еще не "приукрашен".
Это код на стороне сервера:
Компонент Lua: http://meliaserlow.dyndns.tv:8000/alienarena/lua_source/lua/scriptedfx.lua
Компонент C: http://meliaserlow.dyndns.tv:8000/alienarena/lua_source/game/g_scriptedfx.c
Для конкретного примера скрипта, который я опубликовал, это сокращает исходный код размером 1172 байта до 405 байт - все еще недостаточно мало.(Имейте в виду, что я хочу уместить как можно больше из них в 2800 байт!)

РЕДАКТИРОВАТЬ 2:Нет никакой гарантии, что какой-либо данный пакет прибудет.Предполагается, что каждый пакет должен содержать "состояние мира", не полагаясь на информацию, переданную в предыдущих пакетах.Как правило, эти скрипты используются для передачи сообщений "eye candy". Если для одного из них нет места, он удаляется из пакета, и в этом нет ничего страшного.Но если их отбрасывается слишком много, визуально все начинает выглядеть странно, а это нежелательно.

Это было полезно?

Решение 2

ОКОНЧАТЕЛЬНОЕ ОБНОВЛЕНИЕ: Эти две библиотеки кажутся примерно эквивалентными.Zlib обеспечивает примерно на 20% лучшее сжатие, в то время как скорость декодирования LZO примерно в два раза выше, но снижение производительности для обоих очень мало, почти пренебрежимо.Это мой окончательный ответ.Спасибо за все остальные ответы и комментарии!

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

ОРИГИНАЛЬНОЕ СООБЩЕНИЕ:

Итак, я наконец-то нашел время написать для этого какой-нибудь код.Я начал с Zlib, вот первые мои выводы.

Сжатие Zlib является безумно отлично.Это надежно сокращает пакеты размером, скажем, 8,5 кб до, скажем, 750 байт или меньше, даже при сжатии с помощью Z_BEST_SPEED (вместо Z_DEFAULT_COMPRESSION .) Время сжатия также довольно хорошее.

Однако я понятия не имел о скорости декомпрессии что угодно возможно, все даже так плохо.У меня нет фактических цифр, но это должно занимать не менее 1/8 секунды на каждый пакет!(Core2Duo T550 с частотой 1,83 ГГц.) Абсолютно неприемлемо.

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

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

Другие советы

ЛЗО возможно, это хороший кандидат для этого.

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

вам следует взглянуть на OpenTNL и адаптировать некоторые методы, которые они там используют, например, концепцию сетевых строк

Я был бы склонен использовать самый значимый бит каждого символа, который в данный момент тратится впустую, сдвинув группы по 9 байт влево, вы уместитесь в 8 байт.

Вы могли бы пойти дальше и поместить символы в небольшое пространство - можете ли вы сократить их до 6 бит (т. е.всего 64 допустимых символа), например, не допуская заглавных букв и вычитая 0x20 из каждого символа ( так, чтобы пробел принял значение 0 )

Вы могли бы пойти дальше, сопоставив частоту каждого символа и выполнив сжатие типа Хаффмана, чтобы уменьшить среднее число битов каждого символа.

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

Как насчет отправки двоичного представления вашего скрипта?

Итак, я думаю о строках абстрактного синтаксического дерева, где каждая процедура имеет идентификатор.

Это означает увеличение производительности клиентов за счет одноразового синтаксического анализа и уменьшение размера за счет удаления имен методов.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top