Qual è la migliore libreria di compressione per quantità di dati molto piccole (3-4 kib?)

Question

Sto lavorando su un motore di gioco che discende vagamente da Quake 2, aggiungendo alcune cose come effetti con script (che consentono al server di specificare effetti speciali in dettaglio per un client, invece di avere solo un numero limitato di effetti codificati di cui il client è capace of.) Questo è un compromesso tra l'efficienza della rete e la flessibilità.

Ho raggiunto un ostacolo interessante.Vedi, la dimensione massima del pacchetto è 2800 byte e solo uno può uscire per client per frame.

Ecco lo script per creare un effetto "scintille" (potrebbe essere utile per scintille da impatto di proiettili, scosse elettriche, ecc.)http://pastebin.com/m7acdf519 (Se non lo capisci, non preoccuparti;è una sintassi personalizzata che ho creato e non rilevante per la domanda che sto ponendo.)

Ho fatto tutto il possibile per ridurre le dimensioni di quello script.Ho persino ridotto i nomi delle variabili a singole lettere.Ma il risultato è esattamente 405 byte.Ciò significa che puoi inserirne al massimo 6 per frame.Ho anche in mente alcune modifiche lato server che potrebbero ridurne altri 12 e una modifica al protocollo che potrebbe salvarne altri 6.Sebbene il risparmio varierebbe a seconda dello script con cui stai lavorando.

Tuttavia, di questi 387 byte, stimo che solo 41 sarebbero unici tra più utilizzi dell'effetto.In altre parole, questo è un ottimo candidato per la compressione.

Si dà il caso che R1Q2 (un motore Quake 2 retrocompatibile con un protocollo di rete esteso) abbia il codice di compressione Zlib.Potrei sollevare questo codice, o almeno seguirlo da vicino come riferimento.

Ma Zlib è necessariamente la scelta migliore in questo caso?Mi viene in mente almeno un'alternativa, LZMA, e potrebbero facilmente essercene altre.

I requisiti:

1. Deve essere molto veloce (deve avere un calo di prestazioni molto ridotto se eseguito più di 100 volte al secondo).
2. Deve stipare quanti più dati possibile in 2800 byte
3. Piccola impronta di metadati
4. Compatibile con GPL

Zlib ha un bell'aspetto, ma c'è qualcosa di meglio?Tieni presente che nessuno di questi codici è stato ancora unito, quindi c'è molto spazio per la sperimentazione.

Grazie, -max

MODIFICARE:Grazie a coloro che hanno suggerito di compilare gli script in bytecode.Avrei dovuto chiarirlo... sì, lo sto facendo.Se vuoi puoi sfogliare il codice sorgente pertinente sul mio sito web, anche se non è ancora "bello".
Questo è il codice lato server:
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
Per lo script di esempio specifico che ho pubblicato, questo riduce un'origine da 1172 byte a 405 byte, ancora non abbastanza piccola.(Tieni presente che voglio inserirne il maggior numero possibile in 2800 byte!)

EDIT2:Non esiste alcuna garanzia che un determinato pacchetto arrivi.Si suppone che ogni pacchetto contenga "lo stato del mondo", senza fare affidamento sulle informazioni comunicate nei pacchetti precedenti.In generale, questi script verranno utilizzati per comunicare "Accadono per gli occhi". Se non c'è spazio per uno, viene lasciato cadere dal pacchetto e non è un grosso problema.Ma se ne cadono troppi, le cose iniziano ad apparire visivamente strane e questo è indesiderabile.

Answer 1

AGGIORNAMENTO FINALE: Le due librerie sembrano quasi equivalenti.Zlib offre una compressione migliore di circa il 20%, mentre la velocità di decodifica di LZO è circa il doppio più veloce, ma il calo delle prestazioni per entrambi è molto piccolo, quasi trascurabile.Questa è la mia risposta finale.Grazie per tutte le altre risposte e commenti!

AGGIORNAMENTO: Dopo aver implementato la compressione LZO e aver visto prestazioni solo leggermente migliori, è chiaro che il mio codice è responsabile del calo delle prestazioni (numero enormemente aumentato di effetti di script possibili per pacchetto, quindi il mio "interprete" degli effetti viene esercitato molto di più). Vorrei scusarmi umilmente per aver fatto di tutto per scaricare la colpa, e spero che non ci siano rancori.Farò un po' di profilazione e poi forse riuscirò a ottenere dei numeri che saranno più utili a qualcun altro.

POST ORIGINALE:

OK, finalmente sono riuscito a scrivere del codice per questo.Ho iniziato con Zlib, ecco i primi risultati.

La compressione di Zlib è follemente Grande.Riduce in modo affidabile i pacchetti da, diciamo, 8,5 kib fino a, diciamo, 750 byte o meno, anche quando si comprime con Z_BEST_SPEED (invece di Z_DEFAULT_COMPRESSION). Anche il tempo di compressione è piuttosto buono.

Tuttavia, non avevo idea della velocità di decompressione nulla potrebbe anche essere così brutto.Non ho numeri reali, ma deve volerci almeno 1/8 di secondo per pacchetto!(Core2Duo T550 @ 1,83 Ghz.) Totalmente inaccettabile.

Da quello che ho sentito, LZMA è un compromesso tra prestazioni peggiori e prestazioni inferiori.migliore compressione rispetto a Zlib.Dato che la compressione di Zlib è già eccessiva e le sue prestazioni sono già incredibilmente pessime, per ora LZMA è fuori discussione a scatola chiusa.

Se il tempo di decompressione dell'LZO è buono come affermato, allora è quello che userò.Penso che alla fine il server sarà comunque in grado di inviare pacchetti Zlib in casi estremi, ma i client possono essere configurati per ignorarli e questa sarà l'impostazione predefinita.

Answer 2

LZO potrebbe essere un buon candidato per questo.

Answer 3

zlib potrebbe essere un buon candidato: la licenza è molto buona, funziona velocemente e i suoi autori affermano che ha un sovraccarico minimo e il sovraccarico è ciò che rende problematico l'uso di piccole quantità di dati.

Answer 4

dovresti guardare OpenTNL e adattare alcune delle tecniche che utilizzano lì, come il concetto di stringhe di rete

Answer 5

Sarei propenso a utilizzare il bit più significativo di ogni carattere, che attualmente è sprecato, spostando gruppi di 9 byte verso sinistra, ti inserirai in 8 byte.

Potresti andare oltre e mappare i personaggi in un piccolo spazio: puoi ridurli a 6 bit (ad es.avendo solo 64 caratteri validi), ad esempio non consentendo le lettere maiuscole e sottraendo 0x20 da ciascun carattere (in modo che lo spazio diventi valore 0)

Potresti andare oltre mappando la frequenza di ciascun carattere ed effettuare una compressione di tipo Huffman per ridurre il numero medio di bit di ciascun carattere.

Sospetto che non esistano algoritmi in grado di salvare i dati meglio che, nel caso generale, poiché essenzialmente non c'è ridondanza nel messaggio dopo le modifiche già apportate.

Answer 6

Che ne dici di inviare una rappresentazione binaria del tuo script?

Quindi sto pensando alle linee di un albero sintattico astratto in cui ciascuna procedura ha un identificatore.

Ciò significa un miglioramento delle prestazioni dei client grazie all'analisi una tantum e una riduzione delle dimensioni dovuta alla rimozione dei nomi dei metodi.