Les delta-packages. Quelle idée... hum je ne trouve pas le mot, pas grave on va dire "génial". Ainsi je pourrais faire mes mises à jour sans devoir stopper mes téléchargements car ils ralentissent tout :-°

Continu ses petites optimisations qui fera de Setup un gestionnaire de paquet hors norme qui sera utilisé par ton geek préféré ;)

Au passage, désolé de pas pouvoir participer plus, en ce moment je me dégeekise ^^

Au passage, désolé de pas pouvoir participer plus, en ce moment je me dégeekise

Hum hum hum . Aurais-tu trouvé une certaine affinité avec une certaine personne du sexe opposé, et te forçant à plus sortir que coder ?

Ou alors c'est la neige qui tombe chez toi et qui te donne super envie de faire de la luge dehors ?

Merci en tous cas de trouver Setup intéressant. L'algo de diff avance, j'ai un truc qui marche en Python, je le passe en C tout de suite (C++ = trop lent, mais y'aura tout de même un peu de Qt dedans là où ça optimise, comme changer des mallocs en utilisation de QVector qui malloc les enregistrements par groupes).

PS: Au passage, ça existe dans presque tous les gestionnaires de paquets de vrais distributions, comme les Delta RPM, le truc que Debian essaie d'utiliser mais n'y arrive pas, même Pacman le gère .

Bonjour ,

J'ai quelques nouvelles : ça avance. Une étape importante du développement du point non dévoillé vient d'avoir été sauvée, ça marche et c'est rapide (enfin, relativement : 2 fois plus lent que bsdiff, mais c'est du C non-optimisé, ce sera plus rapide en C++ avec les classes genre QList qui évitent un certain nombre de petits mallocs).

Normalement, je pourrai vous dévoiler l'algo après-demain, ou plus tard. Sortie dans Setup en production pour dans deux semaines en même temps.

Ensuite, consolidation de Setup (fichiers .setup_bak quand l'utilisateur a modifié un fichier qu'on souhaite installer par exemple). Puis, Setup bêta1, et ainsi de suite, jusqu'aux -rc, puis enfin Setup 0.1 FINAL !

Re tout le monde .

Normalement, publication du procédé ce week-end, toutes les étapes nécessaires à la création du diff marchent.

Hier, un algo O(n^n) ( ) a réussi à produire le plus petit diff possible entre MISSISSIPPI et MISOUSSISSITTI : C2 02 4F 55 53 C4 82 04 04 00.

Court non ? . Bon allez, voici ce que ça veut dire :

• Saute 3 octets
• Insère «OUS»
• Saute 5 octets
• change PP en TT (opération arithmétique)

Malheureusement, c'est super lent.

J'ai alors trouvé un autre algo, qui est simple et normalement rapide. Je vous donnerai des nouvelles.

lent pour le créer ou pour l'appliquer ?

très bon travail =), j'ai hâte de virer pacman pour mettre setup =) .

À créer. L'application est quasi instantanée : O(n), ou n est le nombre d'instructions dans le patch (donc plus petit que la taille du patch).

Le code de l'application (dans le sens "appliquer le patch", l'appli C entière fait 1000 lignes au moins) :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

 while (1)
{
    // Lire la commande
    ret = read(patchfd, &c, 1);
    pos++;

    if (ret == 0)
    {
        // Fin de fichier
        break;
    }
    else if (ret < 0)
    {
        close(patchfd);
        close(filefd);
        err("Impossible de lire la commande");
    }

    // Commande
    command = (c >> 6);
    arg = (c & 0x3F);
    arg++;          // Le 0 n'est pas utilisé (ça ne sert à rien), 
                    // mais codé, alors on diffère pour l'utiliser quand-même

    // Éxécuter la commande
    switch (command)
    {
        case OP_INSERT: /* Insertion */
            // Arg = nombre d'octets du patch à écrire dans la sortie
            ret = read(patchfd, buffer, arg);
            pos += arg;

            CHK_RET_READ

            ret = write(1, buffer, arg);

            CHK_RET_WRITE
            break;

        case OP_REMOVE: /* Suppression */
            // Arg = nombre d'octets de filefd à sauter, avec seek()
            if (lseek(filefd, arg, SEEK_CUR) == -1)
            {
                close(patchfd);
                close(filefd);
                err("Impossible d'avancer dans le fichier source");
            }
            break;

        case OP_OP: /* Opération arithmétique */
            // Arg = nombre d'octets à additionner entre eux
            for (counter=0; counter<arg; counter++)
            {
                // Lire un octet du patch dans c
                ret = read(patchfd, &c, 1);
                pos++;

                if (ret < 1)
                {
                    close(patchfd);
                    close(filefd);
                    err("Impossible de lire un octet dans le patch");
                }

                // Lire un octet du fichier dans c2
                ret = read(filefd, &c2, 1);

                if (ret < 1)
                {
                    close(patchfd);
                    close(filefd);
                    err("Impossible de lire un octet dans le fichier d'entrée");
                }

                // Additionner les deux dans un uint
                summ = (unsigned int)c;
                summ += (unsigned int)c2;

                // Écrire l'octet de poids faible dans la sortie
                ret = write(1, &summ, 1);

                if (ret < 1)
                {
                    close(patchfd);
                    close(filefd);
                    err("Impossible d'écrire un octet dans la sortie");
                }
            }
            break;

        case OP_SKIP: /* Avancer dans le fichier */
            // Arg = nombre d'octets de filefd à écrire dans stdout
            ret = read(filefd, buffer, arg);

            CHK_RET_READ

            ret = write(1, buffer, arg);

            CHK_RET_WRITE
            break;
    }
}

Simple non ? Normalement, vu comment c'est codé, il doit y avoir moyen d'appliquer 50Mio de patch par seconde, donc vraiment très très rapide .

toi qui est si perfectionniste, je te reconnais pas .

il parait que c'est plus rapide de faire ++i; que i++; et d'utiliser des if else au lieu des switchs

ça fait gagner quelques millionièmes mais il y a un début à tout xD .

Exactement ... en C++ .

Le code que j'ai posté vient de l'appli proof-of-concept en C ANSI pur, hors de Setup. Là, le i++ est conseillé, car il n'y a pas des histoires de operator++() appelés comme en C++.

Et pour les switchs, c'est une simple question de practicité. Généralement, j'en utilise aussi en C++, car ils sont bien plus rapides (le compilo sait qu'on compare avec des constantes, donc optimise ça avec des tables, génères des warnings quand on oublie une valeur d'une enum et qu'on n'a pas de default, etc). Par contre, ils n'acceptent justement que des constantes, et peu de machins sont constants en C++. En effet,

1

if (a == "machin") { }

n'est absolument pas constant, car si a est une QString, ou même std::string, ce n'est pas une bête comparaison ("cmp + je" en assembleur), mais bien operator==() qui est appelé. Et ça, le switch n'aime pas.

Il y a aussi que les switchs sont moins lisibles à mon gout, donc dans un chemin de code qui est déjà lent, le milliardième de seconde gagné ne vaut pas un niveau d'indentation en plus (tu ne trouveras pas un switch dans un if dans un while dans un if dans un for dans une fonction dans une classe dans un namespace ).

Et toc !

heureusement j'ai dit "il parait" .

Hello à tous ceux qui peuvent suivre ce sujet .

Bonne nouvelle, je touche enfin à mon but. Après pas mal de recherches, j'ai trouvé un algorithme extrêmement rapide ( O(N) quasiment ) qui permet de générer des patches 50% plus petits que bsdiff .

Autrement dit, je suis hyper heureux.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

$ setup diff fl.old fl.new
�OUSă
$ setup diff fl.old.bak fl.new.bak 
�D�super ă$▒�!.
$ time setup diff metadata.old metadata.new > metadata.patch

real    0m0.015s
user    0m0.007s
sys     0m0.007s
$ time bsdiff metadata.old metadata.new metadata.bspatch

real    0m0.046s
user    0m0.003s
sys     0m0.003s
$ ls -l metadata.{bs,}patch
-rw-r--r-- 1 steckdenis users 197 04.02.2010 19:29 metadata.bspatch
-rw-r--r-- 1 steckdenis users 191 04.02.2010 19:28 metadata.patch
$ #Maintenant, on compresse les deux
$ xz metadata.bspatch 
$ xz metadata.patch
$ ls -l *.xz
-rw-r--r-- 1 steckdenis users 248 04.02.2010 19:29 metadata.bspatch.xz
-rw-r--r-- 1 steckdenis users 104 04.02.2010 19:28 metadata.patch.xz

On voit donc que pour passer des métadonnées entre initng~0.6.99+git20091106~1 et ~3, Setup crée un patch fortement compressible de 191 octets alors que bsdiff en crée un de 197 octets.

On voit donc que les deux sont quasiment optimaux. Seule différence, le format de Setup est non-compressé, ce qui veut qu'il sera très bien compressé dans les paquets (oui, dans un paquet .delta, chaque fichier sera dans son delta, et non un delta pour le tout, c'est bien plus rapide à créer). Comme bsdiff se repose sur BZip2, un ensemble de fichiers .bspatch sera largement moins bien compressé qu'un ensemble de fichiers .spatch .

Donc, quand on prend le bsdiff le plus petit, c'est à dire non-compressé, et le patch Setup le plus petit, on se rend compte qu'entre 197 octets et 104 octets, il y a un gain de 48%.

Mieux, si je compresse le patche de Setup avec gzip, j'obtiens un fichier de 55 octets ! C'est un gain de 72% ! Bon, sur de gros patches, XZ sera peut-être plus efficace. Un autre test, avec "xz -F raw", qui permet de s'afranchir des en-têtes, me donne un fichier de 45 octets.

Bref, mon algo de diff est bien le plus performant, et de largement très loin, sur cet exemple (un fichier de texte avec peu de modifications). Je dois encore voir s'il bat bsdiff sur de gros fichiers binaires. Avant cela, je dois corriger un bug qui lui fait consommer plein de mémoire (environ 1,5 Gio pour un fichier de 400Kio, quand-même ).

Normalement, maintenant c'est la bonne. Publication de l'algo ce week-end si tout va bien. J'ai déjà créé la branche "delta" dans le dépôt Git, mais il n'y a encore rien dedans .

Patience, patience. La 3eme killer feature de Setup arrive .