Posts tagged compression

Zstandard 1.0

Bonjour,

La version 1.0 de Zstandard (ou zstd) est sortie. Elle se définie elle-même avec:

Zstandard est un algorithm de compression temps réel, fournissant de haut ratio de compression. Il offre une large gamme de compromis compression/vitesse, tout en étant soutenu par un décodeur très rapide (voir benchmarks). Il offre aussi un mode spécial pour les petites données, appellé compression par dictionaire, et peu crée un dictionaire depuis n’importe quel échantillon. La bibliotéque Zstandard est fourni comme logiciel libre sous la license BSD.

Le ratio de compression est proche de zlib qui est la référence en terme de compression. Elle est développer depuis longtemps par l’entreprise Facebook. Mais elle as des vitesses de compression et décompression bien meilleur que zlib. Ce qui pour moi la place comme bonne concurrente pour être le standard de compression des 30 prochaines années. De meilleur standard de compression veut dire une meilleur qualité de navigation et moins de ressources serveurs, et donc moins de coût pour Facebook et tout autre entreprise utilisant ces standards.

Son ouverture et interopérabilité avec une liste impressionnante de language vont participer fortement à son utilisation. Son utilisation pour le streaming est bonne car la compression est très efficace sur les petit contenu de données.

Je ne prévois pas changer CatchChallenger dans un futur proche, car bien que super, ce standard obligerai a refaire le packaging, le protocole, et la compression est peu utilisé dans le coeur du protocole de CatchChallenger (données vraiment trop petite ou non compressible).

Faite vous votre avis.

Tar and gzip

Le format TAR

Le format TAR

Pourquoi je l’utilise? Car c’est un format libre, ce qui garantit l’interopérabilité. Cela est important car cela me permet d’avoir toujours un logiciel pour faire et lire l’archive, sans license ou redevance. Cela permet d’encoder un tar sous Windows, Linux, Mac. Le faire ma propre lib pour le lire (donc réduire la taille du code car je limite les fonctionnalités à ce que j’ai besoin).

Tar and gzip

Tar and gzip

Cela me permet de découplé le format de stockage et la compression en elle même. Utiliser le format Tar avec gzip, zlib ou autre.

Comment est fait un Tar?

Vous avez les données, le contenu des fichiers. Et les métadonnées, nom, chemin, chmod, utilisateur, groupe, date de creation… Le format Tar tar fonctionne par bloque, les trous entre les bloques sont remplit par des 0 binaires. Le format est orienté stockage sur bande, il date de 1979 (normalisation 1988) mais eu des revisions entre temps.

Le fait de ne pas faire une bête sérialisation peu être gênant pour les systèmes de compression car il y as un trou de X 0 binaire. Cela rajoute du bruit, ce qui est problématique pour optimiser la compression. Si en plus l’on rajoute le faite que les entier sont stocké en chaine, ce qui réduit encore le ratio de compression comparé au binaire (voir: Compression et Binary dans le wiki de CatchChallenger). Cela réduit aussi les performances de l’encodeur et décodeur Tar de travailler en chaine et non pas en binaire (sans parler des limitations de la longueur des nombres représentés).

Un format mieux étudié pourrai avoir une taille bien inférieur sans compression et un meilleur ratio de compression.

Supprimer des meta données serai une bonne idée. Par exemple dans mon décompresseur je ne prends en compte QUE le fichier et son nom et j’ignore une grande partie et méta données: chmod, utilisateur, groupe, date de creation…

Conclusion

Je vais continuer à utiliser Tar dans le cadre de mes logiciels pour faciliter la création de plugin pour Ultracopier/Supercopier et pour l’intégration facile coté serveur dédié (99% de unix) pour CatchChallenger via un mirroir http (car pour le self hosting il y as déjà un rsync simplifié qui rends toute utilisation de Tar inutile).

Faire mon propre format n’est pas un probléme, le probléme serai de faire/maintenir et distribuer l’encodeur et le décodeur pour ce format.

Comment augementer votre compression sans toucher au format de compression?

Bonjour,

Aujourd’hui nous allons parler de compression de données lossless (sans changement de l’information).
Cela vas s’appliquer surtout au MMORPG CatchChallenger sur les points suivant: données de taille petite et moyenne, fortement compressible (xml, base64 continue).

Choix de la compression

Même si dans ce post se n’est pas le but, il faut bien choisir votre compression en fonction de votre système. Si vous voulez plus de bande passante en échange de cpu, si vous faites la compression dynamiquement ou non, …

Ratio de compression

Temps de compression

Réduire l’entropie

Nous allons avant tout commencer à reduire l’entropie. Vous devez donc supprimer toutes les données aléatoire inutile. Et faire que celle utile forme des suites.

Isoler les bloques aléatoires

Quand un bloque de donnés viens couper des données similaire:

items/1073.png 1 XXXX
items/1149.png 1 XXXX
items/1178.png 1 XXXX

Cela casse la compression (le système de compression switch tout le de temps compressé a non compressé). Cela n’as pas d’importance sur les grands bloque car le changement de mode est mineur vis a vis de la taille du bloque à compresser. L’idée est donc de les mettre la la fin pour que la compression soit maximal d’un coté et que le système de compression marque simplement un gros bloque comme non compressible.

items/1073.png 1
items/1149.png 1
items/1178.png 1
XXXX
XXXX
XXXX

Cela fait gagné 20% sur le format au dessus.

Binaire et pas hexa

Les formats de compression sont très sensible aux données non compressibles, les mettre en binaire et pas en hexa permet de réduire leur taille (10%).

Contenu

En fonction du contenu ET de la taille certaine compression seront plus avantageuse. Par exemple la zlib/gzip est plus efficace que xz/lzma sur les packet <300o.

Il n’y as pas une compression meilleur que les autres, chaque une ont leurs caractéristiques et leurs caractéristiques vis à vis de certaines données.

Zopfli

Zopfli permet de garder le format de compression actuel, mais à énormément besoin de cpu, ne jamais l’utiliser en dynamique. Il réduit de 10% à 50% la taille de vos compressions zlib/gzip (donc png aussi)

Mon outils tmxTileLayerCompressor pour compresser les bloques zlib dans les tmx avec zopfli permet de réduire la taille des tmx même sous leur forme compressé d’environ 10%.

Chose étonnante je ne constate pas de réduction de taille du datapack.tar.xz comme prévu. Idem coté tar sans xz, je pense que la modification est noyé dans un volume tellement gros d’informations qu’elle n’as pas d’influence. Par contre sur les pngs zopfli a une une influence notable.

Brotli

Je doit tester cette compression qui semble sympa surtout pour le streaming réseau avec des bloques de plus de 800o. Une compression proche de xz pour le statique, mais plus performant que gzip en -6 pour le streaming réseau tout en conservant un trés bon ratio. Mais hélas je trouve qu’il est trop orienté décompression, car la compression est bien trop lente mon gout, où en -6 c’est trés proche ou inférieur au ratio de zlib en fonction du contenu. Comme zlib: C’est parallélisable? Possible accélération hardware?

Voir le super lien: https://quixdb.github.io/squash-benchmark/

Lossy

Pour certain fichier comme les png/audio, les compressions sont lossless (sans perte de qualité/informations) mais j’ai appliquer un filtre de compression lossy (perte de qualité/informations) pour réduire la taille.

CatchChallenger

Voila les résultats spécifiques à CatchChallenger pour la liste des fichiers à télécharger:

Binaire 7% de taille en moins pour gzip
Suppression des retours de ligne pour les hash partiel (données non compressibles: réduction de 10% pour xz, 7% pour gzip
La spéparation en deux fichier (l’un compressé l’autre non) fait gagné 100o mais qui sont perdu par le protocole http (2x les entêtes pour les deux fichiers)
Répartition de la taille pour la base:
* 7Ko pour la liste de fichiers
* 500o pour la taille des fichiers
* 12Ko pour les hash partiel (non compressible)
Répartition de la taille pour le main:
* 2200o pour la liste de fichiers
* 500opour la taille des fichiers
* 2200opour les hash partiel (non compressible)

Compression de données pour l’envoi en ligne

Bonjour,

Je vais vous parler de la compression de données pour avoir sur la destination une arborescence. Cela peut être mis en parallèle avec l’html (page web), qui elle aussi a besoin d’avoir une arborescence de fichiers chargé coté client pour fonctionner. La compression de données est là pour que les données mettent moins de temps à télécharger. Mais le temps n’est pas que le temps de téléchargement, c’est temps de téléchargement + temps de compression + temps de décompression (que j’oublie car coté client, et donc par fait une une machine avec concurrence des ressources).

La compression ajoute une taille fixe (un entête) aux données. La grosse majorité des compressions ne commence à être efficace qu’à partir de 100 octets, mais n’est vraiment intéressante qu’après 15Ko. Pour on choisira une compression lourde, plus les tailles de début de compression, et compression optimal seront grosse (avec xz par exemple). De ce fait, compresser un fichier non compressible, ne fera que lui rajouter de la taille. Vous devez donc filtrer ce qui doit être compressé ou pas.

En fonction de votre protocole, les fichiers non compressés peuvent être envoyés à la queue ou dans un block. Dans mon cas, les fichiers sont assez petits <100octets, mais très répétitifs. La mise dans un block (suite binaire des données des différents fichiers), permet de tirer avantage de la compression sur ce genre de fichier. Mais la où l’on pouvait faire simplement un cache par fichier (pré-compresser le fichier, et renvoyer ceux-ci sur demande), c’est plus difficile car la compression et sur plusieurs fichiers. Certains choisiront de compresser dynamiquement à chaque fois. D’autres mettront un cache, car comme moi, le téléchargement du datapack ce fait soit depuis le début, soit depuis la mise à jour, donc la majorité des fichiers envoyés seront contenu dans les mêmes listes. La gestion du cache, ou même de la compression dynamique doit être bien faite car cela rend sensible votre serveur aux attaques DDOS.

Comme dans une page html, les fichiers de mon datapack sont liés entre eux. Les compresser ensemble permet de compresser la référence « toto » dans tout les fichiers d’un coup, ce qui rend la compression encore plus efficace. Or le protocole http actuel (le 1), ne fait pas ça (en plus de compresser en gzip), ce qui fait perdre beaucoup de bande passante.

Pour éviter le transfert et la compression de données inutiles sur le datapack, les ressources sont préalablement bien compressées (ogg en mono dans mon cas, quantization des fichiers png /!\ trés important, …). Je peux aussi virer tout les caractères utiles que pour la compréhension humaine des xml (indentation, retours à la ligne, …), mais qui peux être inversé.

J’ai aussi passé de la définition d’action sur fichiers de 8Bits à 1Bits pour avoir un minimum de compression naturelle, efficace sans compression, ou avec compression légère (gzip/zlib). Cela est applicable à tout. Par exemple pour l’envoi des déplacements des joueurs, il n’y a pas de compression car les données sont censées être toutes aléatoires. Et le reste compressé par le protocole: pas de nom de map, mais un id (de 8 ou 16Bits).

Au final, cela me permet de reduire la taille du datapack original de 4Mo à 200Ko transféré max sans les musiques.

Voila pour la compression des données pour la transmission dans vos applications.

Go to Top