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

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

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

Le , par Idelways

93PARTAGES

2  0 
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 ?

Une erreur dans cette actualité ? Signalez-nous-la !

Avatar de Benav
Membre habitué https://www.developpez.com
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".
7  2 
Avatar de jpvincent
Membre éclairé https://www.developpez.com
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
3  1 
Avatar de pseudocode
Rédacteur https://www.developpez.com
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.
2  0 
Avatar de pseudocode
Rédacteur https://www.developpez.com
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.
2  0 
Avatar de wiztricks
Expert éminent sénior https://www.developpez.com
Le 24/02/2011 à 20:33
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
2  0 
Avatar de
https://www.developpez.com
Le 28/02/2011 à 9:27
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!
1  0 
Avatar de cd090580
Membre averti https://www.developpez.com
Le 23/02/2011 à 9:42
Ils engagent des cuisiniers chez Google ????

J'adore tous leurs termes de "cuisine"
0  0 
Avatar de LittleWhite
Responsable 2D/3D/Jeux https://www.developpez.com
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
0  0 
Avatar de abriotde
Membre chevronné https://www.developpez.com
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à.
0  0 
Avatar de zeavan
Membre éclairé https://www.developpez.com
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.
0  0