Quelle est la meilleure bibliothèque de compression pour de très petites quantités de données (3-4 kib?)

Question

Je travaille sur un moteur de jeu qui est vaguement descendu de Quake 2, en ajoutant des choses comme des effets scriptés (qui permet au serveur de spécifier des effets spéciaux en détail à un client, au lieu d'avoir un nombre limité d'effets codées en dur que le client est capable.) Ceci est un compromis entre l'efficacité du réseau de flexibilité.

Je l'ai frappé une barrière intéressante. Voir, la taille maximale des paquets est de 2800 octets, et que l'on peut sortir par client par image.

Voici le script pour faire un effet « étincelles » (peut-être bon pour les étincelles d'impact de la balle, les chocs électriques, etc.) http://pastebin.com/m7acdf519 (Si vous ne comprenez pas, ne transpire pas, il est une syntaxe personnalisée et j'ai fait sans rapport avec la question que je pose.)

Je l'ai fait tout son possible pour réduire la taille de ce script. J'ai même réduit les noms de variables à une seule lettre. Mais le résultat est exactement 405 octets. Cela signifie que vous pouvez adapter au plus 6 de ces par image. Je pense aussi à quelques changements côté serveur qui pourrait se raser vers le bas une autre 12, et un changement de protocole qui pourrait sauver une autre 6. Bien que les économies modifierais en fonction de ce script que vous travaillez.

Cependant, de ces 387 octets, j'estime que seulement 41 serait unique entre usages multiples de l'effet. En d'autres termes, il est un candidat de choix pour la compression.

Il se trouve que R1Q2 (un moteur Quake 2 à compatibilité descendante avec un protocole de réseau étendu) a le code de compression Zlib. Je pourrais soulever ce code, ou au moins suivre de près comme référence.

Mais est Zlib nécessairement le meilleur choix ici? Je peux penser à au moins une alternative, LZMA, et il pourrait facilement être plus.

Les exigences:

1. Doit être très rapide (il faut avoir très faible impact sur les performances s'il est exécuté plus de 100 fois par seconde.)
2. Doit entasser autant de données que possible dans 2800 octets
3. Faible encombrement de métadonnées
4. GPL compatible

Zlib est à la recherche de bien, mais est-il quelque chose de mieux? Gardez à l'esprit, rien de ce code est encore fusionné, donc il y a beaucoup de place à l'expérimentation.

Merci, -Max

EDIT: Merci à tous ceux qui ont suggéré de compiler les scripts en bytecode. J'aurais fait ce clear-- oui, je fais cela. Si vous le souhaitez, vous pouvez parcourir le code source correspondant sur mon site, bien qu'il soit toujours pas « enjolivée. »
Voici le code côté serveur:
composante Lua: http://meliaserlow.dyndns.tv:8000/alienarena/ lua_source / lua / scriptedfx.lua
composant C: http://meliaserlow.dyndns.tv:8000/alienarena/ lua_source / jeu / g_scriptedfx.c
Pour le script exemple précis que j'ai posté, cela devient une source de 1172 octets jusqu'à 405 bytes-- pas encore assez petit. (Gardez à l'esprit que je veux tenir le plus grand nombre possible de ces octets en 2800!)

EDIT2: Il n'y a aucune garantie que tout paquet donné arrivera. Chaque paquet est censé contenir « l'état du monde », sans compter sur les informations communiquées dans les paquets précédents. En général, ces scripts seront utilisés pour communiquer « bonbons pour les yeux. » S'il n'y a pas de place pour un, il est abandonné du paquet et c'est pas une grosse affaire. Mais si un trop grand nombre DROPpé, les choses commencent à paraître étrange visuellement et ceci est indésirable.

Answer 1

Mise à jour FINAL: Les deux bibliothèques semblent à peu près équivalent. Zlib donne environ 20% une meilleure compression, tandis que la vitesse de décodage de LZO est environ deux fois plus rapide, mais le coup de performance pour les deux est très faible, presque négligeable. Voilà ma réponse finale. Merci pour toutes les autres réponses et commentaires!

Mise à jour: Après la mise en œuvre de compression LZO et ne voyant que sightly une meilleure performance, il est clair que mon code est à blâmer pour la perte de performance (nombre massivement accru d'effets scriptés possibles par paquet, donc mon effet « interprète » devient beaucoup plus exercé.) Je voudrais présenter mes excuses humblement bousculent pour passer le blâme, et je l'espère, il n'y a pas de rancune. Je vais faire un peu de profilage et alors peut-être que je vais être en mesure d'obtenir des chiffres qui seront plus utiles à quelqu'un d'autre.

ORIGINAL POST:

OK, j'ai finalement eu le temps d'écrire un code pour cela. J'ai commencé avec Zlib, voici la première de mes conclusions.

La compression de

Zlib est insensément great. Il réduit de manière fiable les paquets de, disons, 8,5 kib jusqu'à, disons, 750 octets ou moins, même lors de la compression avec Z_BEST_SPEED (au lieu de Z_DEFAULT_COMPRESSION.) Le temps de compression est également très bon.

Cependant, je ne savais pas la vitesse de décompression de quoi que ce soit pourrait même peut-être ce mauvais . Je n'ai pas les chiffres réels, mais il doit être 1/8 seconde par prends paquet au moins! (Core2Duo T550 @ 1.83 Ghz.) Totalement inacceptable.

D'après ce que je l'ai entendu, LZMA est un compromis entre la performance pire par rapport à une meilleure compression par rapport à Zlib. Depuis la compression de Zlib est déjà surpuissant et sa performance est déjà incroyablement mauvais, LZMA est hors de la vue de la table invisible pour l'instant.

Si le temps de décompression de LZO est aussi bon qu'il est prétendu être, alors c'est ce que je vais utiliser. Je pense à la fin le serveur sera toujours en mesure d'envoyer des paquets Zlib dans les cas extrêmes, mais les clients peuvent être configurés pour les ignorer et ce sera la valeur par défaut.

Answer 2

LZO pourrait être un bon candidat pour cela.

Answer 3

zlib pourrait être un bon candidat - licence est très bon, travaille vite et ses auteurs disent qu'il a très peu les frais généraux et les frais généraux est la chose qui utilise pour de petites quantités de données problématiques.

Answer 4

vous devriez regarder OpenTNL et adapter certaines des techniques qu'ils utilisent là, comme le concept de chaînes réseau

Answer 5

Je serais inclinded d'utiliser le bit le plus significatif de chaque caractère, qui est actuellement gaspillée, en déplaçant les groupes de 9 octets vers la gauche, vous adapter à 8 octets.

Vous pouvez aller plus loin et cartographier les personnages dans un petit espace - vous pouvez les obtenir à partir de 6 bits (soit seulement ayant 64 caractères valides), par exemple, ne permettant pas des lettres majuscules et soustraire 0x20 de chaque personnage (de sorte que l'espace devient la valeur 0)

Vous pouvez aller plus loin en cartographiant la fréquence de chaque caractère et faire une compression de type Huffman pour réduire les bits de nombre de avarage de chaque caractère.

Je pense qu'il n'y a pas des algorithmes qui enregistre les données mieux que, dans le cas général, il n'y a pratiquement pas de redondance dans le message après les modifications que vous avez faites alrady.

Answer 6

Que diriez-vous d'envoyer une représentation binaire de votre script?

Alors, je pense dans les lignes d'un arbre de syntaxe abstraite avec chaque procédure ayant un identifiant.

Cela signifie gain de preformance sur les clients en raison de l'une analyse syntaxique du temps, et la diminution de la taille en raison de la suppression des noms de méthode.