¿Cuál es la mejor biblioteca de compresión de muy pequeñas cantidades de datos (3-4 kib?)

Question

Estoy trabajando en un motor de juego que se descendió ligeramente desde Quake 2, la adición de algunas cosas como efectos guión (que permite el servidor para especificar los efectos especiales en detalle a un cliente, en lugar de tener sólo un número limitado de efectos Hardcoded cual el cliente es capaz de hacer.) Esta es una solución de compromiso de eficiencia de la red para la flexibilidad.

He golpeado una barrera interesante. Ver, el tamaño máximo de paquete es de 2800 bytes, y sólo uno puede salir por cliente al bastidor.

Esta es la secuencia de comandos para hacer un efecto de "chispas" (podría ser bueno para las chispas de impacto de bala, descargas eléctricas, etc.) http://pastebin.com/m7acdf519 (Si no lo entiende, no se preocupe, es una sintaxis a medida que hace y no es relevante para la cuestión que estoy pidiendo.)

He hecho todo lo posible para reducir el tamaño de ese guión. Incluso me he reducido los nombres de las variables a las letras individuales. Pero el resultado es exactamente 405 bytes. Lo que significa que puede caber en la mayoría de éstos 6 por cuadro. También tengo en cuenta algunos cambios en el servidor, que podría recortar hacia abajo otro 12, y un cambio de protocolo que podría salvar a otro 6. Aunque el ahorro podría variar dependiendo de qué secuencia de comandos que se está trabajando.

Sin embargo, de esos 387 bytes, estimo que sólo 41 pueden ser única entre múltiples usos del efecto. En otras palabras, este es un candidato ideal para la compresión.

Lo que pasa es que R1Q2 (un motor compatible con versiones anteriores Quake 2 con un protocolo de red extendida) tiene código de compresión Zlib. Podía levantar este código, o al menos seguir de cerca como referencia.

Pero es Zlib necesariamente la mejor opción aquí? Se me ocurren al menos una alternativa, LZMA, y no podía ser más fácil.

Los requisitos:

1. Debe ser muy rápido (debe tener muy pequeño impacto en el rendimiento si se ejecuta más de 100 veces por segundo.)
2. Debe meter tantos datos como sea posible en 2800 bytes
3. Tamaño reducido metadatos
4. GPL compatibles

Zlib se ve bien, pero ¿hay algo mejor? Tenga en cuenta, se fusionó ninguno de este código, sin embargo, por lo que hay mucho espacio para la experimentación.

Gracias, -Max

EDIT: Gracias a los que han sugerido la compilación de las secuencias de comandos en bytecode. Debería haber hecho este clear-- sí, yo estoy haciendo esto. Si lo desea, puede ver el código fuente relevante en mi sitio web, aunque todavía no "prettied."
Este es el código del lado del servidor:
componente Lua: http://meliaserlow.dyndns.tv:8000/alienarena/ lua_source / lua / scriptedfx.lua
componente C: http://meliaserlow.dyndns.tv:8000/alienarena/ lua_source / juego / g_scriptedfx.c
Para el guión ejemplo específico que he publicado, esto se vuelve una fuente de 1.172 bytes hasta 405 bytes-- todavía no lo suficientemente pequeño. (Hay que tener en cuenta que quiero para adaptarse a la mayor cantidad posible de esta opción en 2800 bytes!)

Edit2: No hay garantía de que va a llegar a cualquier paquete dado. Cada paquete se supone que contienen "el estado del mundo", sin depender de la información comunicada en los paquetes anteriores. En general, estas secuencias de comandos se pueden utilizar para comunicar "ojos dulces." Si no hay espacio para uno, que se cae del paquete y que no es gran cosa. Pero si muchos son eliminadas del mismo, las cosas empiezan a parecer extraño visual y esto no es deseable.

Answer 1

INFORME FINAL DE ACTUALIZACIÓN: Las dos bibliotecas parecen casi equivalente. Zlib da alrededor del 20% mejor compresión, mientras que la velocidad de decodificación de LZO es dos veces más rápido, pero el impacto en el rendimiento, ya sea es muy pequeño, casi insignificante. Esa es mi respuesta final. Gracias por todas las demás respuestas y comentarios!

ACTUALIZACIÓN: Después de la aplicación de la compresión de LZO y viendo sólo un poquitito mejor rendimiento, es evidente que mi propio código es el culpable de la pérdida de rendimiento (masivo aumento del número de efectos con secuencias de comandos posibles por paquete, por lo tanto mi efecto de "intérprete" es ejercido conseguir mucho más.) me gustaría pedir disculpas humildemente para codificar de echarle la culpa, y espero que no hay resentimientos. Voy a hacer un poco de perfiles y luego tal vez voy a ser capaz de conseguir algunos números que serán más útiles a otra persona.

Post original:

OK, finalmente conseguí alrededor de escribir algo de código para esto. Empecé con Zlib, he aquí el primero de mis hallazgos.

la compresión

de Zlib es locamente grande. Se está reduciendo de forma fiable de paquetes, por ejemplo, 8,5 kib hasta, digamos, 750 bytes o menos, incluso cuando se comprime con Z_BEST_SPEED (en lugar de Z_DEFAULT_COMPRESSION.) El tiempo de compresión también es bastante bueno.

Sin embargo, no tenía idea de la velocidad de descompresión de lo incluso podría posiblemente ser tan malo. No tengo los números reales, pero debe estar tomando 1/8 segundos por paquete por lo menos! (Core2Duo T550 @ 1,83 Ghz.) Totalmente inaceptable.

Por lo que he oído, LZMA es un compromiso de peor rendimiento en relación con una mejor compresión en comparación con Zlib. Ya que la compresión de Zlib es ya una exageración y su rendimiento ya es muy mala, LZMA está fuera de la mesa de la vista no se ve por ahora.

Si el tiempo de descompresión de LZO es tan bueno como se decía ser, entonces eso es lo que va a utilizar. Creo que al final el servidor todavía será capaz de enviar paquetes Zlib en casos extremos, pero los clientes se pueden configurar para ignorarlos y que será la predeterminada.

Answer 2

lzo podría ser un buen candidato para esto.

Answer 3

zlib podría ser un buen candidato - licencia es muy bueno, funciona rápido y sus autores dicen que tiene muy poco gastos generales y los gastos generales es lo que hace uso de pequeñas cantidades de datos problemática.

Answer 4

usted debe buscar en OpenTNL y adaptar algunas de las técnicas que utilizan allí, como el concepto de red Cuerdas

Answer 5

estaría inclinded utilizar el bit más significativo de cada personaje, que actualmente se desperdicia, desplazando grupos de 9 bytes hacia la izquierda, que se ajusta a 8 bytes.

Se podría ir más allá y un mapa de los personajes en un espacio pequeño - se puede conseguir hasta 6 bits (es decir, sólo tienen 64 caracteres válidos) mediante, por ejemplo, no permitir que las letras mayúsculas y restando 0x20 de cada personaje (de modo que el espacio se convierte en el valor 0)

Se podría ir más allá mediante la asignación de la frecuencia de cada personaje y hacer un tipo de compresión Huffman para reducir los bits del número avarage_nus de cada personaje.

Sospecho que no hay algoritmos que guardará los datos mejor que, en el caso general, ya que esencialmente no hay redundancia en el mensaje después de los cambios que haya realizado alrady.

Answer 6

¿Cómo sobre el envío de una representación binaria de la secuencia de comandos?

Así que estoy pensando en las líneas de un árbol de sintaxis abstracta de cada procedimiento tiene un identificador.

Esto significa ganancia Preformance en los clientes debido al análisis de una sola vez, y la disminución de tamaño debido a la eliminación de los nombres de los métodos.