IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

ALM Discussion :

Google présente « Courgette », son algorithme de compression différentielle


Sujet :

ALM

  1. #1
    Expert éminent sénior
    Avatar de Idelways
    Homme Profil pro
    Développeur Ruby on Rails / iOS
    Inscrit en
    Juin 2010
    Messages
    1 374
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur Ruby on Rails / iOS

    Informations forums :
    Inscription : Juin 2010
    Messages : 1 374
    Points : 68 548
    Points
    68 548
    Par défaut Google présente « Courgette », son algorithme de compression différentielle
    Google présente « Courgette », son algorithme de compression différentielle
    Utilisé pour réduire la taille des mises à jour du navigateur Chrome



    Pour une application qui évolue aussi vite que Google Chrome, le téléchargement des nombreuses mises à jour pourrait devenir un véritable casse-tête si les utilisateurs devaient rapatrier chaque fois l'installable du navigateur (environ 10 MO)

    Nombre d'entre eux renâcleraient certainement à l'idée de saturer leur connexion de mises à jour volumineuses et répétées et risqueraient de les désactiver.

    La solution qu'utilise Google est de n'envoyer à l'utilisateur que les différences avec la version installée et laisser le navigateur générer la nouvelle version.

    Si cette manœuvre peut sembler triviale avec du code source, elle s'avère beaucoup moins évidente quand il s'agit d'applications compilées où une petite intervention sur le code source peut induire des changements considérables d'octets.

    Les (très nombreux) pointeurs internes du programme pourraient changer de valeurs et compliqueraient la différentiation.

    Éternels insatisfaits et obstinés de l'optimisation, les ingénieurs de Google ont donc développé leur propre algorithme de compression différentielle appelé « Courgette ». L'utilitaire bsdiff étant jugé bon, mais insuffisant.

    Courgette utilise un désassembleur primitif pour retrouver les pointeurs internes et divise le programme en trois parties : une liste des adresses des pointeurs internes, tous les autres octets et enfin une séquence d'instruction qui détermine comment ces octets pourraient être entrelacés et ajustés pour retrouver l'exécutable original.

    La différentiation des octets dépourvus de pointeurs (environ 80% de l'application) devient alors plus simple et bsdiff réduit ainsi de 30% la taille du fichier de différentiation.

    Courgette gère ensuite la partie pointeurs en introduisant des « labels » aux adresses. Ces adresses seront stockées dans des tableaux de symboles et les pointeurs seront remplacés par une liste d’index de tableaux. Cela permet de changer les adresses dans le tableau et porter les modifications correspondances dans la liste des index.

    Courgette désassemble selon le procédé sus-décrit l'exécutable original et celui de la mise à jour . Il lance ensuite cette procédure d'ajustement qui minimise grandement la taille du fichier de différentiation.

    Résultat, un format alternatif de différentiation qui est à la fois plus qu'un seul exécutable et moins qu'un exécutable.

    On ne sait pas si Google envisage de publier courgette sous licence open source.

    Mais on sait que beaucoup de développeurs espèrent déjà que Apple et Adobe mettent en place des solutions similaires.


    Source : Présentation de Courgette sur le projet Chromium

    Et vous ?

    Qu'en pensez-vous ?
    Aimeriez-vous un système similaire pour d'autres applications et d'autres outils ?

  2. #2
    Membre habitué Avatar de Benav
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2004
    Messages
    48
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Finance

    Informations forums :
    Inscription : Janvier 2004
    Messages : 48
    Points : 167
    Points
    167
    Par défaut
    La seule vraie question, c'est de savoir comment un groupe d'êtres humains suffisamment étendu pour qu'on puisse statistiquement considérer comme acquis qu'il comporte au moins un membre sain de corps et d'esprit peut décider d'appeler une de ses créations "Courgette".

  3. #3
    Membre averti Avatar de vintz72
    Profil pro
    Inscrit en
    Octobre 2005
    Messages
    154
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Octobre 2005
    Messages : 154
    Points : 316
    Points
    316
    Par défaut
    Y'en a bien qu'ils font des block-busters avec "Ratatouille" !

  4. #4
    Membre éclairé

    Profil pro
    Inscrit en
    Février 2010
    Messages
    119
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 119
    Points : 777
    Points
    777
    Par défaut
    c'est vraiment des génis ces types

    ils ont un système équivalent en javascript, pour google maps, qui fait que l'utilisateur ne télécharge que les lignes de JS (compilé) de la nouvelle version (par rapport au cache) et s'auto patche

    je n'imagine pas le cauchemard que ça doit être à inventer des trucs comme ça

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    J'admire l'effort de Google pour trouver de meilleures techniques de compression des updates pour gagner 600Ko.

    En meme temps, ca m'amuse de comparer ce gain avec la taille des données transférées lorsqu'on va sur la page d'accueil de Youtube ou Maps par exemple.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2002
    Messages
    245
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Décembre 2002
    Messages : 245
    Points : 320
    Points
    320
    Par défaut
    Ils engagent des cuisiniers chez Google ????

    J'adore tous leurs termes de "cuisine"

  7. #7
    Responsable 2D/3D/Jeux


    Avatar de LittleWhite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mai 2008
    Messages
    26 826
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mai 2008
    Messages : 26 826
    Points : 218 287
    Points
    218 287
    Billets dans le blog
    117
    Par défaut
    C'est très intéressant comme principe ... cela me rappelle les patcher de certains cracks... sauf que l'a, ils nous disent que cela fonctionne de manière générique.
    Est ce c'est compatible pour tout les systèmes d'exploitation, ou juste un vu que le format de l’exécutable dépend aussi du système d'exploitation.

    Toujours est il qu'il faudra télécharger la prochaine mis à jour intégralement pour avoir le patcher dedans
    Vous souhaitez participer à la rubrique 2D/3D/Jeux ? Contactez-moi

    Ma page sur DVP
    Mon Portfolio

    Qui connaît l'erreur, connaît la solution.

  8. #8
    Membre chevronné
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2007
    Messages
    884
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Juillet 2007
    Messages : 884
    Points : 2 018
    Points
    2 018
    Par défaut
    S'il y a une société innovante au monde c'est bien Google. C'est de la haute voltige ce qu'ils font et le résultat est là.
    Tout ce que j'écris est libre de droits (Licence CC0) et je vous incite à faire de même.

  9. #9
    Membre éclairé Avatar de zeavan
    Architect
    Inscrit en
    Avril 2003
    Messages
    590
    Détails du profil
    Informations personnelles :
    Âge : 47
    Localisation : Autre

    Informations professionnelles :
    Activité : Architect

    Informations forums :
    Inscription : Avril 2003
    Messages : 590
    Points : 774
    Points
    774
    Par défaut
    Haute voltige qui existe depuis un peu moins d'une decenie avec install shield et click once de microsoft.

  10. #10
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut



    J'avoue mon incrédulité devant vos nombreux messages....

    Comme si c'était extraordinaire.....


    Mais DEC pour ne citer qu'eux, mais aussi HP et autres, pratiquent le patchage binaire depuis plus de 25 ans.... Les VMS updates de 1984 étaient déjà du binaire, qui allaient s'insérer directement au bon endroit dans le binaire du kernel....




    Ou comment faire du marketing avec le fil à couper le beurre...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  11. #11
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    Mais DEC pour ne citer qu'eux, mais aussi HP et autres, pratiquent le patchage binaire depuis plus de 25 ans.... Les VMS updates de 1984 étaient déjà du binaire, qui allaient s'insérer directement au bon endroit dans le binaire du kernel....
    Google utilise déjà les techniques usuelles de patchage binaire, à l'aide de bsdiff/bspatch. Là, il s'agit de procéder à une optimisation du "binaire" à patcher.

    Traditionnellement, lorsqu'on ajoute une ligne dans un source, le binaire résultant se voit ajouté une suite d'instructions. So far, so good.

    Le problème c'est que cette suite d'instruction "décale" la position du reste des instructions. Et donc ca décale d'autant les adresses des pointeurs. Conclusion, le reste du binaire se trouve modifié sporadiquement à chaque fois qu'il y a une adresse de pointeur.

    L'idée de Google c'est donc de désassembler le binaire afin d'avoir des labels au lieu d'avoir des adresses mémoires, de procéder au diff/patch sur ce code désassemblé (donc uniquement sur la suite d'instructions qui a changé), puis de réassembler le code ce qui remplace les labels par les nouvelles adresses mémoires.

    J'ai un peu simplifié la problématique, mais c'est pour clarifier les choses.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Membre actif
    Avatar de TheDrev
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    310
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Novembre 2006
    Messages : 310
    Points : 263
    Points
    263
    Par défaut
    décidément ces appellations commerciales sont de plus en plus idiotes
    all your base are belong to us.

  13. #13
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    L'étape suivante sera de lyophiliser les courgettes ...
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  14. #14
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    ben non...

    Soit les virtualiser, soit les "nuagifier" (cloud)

    Vous me referez bien une t'ite courgette dans un nuage !!

    (ça fait penser à Astérix chez les Bretons )
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  15. #15
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 235
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 235
    Points : 36 684
    Points
    36 684
    Par défaut
    Salut,

    Citation Envoyé par souviron34 Voir le message
    Mais DEC pour ne citer qu'eux, mais aussi HP et autres, pratiquent le patchage binaire depuis plus de 25 ans.... Les VMS updates de 1984 étaient déjà du binaire, qui allaient s'insérer directement au bon endroit dans le binaire du kernel....
    Patcher les binaires posait le même problème que le truc de Google résoud: il faut inscruster au bon endroit un JUMP vers le code patché et revenir au code "normal" ensuite pour ne pas foutre le b... sur le code qu'on ne voulait pas toucher. En gros, on faisait une sorte de dérivation.

    L'intérêt de cette techno avant "internet" était non seulement de réduire la quantité d'information à transférer, et de pouvoir le faire sous forme texte.

    Cette technique a été abandonnée avec l'arrivée des cpu Risc et la possibilité de transférer des binaires assez vite:
    - trop d'instructions à écrire pour se passer d'un compilo,
    - la dérivation jette à la poubelle les optimisations effectuées, ce qui est dommage,

    Il n'est pas complètement farfelu de remettre ce genre de techno au goût du jour: imaginez un gadget qui ne puisse se mettre à jour que via des connexions WEB.
    Espérez en vendre beaucoup et d'avoir le même succès que Windows auprès des crackers. Il va falloir réaliser une infrastructure et disposer de la bande passante nécessaire pour diffuser des patchs de sécurité raisonnablement vite.
    Si on peut diviser la taille du problème par 10 ou 100, on n'a peut être pas encore la solution mais... un peu moins mal à la tête.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  16. #16
    Invité
    Invité(e)
    Par défaut
    On peut dire que Google cherche vraiment à bien faire les choses: c'est assez rassurant quelque part
    Merci wiztricks d'avoir résumé le détail du concept!

Discussions similaires

  1. Réponses: 5
    Dernier message: 04/05/2012, 00h22
  2. Réponses: 0
    Dernier message: 22/02/2011, 14h24
  3. Réponses: 1
    Dernier message: 01/02/2011, 10h46
  4. Réponses: 17
    Dernier message: 10/12/2010, 10h07
  5. Réponses: 0
    Dernier message: 15/10/2009, 08h16

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo