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

Question

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

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

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

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

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

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

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

Требования:

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

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

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

РЕДАКТИРОВАТЬ: Спасибо тем, кто предложил компилировать скрипты в байт-код. Я должен был прояснить это - да, я делаю это. Если вам нравится, вы можете просмотреть соответствующий исходный код на моем веб-сайте, хотя он по-прежнему не является «симпатичным».
Это код на стороне сервера:
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 байт!)

EDIT2: нет никакой гарантии, что какой-либо данный пакет прибудет. Каждый пакет должен содержать «состояние мира», не полагаясь на информацию, переданную в предыдущих пакетах. Как правило, эти сценарии будут использоваться для сообщения "конфетка глаз". Если для одного места нет места, он выпадает из пакета, и в этом нет ничего страшного. Но если их бросить слишком много, все начинает выглядеть странно, и это нежелательно.

Answer 1

LZO может быть хорошим кандидатом для этого.

Answer 2

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

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

ОРИГИНАЛЬНАЯ ПОЧТА:

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

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

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

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

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