Какая библиотека сжатия лучше всего подходит для очень маленьких объемов данных (3-4 киб?)
Я работаю над игровым движком, слабо унаследованным от Quake 2, добавляя некоторые вещи, такие как скриптовые эффекты (позволяя серверу детально задавать специальные эффекты клиенту, вместо того, чтобы иметь только ограниченное количество жестко закодированных эффектов, на которые способен клиент о.) Это компромисс эффективности сети для гибкости.
Я столкнулся с интересным барьером. Видите, максимальный размер пакета составляет 2800 байт, и только один может выходить на одного клиента на кадр.
Вот сценарий для создания эффекта "искры" (может быть полезен для искр от пуль, электрических ударов и т. Д.) http://pastebin.com/m7acdf519 (Если вы этого не понимаете, не переживайте; это собственный синтаксис, который я сделал и не имеет отношения к вопросу, который я задаю.)
Я сделал все возможное, чтобы уменьшить размер этого сценария. Я даже сократил имена переменных до отдельных букв. Но результат составляет ровно 405 байтов. Это означает, что вы можете разместить не более 6 из них на кадр. Я также имею в виду несколько изменений на стороне сервера, которые могли бы сократить его еще на 12, и изменение протокола, которое могло бы спасти еще 6. Хотя экономия будет зависеть от того, с каким сценарием вы работаете.
Тем не менее, из этих 387 байтов, я считаю, что только 41 будет уникальным при многократном использовании эффекта. Другими словами, это главный кандидат на сжатие.
Так получилось, что R1Q2 (обратно совместимый движок Quake 2 с расширенным сетевым протоколом) имеет код сжатия Zlib. Я мог бы поднять этот код или, по крайней мере, внимательно следить за ним в качестве ссылки.
Но Zlib обязательно лучший выбор здесь? Я могу придумать, по крайней мере, одну альтернативу, LZMA, и их может быть больше.
Требования:
- Должен быть очень быстрым (должен иметь очень маленький удар по производительности, если работает более 100 раз в секунду.)
- Необходимо втиснуть как можно больше данных в 2800 байт
- Небольшой след метаданных
- Совместимость с 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 байт!)
РЕДАКТИРОВАТЬ 2: Нет никакой гарантии, что какой-либо пакет будет доставлен. Каждый пакет должен содержать "состояние мира", не полагаясь на информацию, переданную в предыдущих пакетах. Как правило, эти сценарии будут использоваться для сообщения "конфетка глаз". Если для одного места нет места, он выпадает из пакета, и в этом нет ничего страшного. Но если бросить слишком много, все начинает выглядеть странно, и это нежелательно.
6 ответов
ЗАКЛЮЧИТЕЛЬНОЕ ОБНОВЛЕНИЕ: две библиотеки кажутся примерно одинаковыми. 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 в крайних случаях, но клиенты могут быть настроены на их игнорирование, и это будет по умолчанию.
zlib может быть хорошим кандидатом - лицензия очень хорошая, работает быстро, и ее авторы говорят, что у нее очень мало накладных расходов, и это проблема, которая делает использование небольших объемов данных проблематичным.
Вам следует взглянуть на OpenTNL и адаптировать некоторые методы, которые они там используют, например концепцию сетевых строк
Как насчет отправки двоичного представления вашего скрипта?
Поэтому я думаю в строках абстрактного синтаксического дерева, в котором каждая процедура имеет идентификатор.
Это означает выигрыш преформана на клиентах из-за разового разбора и уменьшение размера из-за удаления имен методов.
Я был бы склонен использовать самый значимый бит каждого символа, который в настоящее время тратится впустую, сдвигая группы в 9 байтов влево, вы вписываетесь в 8 байтов.
Вы можете пойти дальше и отобразить символы в небольшом пространстве - можете ли вы уменьшить их до 6 бит (т.е. иметь только 64 действительных символа), например, не допуская заглавных букв и вычитая 0x20 из каждого символа (чтобы пробел стал значением 0)
Вы можете пойти дальше, сопоставив частоту каждого символа и сделав сжатие типа Хаффмана, чтобы уменьшить средние биты числа каждого символа.
Я подозреваю, что нет алгоритмов, которые будут лучше сохранять данные, чем, в общем случае, поскольку в сообщении практически нет избыточности после внесенных вами изменений.