Google présente « Courgette », son algorithme de compression différentielle
Pour réduire la taille des mises à jour de Chrome
Le 2011-02-22 13:24:26, par Idelways, Expert éminent sénior
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 ?
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 ?
-
BenavMembre habitué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".le 22/02/2011 à 14:02
-
jpvincentMembre éclairé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 çale 22/02/2011 à 14:28 -
pseudocodeRédacteurJ'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.le 22/02/2011 à 17:38 -
pseudocodeRédacteurGoogle 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.le 23/02/2011 à 14:16 -
wiztricksExpert éminent séniorSalut,
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.
- Wle 24/02/2011 à 20:33 -
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!le 28/02/2011 à 9:27 -
cd090580Membre avertiIls engagent des cuisiniers chez Google ????
J'adore tous leurs termes de "cuisine"le 23/02/2011 à 9:42 -
LittleWhiteResponsable 2D/3D/JeuxC'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 dedansle 23/02/2011 à 9:49 -
abriotdeMembre chevronné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à.le 23/02/2011 à 12:01
-
zeavanMembre éclairéHaute voltige qui existe depuis un peu moins d'une decenie avec install shield et click once de microsoft.le 23/02/2011 à 12:42