Google présente « Courgette », son algorithme de compression différentielle
Pour réduire la taille des mises à jour de Chrome

Les rubriques (actu, forums, tutos) de Développez
Tags
Réseaux sociaux


 Discussion forum

Sur le même sujet
Le , par Idelways, Expert Confirmé 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 ?

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


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de Benav Benav
http://www.developpez.com
Membre habitué
le 22/02/2011 14:02
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".
Avatar de vintz72 vintz72
http://www.developpez.com
Membre confirmé
le 22/02/2011 14:15
Y'en a bien qu'ils font des block-busters avec "Ratatouille" !
Avatar de jpvincent jpvincent
http://www.developpez.com
Membre chevronné
le 22/02/2011 14:28
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
Avatar de pseudocode pseudocode
http://www.developpez.com
Rédacteur/Modérateur
le 22/02/2011 17:38
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.
Avatar de cd090580 cd090580
http://www.developpez.com
Membre habitué
le 23/02/2011 9:42
Ils engagent des cuisiniers chez Google ????

J'adore tous leurs termes de "cuisine"
Avatar de LittleWhite LittleWhite
http://www.developpez.com
Responsable 2D/3D/Jeux
le 23/02/2011 9:49
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
Avatar de abriotde abriotde
http://www.developpez.com
Membre éclairé
le 23/02/2011 12:01
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à.
Avatar de zeavan zeavan
http://www.developpez.com
Membre chevronné
le 23/02/2011 12:42
Haute voltige qui existe depuis un peu moins d'une decenie avec install shield et click once de microsoft.
Avatar de souviron34 souviron34
http://www.developpez.com
Expert Confirmé Sénior
le 23/02/2011 12:43


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...
Avatar de pseudocode pseudocode
http://www.developpez.com
Rédacteur/Modérateur
le 23/02/2011 14:16
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.
Offres d'emploi IT
Développeur Java - IDF (94) (H/F)
CDI
Synchrone technologies - Ile de France - Paris
Parue le 04/12/2014
Hacker bas niveau soft et hard
CDI
iBou.fr - Rhône Alpes - St Etienne
Parue le 15/12/2014
stage dev d'application -Grenoble H/F
Stage
BULL FR - Rhône Alpes - GRENOBLE - BULL ECHIROLLES
Parue le 10/12/2014

Voir plus d'offres Voir la carte des offres IT
 
 
 
 
Partenaires

PlanetHoster
Ikoula