Qual é a melhor biblioteca de compactação para quantidades muito pequenas de dados (3-4 kib?)

Question

Estou trabalhando em um mecanismo de jogo que é vagamente descendente do Quake 2, adicionando algumas coisas como efeitos de script (permitindo ao servidor especificar efeitos especiais em detalhes para um cliente, em vez de ter apenas um número limitado de efeitos codificados que o cliente é capaz de.) Esta é uma troca entre eficiência de rede e flexibilidade.

Eu bati em uma barreira interessante.Veja, o tamanho máximo do pacote é 2.800 bytes e apenas um pode sair por cliente por quadro.

Aqui está o script para fazer um efeito de "faíscas" (pode ser bom para faíscas de impacto de bala, choques elétricos, etc.)http://pastebin.com/m7acdf519 (Se você não entende, não se preocupe;é uma sintaxe personalizada que criei e não é relevante para a pergunta que estou fazendo.)

Fiz todo o possível para diminuir o tamanho desse script.Até reduzi os nomes das variáveis ​​para letras únicas.Mas o resultado é exatamente 405 bytes.O que significa que você pode colocar no máximo 6 deles por quadro.Também tenho em mente algumas alterações no servidor que podem reduzir outras 12, e uma alteração de protocolo que pode economizar outras 6.Embora a economia varie dependendo do script com o qual você está trabalhando.

No entanto, desses 387 bytes, estimo que apenas 41 seriam únicos entre múltiplos usos do efeito.Em outras palavras, este é um excelente candidato para compressão.

Acontece que R1Q2 (um mecanismo Quake 2 compatível com versões anteriores com um protocolo de rede estendido) possui código de compactação Zlib.Eu poderia levantar esse código, ou pelo menos segui-lo de perto como referência.

Mas o Zlib é necessariamente a melhor escolha aqui?Posso pensar em pelo menos uma alternativa, LZMA, e poderia facilmente haver mais.

Os requisitos:

1. Deve ser muito rápido (deve ter um impacto muito pequeno no desempenho se for executado mais de 100 vezes por segundo).
2. Deve amontoar o máximo de dados possível em 2.800 bytes
3. Pegada pequena de metadados
4. Compatível com GPL

Zlib parece bom, mas há algo melhor?Lembre-se de que nenhum código foi mesclado ainda, portanto há muito espaço para experimentação.

Obrigado, -max

EDITAR:Obrigado a todos aqueles que sugeriram compilar os scripts em bytecode.Eu deveria ter deixado isso claro - sim, estou fazendo isso.Se quiser, você pode navegar pelo código-fonte relevante em meu site, embora ainda não esteja "embelezado".
Este é o código do lado do servidor:
Componente Lua: http://meliaserlow.dyndns.tv:8000/alienarena/lua_source/lua/scriptedfx.lua
Componente C: http://meliaserlow.dyndns.tv:8000/alienarena/lua_source/game/g_scriptedfx.c
Para o script de exemplo específico que postei, isso reduz uma fonte de 1172 bytes para 405 bytes - ainda não é pequena o suficiente.(Lembre-se de que quero encaixar o máximo possível em 2.800 bytes!)

EDITAR2:Não há garantia de que qualquer pacote chegará.Cada pacote deve conter “o estado do mundo”, sem depender de informações comunicadas em pacotes anteriores.Geralmente, esses scripts serão usados ​​para comunicar "colírio para os olhos". Se não houver espaço para um, ele será retirado do pacote e isso não é grande coisa.Mas se muitos caírem, as coisas começarão a parecer estranhas visualmente e isso é indesejável.

Answer 1

ATUALIZAÇÃO FINAL: As duas bibliotecas parecem equivalentes.O Zlib oferece compactação cerca de 20% melhor, enquanto a velocidade de decodificação do LZO é cerca de duas vezes mais rápida, mas o impacto no desempenho de ambos é muito pequeno, quase insignificante.Essa é minha resposta final.Obrigado por todas as outras respostas e comentários!

ATUALIZAR: Depois de implementar a compactação LZO e ver um desempenho apenas ligeiramente melhor, fica claro que meu próprio código é o culpado pelo impacto no desempenho (aumento maciço do número de efeitos de script possíveis por pacote, portanto, meu "intérprete" de efeito está sendo exercitado muito mais.) Gostaria de pedir desculpas humildemente por ter lutado para transferir a culpa e espero que não haja ressentimentos.Farei alguns perfis e talvez consiga alguns números que serão mais úteis para outra pessoa.

POSTAGEM ORIGINAL:

OK, finalmente consegui escrever algum código para isso.Comecei com Zlib, aqui estão as primeiras descobertas.

A compressão do Zlib é insanamente ótimo.Ele reduz de forma confiável pacotes de, digamos, 8,5 kib para, digamos, 750 bytes ou menos, mesmo ao compactar com Z_BEST_SPEED (em vez de Z_DEFAULT_COMPRESSION). O tempo de compactação também é muito bom.

No entanto, eu não tinha ideia da velocidade de descompressão do qualquer coisa poderia até ser tão ruim.Não tenho números reais, mas deve levar pelo menos 1/8 de segundo por pacote!(Core2Duo T550 @ 1,83 Ghz.) Totalmente inaceitável.

Pelo que ouvi, o LZMA é uma compensação entre pior desempenho e desempenho inferior.melhor compactação quando comparado ao Zlib.Como a compactação do Zlib já é um exagero e seu desempenho já é incrivelmente ruim, o LZMA está fora de questão por enquanto.

Se o tempo de descompressão do LZO for tão bom quanto afirma ser, então é isso que irei usar.Acho que no final o servidor ainda poderá enviar pacotes Zlib em casos extremos, mas os clientes podem ser configurados para ignorá-los e esse será o padrão.

Answer 2

LZO pode ser um bom candidato para isso.

Answer 3

zlib pode ser um bom candidato - a licença é muito boa, funciona rápido e seus autores dizem que tem muito pouca sobrecarga e sobrecarga é o que torna problemático o uso de pequenas quantidades de dados.

Answer 4

você deveria olhar OpenTNL e adaptar algumas das técnicas que eles usam lá, como o conceito de Network Strings

Answer 5

Eu estaria inclinado a usar o bit mais significativo de cada caractere, que atualmente é desperdiçado, deslocando grupos de 9 bytes para a esquerda, você caberá em 8 bytes.

Você poderia ir mais longe e mapear os caracteres em um espaço pequeno - você pode reduzi-los para 6 bits (ou seja,tendo apenas 64 caracteres válidos), por exemplo, não permitindo letras maiúsculas e subtraindo 0x20 de cada caractere (para que o espaço se torne o valor 0)

Você poderia ir além mapeando a frequência de cada caractere e fazer uma compactação do tipo Huffman para reduzir o número médio de bits de cada caractere.

Suspeito que não existam algoritmos que salvem melhor os dados do que, no caso geral, já que essencialmente não há redundância na mensagem após as alterações que você já fez.

Answer 6

Que tal enviar uma representação binária do seu script?

Então estou pensando nas linhas de uma Árvore de Sintaxe Abstrata com cada procedimento tendo um identificador.

Isso significa ganho de desempenho nos clientes devido à análise única e diminuição de tamanho devido à remoção dos nomes dos métodos.