Journal Un compresseur par ci, un compresseur par là. Au temps de l'algo des hackeurs.

Posté par  . Licence CC By‑SA.
Étiquettes : aucune
45
8
oct.
2020

UNE HISTOIRE DE LANGUE   Pour un peu, ceux qui ont plus de 50 ans ont lu « l'argot des hackeurs ». Remontons un peu le temps. À la naissance de linuxfr il y a 22 ans la démoscène palpitait encore mais c'était moins furieux. On commençait à avoir beaucoup de Ram, beaucoup d'espace disque. Ne rigolez pas. À cette époque on voyait encore pas mal de démos 5k, oui 5 kilos-octets mon jeune padaw… — oui jeune lecteur c'est presque une unité désuète pour toi : 1 ko c'est tout petit. Pour faire tenir « des trucs » là-dedans, il fallait beaucoup d'imagination. Et forcément, on bricolait des algos de compression. Cet art noble du hacker s'est perdu. Quand on se rencontre aujourd'hui on parle des termes à la mode, venus de l'argot des startup en passant par la case presse extasiée.

REVIVAL ?   Phillip Cutter et Arnav Chawla, deux étudiants américains ont pris l'initiative de documenter l'art de la compression. Il s'agit dans leur esprit de restaurer l'intérêt des cerveaux pour les techniques de compression et de les détourner des problèmes de grande ampleur à la mode comme la création du prochain cadriciel NodeJS. La compression demeure d'un grand intérêt, car la création de données numérique est de plus en plus gigantesque (on prévoit 463 Exaoctets de nouvelles données par jour vers 2025. D'ailleurs des recherches sont toujours effectuées dans ce domaine, tout intéret n'est pas perdu. Quoique ? Ce n'est plus un thème majeur.

S'AMUSER LIBREMENT   Ce qu'il faut faire c'est expérimenter. Quoi de mieux qu'un groupe de hackers avec l'envie d'inventer ? Pour bien faire les choses, nos deux étudiants ont placé une partie interactive dans leur topo. Ils vous encouragent à essayer, voir ce que ça donne, modifier, recommencer et ainsi de suite.

(Très funambulesquement traduit de l'intro.)

  • # chouette

    Posté par  . Évalué à 3.

    Une très belle initiative àmha.

  • # Travaux

    Posté par  . Évalué à 4.

    D'ailleurs des recherches sont toujours effectuées dans ce domaine, tout intéret n'est pas perdu. Quoique ? Ce n'est plus un thème majeur.

    Il continue à y avoir des travaux dessus. Mais pour ce qui prend le plus de place et qui grossi le plus avec le temps il faut un algo avec perte dédié comme les h265 et autres av1. On découle pas mal les formats d'images de ses formats de vidéo, mais jpeg n'a pas dit son dernier mot il me semble.

    Pour les compressions généralistes, j'ai l'impression d'avoir surtout vu passer des choses pour accélérer la compression plus que pour la plus compressif. Je pense par exemple à snappy.

    • [^] # Re: Travaux

      Posté par  (site Web personnel) . Évalué à 6.

      Y'a moins de challenge à faire du lossy que du loseless, non ?

      (j'ai une longue émission sur le sujet des codecs audio qui est montée et arrive)

      • [^] # Re: Travaux

        Posté par  (site Web personnel) . Évalué à 6. Dernière modification le 09/10/20 à 09:25.

        Je dirais plutôt le contraire (part de subjectif, pas de limite théorique bien définie, mix de plusieurs domaines, plein de potentiel d'idées novatrices …). T'as pas inversé ?

        C'est d'ailleurs ce qui faisait le charme des demos: la compression était ad-hoc parce que on pouvait se permettre de l'adapter au besoin mais aussi d'adapter légèrement le besoin pour s'autoriser la petite optim de malade qui ne marche que si … Il fallait un algo rapide et efficace mais dédié à un seul jeu de données.

        • [^] # Re: Travaux

          Posté par  . Évalué à 3.

          Idem. Quand tu fais de la compression avec perte tu dois te poser la question des critères qui définissent la qualité du document final et de mettre le curseur là où il faut dans ce qui est acceptable ou pas pour chacun de ces critères (respect des couleurs, netteté des objets, fréquences audio percevables par n% de la population, etc, etc). Ça me semble un sujet bien plus complexe.

        • [^] # Re: Travaux

          Posté par  . Évalué à 2.

          Qu'est ce qui distingue la compression de simplement une donnée compact. Si je prends protobuf, c'est quelque chose qui permet de faire produire une serialization compacte. Si on parle de bzip c'est de la compression.

          J'allais te dire que si la décompression n'est pas distingable du parsing, c'est plus un format compact que de la compression sauf que les formats d'images, de vidéos et de sont considéré comme de la compression.

          • [^] # Re: Travaux

            Posté par  . Évalué à 1.

            Si je prends protobuf, c'est quelque chose qui permet de faire produire une serialization compacte. Si on parle de bzip c'est de la compression.

            Il y a quand même une différence non négligeable entre les 2 : avec bzip, tu as juste besoin de l'algorithme pour lire le résultat. Avec protobuf, tu as besoin de l'algorithme + de la description protobuf pour lire le résultat. Je ne crois pas qu'avec uniquement le résultat tu puisses faire une lecture non ambigüe.

            Sinon en omettant ce point, je dirais que tu parles de compression quand tu agis sur un format naturel de manière à obtenir un format plus compact. Par exemple, si tu écris un texte en markdown, le format naturel va être un format texte que tu compresses en .bzip. Si tu décides de sérialiser tes données, le format "naturel" va être de l'xml, du json ou du protobuf, qui va être plus ou moins compact, et que tu pourras ensuite plus ou moins compresser.

          • [^] # Re: Travaux

            Posté par  (site Web personnel) . Évalué à 2.

            La compression consiste à supprimer ou réduire la redondance des données.

            • Ne pas stocker/transmettre 2 fois la même chose
            • Ne pas stocker/tranmettre ce qui n'a pasbesoin de l'être

            On peut regarder du côté de la théorie de l'information et la façon dont on peut définir la quantité d'information présente dans une donnée quelconque, en étudiant la probabilité dechaque bit d'être un 0 ou un 1, en fonction des bits précédents et de toute autre connaissance du récepteur de la donnée. Ce qui donne une limite théorique à la réduction de taillle qu'on peut obtenir, si on atteint le fomat de compression idéal ou chaque bit a exactement une probabilité de 0.5 d'être un 0 ou un 1.

            • [^] # Re: Travaux

              Posté par  . Évalué à 2.

              Tout cela marche aussi très bien pour les structures et sérialisation compactes :)

  • # Comment ça perdu?

    Posté par  (site Web personnel) . Évalué à 10.

    Pendant le mois de septembre 2020, près d'une vingtaine de nouvelles oeuvres de la demoscene dans les catégories <= 4Ko (je ne sais pas d'ou sort cette histoire de 5Ko, ça fonctionne par multiples de 2 bien sûr).

    La page de LZSA donne une comparaison des différents outils souvent utilisés, en terme d'efficacité de la compression ainsi que du temps de décompression.

    Dire que "cet art noble du hacker s'est perdu", ça me semble… quelque peu exagéré, au moins.

    (ce ne sont pas forcément les algorithmes les plus efficaces en terme de taille économisée, il y a des compromis pour garder une vitesse de décompression acceptable y compris pour des CPUs peu performants).

    • [^] # Re: Comment ça perdu?

      Posté par  . Évalué à 2.

      je ne sais pas d'ou sort cette histoire de 5Ko

      De ma mémoire abîmée … 5k ça me rapelle un truc des débuts du web, peut-être un des projets de David Siegel. J'ai du confondre.

    • [^] # Re: Comment ça perdu?

      Posté par  . Évalué à 3. Dernière modification le 09/10/20 à 13:36.

      Ca c'est pas totalement perdu, bien sûr qu'il est question de compression. Mais la problématique de bidouiller pour gagner en place dans chaque programme s'est perdue.

      Aujourd'hui la plupart des programmes sont développés vite fait sans trop se soucier de performances et encore moins de la RAM/disque. C'est que dans un second temps quand ils prennent de l'importance que l'on reviens sur les performances d'abord ensuite sur la RAM et très rarement sur l'utilisation disque.

      Et quand on parle de revenir sur les perfs, on parle juste de quelques optimisation assez simple. On cherche rarement a pousser le bouchon. Pour la RAM ou le CPU, parfois on a fait des trucs vraiment pourri que l'on va juste éliminer (avec genre un cache, ou en utilisant une librairie de compression). Je vois rarement des recherche très poussées sur les algorithmes (comme une compression maison). Ca veux pas dire que ça n'arrive pas.

      • [^] # Re: Comment ça perdu?

        Posté par  . Évalué à 4.

        Je vois pas le rapport entre la perf et la compression ?

        Il n'y a même pas de lien direct entre la taille d'un programme et sa performance. Par exemple C++ génère du code via les templates pour produire du code plus performant (mais d'autres chose comme le fait de dérouler les boucles rendent un programme plus rapide au détriment de sa taille).

        Je vois rarement des recherche très poussées sur les algorithmes (comme une compression maison).

        Tu veux dire qu'il y moins de syndrome NIH qu'avant ? C'est possible.
        Avoir des usages si particulier pour nécessité une compression vraiment différente de ce qui existe c'est rarissime. Après la compression n'est pas le seul moyen de gagner en taille utiliser des formats compacts peut être salvateur et encore une fois, tu a pléthore implémenté avec différentes fonctionnalités (traitement en flux, avec ou sans schémas,…). Il est urgent de se poser la question avant de vouloir réimplémenter soit-même ce genre de choses.

        • [^] # Re: Comment ça perdu?

          Posté par  (site Web personnel) . Évalué à 2.

          Euh, Zstd, développé par Facebook pour avoir un truc plus rapide et plus efficace que la zlib?

          Alors oui si on regarde le web frontend, le desktop et les applis mobiles, en ce moment, c'est pas trop l'aspect privilégié. Mais ça ne veut pas dire que les compétences sont perdues, seulement qu'il y a des endroits ou ça n'est pas justifié/pas rentable de le faire.

          Le logiciel embarqué a toujours des contraintes, mais pas forcément les mêmes. Pour gagner en durée de batterie sur un téléphone, il vaut mieux avoir des données moins compressées mais accessibles sans faire plein de calculs cpu pour les décoder, par exemple.

          • [^] # Re: Comment ça perdu?

            Posté par  . Évalué à 2.

            C'est exactement ce que je dis plus haut, mais ce ne sont pas les projets de google/fb qui font des outils de compression, mais des équipes dédiées à la performance dont c'est le travail. C'est un "à coté" au niveau de la boite, mais pas de l'équipe. Chacun de leur projet n'a pas son algo à lui qui espère être top moumoute.

          • [^] # Re: Comment ça perdu?

            Posté par  . Évalué à 3.

            Globalement, je pense que c'est surtout que les métiers de l'informatique, sauf cas particulier, ont tendance à s'éloigner du bas niveau, au moins pour la majorité des gens. Le travail de bas niveau est aujourd'hui celui de quelques spécialistes.

            Et la compression, c'est à mon avais de plus en plus une problématique de "bas niveau", souvent mise en oeuvre au niveau du "canal" (filesystem ou réseau), qui a eu une recherche très intensive à une période, et qui est assez bien résolue, au moins au niveau de la compression sans perte. De mémoire, on est assez proche des limites théoriques de Shannon, et il s'agit maintenant de régler des curseurs entre performances/compression (un compromis temps/mémoire assez classique, en somme). C'est donc naturel qu'on le trouve de moins en moins au niveau des couches hautes, où se concentre le gros du travail.

            • [^] # Re: Comment ça perdu?

              Posté par  (site Web personnel) . Évalué à 5.

              La compression c'est tout le contraire du bas niveau. C'est justement un truc purement algorithmique et indépendant du matériel.

              Si le problème était résolu, on aurait un algo super efficace de la mort qui tue et il serait implémenté par le premier disque dur/ssd/carte sd venue (qui ne voudrait pas faire x2 sur sa capacité de stockage affichée?). A priori ce n'est pas le cas.

              En télécom, on utilise la compression (et ça fait partie de la formation, en tout cas y'a 10 ans quand j'étais étudiant?) mais on a des problématiques qui font qu'on ne peut pas forcément atteindre les limites théoriques: contraintes de temps réel, de limitations matérielles (taille de la mémoire disponible) et de latence. En gros, on ne peut pas attendre d'avoir 4Go de données à envoyer pour les compresser de façon optimale, on est obligés de traiter ça en flux au fur et à mesure que les données arrivent.

              Après, oui, y'a plein de cas ou il n'y a pas besoin de compression à proprement parler (ça peut être suffisant d'utiliser un format approprié pour les données, ou il y aura déjà peu de redondance), ou alors, on peut utiliser un algorithme existant qui fonctionnera très bien pour les besoins identifiés. Ou bien on peut tomber sur des cas tordus, par exemple dans Haiku on a un gestionnaire de paquets qui a besoin de faire des accès aléatoires au contenu du paquet. Actuellement l'approche utilisée est de découper le paquet en blocs de 4K et de compresser chaque bloc séparément, et c'est pas hyper efficace. Y'a probablement mieux comme algo de compression qui permet de décompresser une partie aléatoire du flux (sans décompresser tout ce qu'il y a avant), non? Des suggestions?

              • [^] # Re: Comment ça perdu?

                Posté par  . Évalué à 3.

                La compression c'est tout le contraire du bas niveau. C'est justement un truc purement algorithmique et indépendant du matériel.

                Je me suis sans doute pas très bien exprimé. Ce que je voulais dire, c'est que c'est souvent implémenté dans des couches assez basses, certes en logiciel, mais souvent dans des micro-contrôleurs, et bien souvent quand même, on les retrouve en ASIC (c'est encore plus vrai pour la compression avec perte).

                Mais je viens du codage et de la crypto, ce sont des problématiques qui peuvent être très théoriques mais qui se retrouvent pourtant traitées à assez bas niveau dans les piles, très très souvent en matériel, encore plus en embarqué, ça biaise sans doute ma vision. (Mais nous, on ajoute de la donnée inutile ;) )

                Si le problème était résolu, on aurait un algo super efficace de la mort qui tue et il serait implémenté par le premier disque dur/ssd/carte sd venue

                Ça peut être résolu au sens où on peut prouver qu'on n'est vraiment pas loin du max sans que ce soit très intéressant dans tous les cas.

                (qui ne voudrai pas faire x2 sur sa capacité de stockage affichée?).

                Celui qui ne veux pas faire un x3 sur le temps d'accès ? Clairement, le passage au SSD a montré que les gens étaient prêts à renoncer à de la capacité pour gagner en temps d'accès.

                Pour continuer sur le stockage, des appliances qui de vendent un FS très compressé (à base de dedup et de compression pure et dure), il y en a quand même pas mal. Mais c'est souvent réservé aux cas où c'est un réel besoin. Du point de vue de l'OS et de l'application métier, c'est un stockage par bloc standard. Là encore c'est une problématique traitée à bas niveau (ou en tout cas en embarqué), celui du contrôleur de disque.

                Je ne dis pas que c'est jamais intéressant pour les couches hautes de regarder du côté de la compression, je tente juste une explication de pourquoi on a l'impression de moins le voir. Du point de vue du développeur web, la compression des donnée en transit, c'est
                une option de config d'apache/Nginx…

                • [^] # Re: Comment ça perdu?

                  Posté par  (site Web personnel) . Évalué à 2.

                  Du point de vue du développeur web, la compression des donnée en transit, c'est une option de config d'apache/Nginx…

                  Ah ah ah ah ah ah !

                  • [^] # Re: Comment ça perdu?

                    Posté par  . Évalué à 2.

                    Je comprends pourquoi tu rigole. Mais mis à part la compilation de js (et éventuellement un peu de truc type optipng), le gros des gains web c'est plus lié à la latence qu'au débit et évidement au cache.

              • [^] # Re: Comment ça perdu?

                Posté par  . Évalué à 5.

                La compression c'est tout le contraire du bas niveau. C'est justement un truc purement algorithmique et indépendant du matériel.

                Tu veux de la perf sans aller en bas niveau ? Il y a une part théorique, mais ça n'est pas pour rien qu'on attends que les h265 et consort soient brulés sur silicium pour s'en servir.

                qui ne voudrait pas faire x2 sur sa capacité de stockage affichée?

                Celui qui ne veut pas perdre la moitié de ces données à chaque secteur perdu (voir des compromission ), qui ne veut pas de latence, celui n'a pas besoin de Tio de données,…

                Si le problème était résolu

                En terme de compression sans perte (les zip, gzip et autre lzma) il n'y a pas grand chose. Ils dérivent tous du même principe. Ce qui fait la différence c'est justement des aspects assez bas niveau de performance en exécution.

                Pour les algos destructif, ils font appel la connaissance de nos sens, des mathématiques un chouia poussées et des concepts bas niveau pour savoir ce qui s'exécute efficacement ou non. Typiquement ce que la plupart des projets n'ont pas forcément à investir.

                Actuellement l'approche utilisée est de découper le paquet en blocs de 4K et de compresser chaque bloc séparément, et c'est pas hyper efficace. Y'a probablement mieux comme algo de compression qui permet de décompresser une partie aléatoire du flux (sans décompresser tout ce qu'il y a avant), non? Des suggestions?

                Ça ne dit pas bien ce que vous faites et comment ni ce qui te gêne. C'est exactement ce que propose xz c'est ce que vous utilisez ?

  • # Réduire le volume de données...

    Posté par  . Évalué à 10.

    Compresser c'est une chose, mais est-il vraiment utile de capturer et publier autant de photos, de vidéos, dans des résolutions aussi démentielles ?

    L'art qui s'est perdu n'est pas celui de la compression mais de l'ascétisme je crois.

    • [^] # Re: Réduire le volume de données...

      Posté par  . Évalué à 3.

      Bonjour,

      C'est tout à fait vrai, et c'est souvent mentionné ici par ailleurs, il en va de même des usages immodérés de la bande passante. Ce qui ne va pas sans problème par ailleurs, quand au niveau professionnel on voit des collègues et des élèves ingénieurs lancer des applis à distance au travers d'un VPN (IDE, suites bureautiques, progiciels de calcul/simulation numérique etc…) car nous avons collectivement perdu la bataille de l'apprentissage de la sobriété(rusticité) numérique.

    • [^] # Re: Réduire le volume de données...

      Posté par  . Évalué à 2.

      Surtout en photo.
      J'ai vécu l'arrivée et le développement de la photo numérique. Les images s'amélioraient, et puis on s'est retrouvé avec des 10 aines de millions de pixels pourris par du bruit qu'on doit retravailler avec des tétrachiées d'algos pour masquer le bruit, alors qu'avec deux fois moins de pixels, on aurait moins de volume de données, mais tout autant d'information, et moins besoin de « nettoyer » les images derrière… et plus de sensibilité.

  • # ...

    Posté par  . Évalué à 4.

    Ce qui c'est perdu c'est aussi la curiosité de comprendre comment ça fonctionne et d'expérimenter des choses.

    Je ne sais pas s'il y a beaucoup de dev qui sorte d'école qui sache comment les systèmes actuels/passés fonctionnent.

    • [^] # Re: ...

      Posté par  (site Web personnel) . Évalué à 9.

      rejoins un fablab, tu verras qu'il reste des jeunes qui ont la niak :-)

    • [^] # Re: ...

      Posté par  . Évalué à 3.

      Qui sache, peut-être pas, mais qui savent, surement plus. Ca dépend des écoles et des profs, si il y en a encore pour enseigner les systèmes legacy ou si ils sont tous orientés vers des techos actuelles.

      Emacs le fait depuis 30 ans.

    • [^] # Re: ...

      Posté par  (site Web personnel) . Évalué à 10.

      En tout cas il y a toujours autant de grincheux qui pensent que c'était mieux avant!

  • # Clip vidéo

    Posté par  . Évalué à 1.

    Ça me rappelle ce vieux clip vidéo de plusieurs minutes tenant sur peut-être 800 octets. J'ai dû en entendre parler par ici. Quelqu'un a un lien sous le coude svp ?

    • [^] # Re: Clip vidéo

      Posté par  (site Web personnel) . Évalué à 2.

      vieux clip vidéo de plusieurs minutes tenant sur peut-être 800 octets

      voir dans les contenus https://linuxfr.org/tags/i2bp/public

      de rien ;-) (il y a star trek en mode texte dans les commentaires iirc)

      • [^] # Re: Clip vidéo

        Posté par  . Évalué à 1.

        Hin hin hin !
        Je parlais d'une démo, pas d'une vidéo filmée puis compressée.

        J'avais raté l'aventure i2db, eh bien j'avais pas raté grand'chose.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n’en sommes pas responsables.