Bonjour ,

Comme dit dans mon précédant journal, j'utilise maintenant plus Setup que Pacman (gestionnaire de paquets d'ArchLinux, distro que j'utilise), et pourtant, je passe mon temps à jouer avec les paquets !

Ceci est du au fait que je recompile tous les paquets Logram depuis Logram, et que je dois donc installer les paquets -dev, mettre à jour les anciens avec les nouveaux, voir ce qu'installe un paquet, récupérer leurs descriptions, construire, etc. Bref, tout Setup (sauf les communications, pour le moment) est utilisé .

Trois lenteurs dans Setup

Globalement, Setup est bien ce que je pensais : une foudre de guerre. L'installation des paquets est extrêmement rapide, la résolution des dépendances aussi (sauf exceptions, d'où mon journal), les informations, la mise à jour de la base de donnée, etc.

Bref, je suis extrêmement satisfait. Pendant que Pacman installe OProfile, j'ai le temps d'installer GCC, G++, GFortran, les binutils et libc-dev dans Setup que je dois encore attendre Pacman.

Il y a néanmoins trois points de Setup qui sont relativement lents :

• Le solveur s'emballe. Dans certaines conditions (ici quand je met à jour ncurses vers ma version locale), il occupe toute ma RAM et mon proc à 100%. Un petit coup de GDB me montre qu'il entre dans une récursion sans fin, difficile à résoudre (j'ai pas cherché). J'avais déjà eu des problèmes avec la mise à jour de Qt (40 paquets), qui me générait près d'un million de branches.
• L'exportation de la distribution prend un peu de temps (mais c'est très raisonnable, c'est juste un des seuls endroits de Setup pas «instantané». Ça prend 1m d'exporter les dépôts officiels, à vue de nez).
• Quand on vient d'installer un paquet, même un petit, Setup prend 2 ou 3 secondes pour recréer /var/cache/lgrpkg/db/installed_files.list.

Les deux derniers points sont le fait de la gestion des fichiers des paquets. Ce n'est pas gênant, mais les paquets ont un fort pouvoir de nuire à cet endroit (linux-source : 1 paquet, 33507 fichiers, dans sa version 2.6.33.4). D'ailleurs, linux-source contient plus de fichiers que tous les autres paquets réunis, ce qui fait qu'exporter experimental-all prend 3 fois plus de temps qu'experimental-i686 !

C'est un point qui me dérange car il ne dépend pas du nombre de paquets (croissant plus ou moins linéairement avec le temps, c'est à dire en même temps que la puissance des ordinateurs), mais bien de leur contenu, qui croît exponentiellement !

Côté export, c'est MySQL qui prend un grand coup, du fait que je lui envoie une requête qui construit la liste de tous les paquets de la distribution, sous une forme facilement parsable en C++. Problème, ça lui demande une concaténation, et il n'aime pas :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

SELECT
    CONCAT(dir.path, '/', dir.name, '/', file.name),
    pkg.name,
    file.flags
FROM packages_file file
LEFT JOIN packages_directory dir 
    ON dir.id=file.directory_id
LEFT JOIN packages_package pkg 
    ON pkg.id=file.package_id
WHERE pkg.arch_id=%1 
    AND pkg.distribution_id=%2
ORDER BY dir.path ASC, 
         dir.name ASC;

Le résutat est de la forme :

Lenteur du solveur

Le premier point m'embête bien plus, car ce n'est pas une lenteur, c'est un blocage. Le solveur ne va pas prendre 10s, pas 1 minute, pas 30 minutes, mais bien une infinité de temps et de mémoire à résoudre certains problèmes.

La source de cela n'est pas un problème dans l'algorithme, mais bien un bug. Seulement, le code est complexe (pour ceux qui ont lu, vous savez de quoi je parle ), l'algo pas simple du tout, et il y a plein de petits détails (qui peut me dire quelle est la différence en pkg, mpkg et dpkg ?).

De plus, une quantité de temps considérable est passée à ... dupliquer les branches ! En effet, si on a 15 branches, et qu'on a besoin de forker, on va se retrouver avec pas moins de 30 branches. Si chaque branche était bien remplie, on voit où ça mène.

Le problème est particulièrement vrai avec les mises à jour. Par exemple, si je met à jour 10 paquets, donc que chacun de ces paquets a au moins 2 versions, je me retrouve avec 2x2x2x2x2x2x2x2x2x2 = 1024. Oui, 1024 branches d'au moins 10 paquets.

Et encore, il y en a bien plus, car pour chaque paquet, on peut :

1. Installer la version A
2. Installer la version B
3. Installer un éventuel provide
4. Supprimer tout ce qui en dépend

Le point 4 étant récursif, et pouvant mener à :

1. Supprimer tout ce qui en dépend
2. Installer d'autres provides (versions, etc)

Problème, si on veut mettre à jour A et B, et que A dépend de B, ça commence à faire beaucoup, car le point 4 de B, supprimer A (qui dépend de B), va entrainer deux choix pour A : soit supprimer ce qui en dépend (ici rien, mais on peut avoir C), soit installer une autre version de A, c'est à dire soit l'ancienne, soit la nouvelle.

Je n'ai aucune idée du nombre de branches que ça fait, mais on ne doit pas être loin de 2^2^2. Ok, ça va encore, mais si on a dix paquets, on se prend un 2^10^10 = 2^10000000000. Oufti, c'est beaucoup .

De plus, l'occupation mémoire n'est pas négligeable non-plus. Il y a plein de doublons, chaque paquet étant copié dans toutes les branches dans lesquelles il se trouve. Plein de RAM perdue, plein de mallocs, plein de fragmentation de la mémoire, plein de problèmes :

La solution : présentation en arbre

La création de branches est un algorithme complexe, surtout qu'il faut garder trace des branches, puis les peser. Bref, plein de code et plein de bugs.

J'ai donc pensé à une amélioration de l'algorithme, qui peut se considérer comme deux choses :

• Un algo qui fusionne les branches quand des paquets sont partagés.
• Un algo tout neuf qui fait ce que les branches devraient faire, mais correctement.

La précédante situation peut être représentée très élégamment :

Chaque paquet n'est représenté qu'une seule fois. C'est simple, élégant, et très puissant.

Construction de l'arbre

L'arbre est encore assez simple à construire, mais c'est difficile à décrire.

• Soit T un tableau de Node, contenant comme unique élément le Node courant
• Pour chaque dépendance
  • Pour chaque paquet qui correspond (différentes versions, provides)
    • Créer le node N pour ce paquet
    • Appeler cette fonction pour N. Elle retourne un tableau des derniers enfants de N, T'
    • Lier N comme enfant de chaque Node dans T (un noeud peut avoir plusieurs enfants et plusieurs parents)
    • T = T'
• Retourner T

Le point intéressant est l'étape «T = T'», qui permettra peut-être de stocker T et T' comme étant un tableau global au solveur, et ainsi d'éviter une assignation de tableau (donc gestion de la mémoire complexe pour Qt), et de la place prise sur la pile.

On voit que l'algo est simple, et récursif. L'arbre se construit noeud par noeud, chaque noeud ayant un paquet, et un poids (ainsi que des parents et des enfants).

Ok, ce n'est pas très bien expliqué, mais c'est déjà pas clair dans ma tête .

La relations parents/enfants me fait un peu peur, car une relation Plusieurs à Plusieurs est assez difficile à bien faire. Il faut que ce soit rapide, en évitant d'avoir une QList pour chaque noeud (on perd alors l'intérêt de l'algorithme). Peut-être un système à base de QHash, même si ça revient plus ou moins à une QList de QList, c'est à dire une QList par noeud . Je vais devoir Googler.

Sinon, c'est bien plus simple qu'avec les branches ! Une seule fonction (en tous cas pour le moment), des conditions simples, très simples.

Car pour le moment, je ne décris en rien les opérations (installation, suppression), le conflit de ces opérations (on veut installer un paquet qu'on veut supprimer), les dépendances en boucles (plus généralement : vouloir installer/supprimer un paquet qu'on veut déjà installer/supprimer).

Le cas des dépendances en boucle

Ce dernier point m'a amené (il y a disons 30 minutes ) à réfléchir un peu. En effet, si on a un arbre du genre A dépend de B ou C, B dépend de E, C dépend de D qui dépend de E. Ok, vous voyez ? On a dont ABE et ACDE, qui sont joint en A et en E. Vu ?

Bref, si maintenant, on a E qui dépend de C, on a un petit problème. En effet, on ne peut pas ignorer C, car bien qu'il soit dans ACDE, il n'est pas dans ABE. L'ignorer casserait ABE.

Il faut donc ajouter C dans la liste, ce qui reviendrait à ne pas gérer les dépendances en boucles. Ok, pas de problème ici, mais si X dépend e Y qui dépend de X, on a une boucle infinie. Mauvais.

Il faut donc traiter ce cas particulier avec un petit hack. Quand on ajoute un paquet, on remonte l'arbre tant qu'il ne part pas en branches (ABEXYZ et ACDEXYZ : EXYZ est une partie sans branches, commune aux deux groupes). Si on veut par exemple ajouter E, on remonte de Z. Y, ok. X, ok, E, tiens, il y est déjà. On peut donc ignorer ce paquet.

Ainsi, pas de branches cassées, pas de dépendances en boucles infinies.

En théorie, car l'algo n'est pas solide. Imaginez ceci :

Aïe ! On a une récursion infinie.

Une solution possible serait de compter combien de fois les branches divergent puis reconvergent, en s'assurant que ce sont les mêmes. C'est possible, mais il faut vraiment avoir une relation Plusieurs à Plusieurs très rapide pour ne pas ralentir l'algo !

Possible amélioration : remonter l'arbre, et vérifier que toute divergeance contienne le paquet cherché. S'arrêter quand on est arrivé en haut. Si on est arrivé en haut, ajouter le paquet. Sinon, ne pas l'ajouter. J'aime .

Pesage des branches

Ah, enfin quelque-chose d'un tout petit peu moins abstrait !

Premièrement, un des avantages de cette méthode est de garder l'arbre, qui est en quelque sorte «aplati» par l'ancienne. Pour le moment, Setup ne sait que présenter des branches, pesées, et il faut toutes les parcourir pour trouver celle qui est la mieux. Quand il y en a 1000, ça prend un peu de temps.

Ici, il est possible de présenter un choix, par exemple :

Liste des paquets à installer :

• brol~1.1
• truc~2.3
• chose~4.1

Pour satisfaire les dépendances, vous pouvez choisir entre les paquets suivants :

1. paquet1~1.2 : installera entre 12Mio et 54Mio, entre 8Mio et 23Mio de téléchargement, poids entre 134 et 456
2. paquet2~2.1 : installera entre 5Mio et 18Mio, entre 2Mio et 4Mio de téléchargement, poids entre 56 et 78

Votre choix : 2

Oufti ! Qu'est-ce que c'est cette horreur !

C'est simplement la killer-feature de l'algo . Considérons cet arbre d'exemple :

Note : erreur : le noeud 1 en bas, celui à gauche du 5,6, devrait être un 2

Chaque rond contient le poids de son paquet (ici entre 1 et 3). La légende de chaque connexion contient le poids minimum et maximum apporté par le paquet vers lequelle elle pointe.

Par exemple, les dernières connexions à droite sont évidentes (on a un paquet de poids 1 ou 2). Les deux connexions qui mènent à 3 sont le poids de 3 : entre 4 et 5. 4 = 3 + 1, 5 = 3 + 2.

Vous avez compris ? Chaque paquet a son propre poids, calculé par weight.qs (qui calcule donc le poids de paquets et non de branches, mais en guise de paquet, il aura un Node, donc avec des informations sur ses parents et enfants).

Le poids minimum d'un noeud est son poids plus le plus petit poids minimum de ses enfants. Si un noeud a un poids de 2 et des enfants de 1-5, 2-7 et 8-16, son poids minimum sera de 3 (2 + 1).

Le poids maximum est le poids du noeud plus le plus grand poids maximum de ses enfants. Dans l'exemple ci-dessus, c'est 18 (2 + 16).

Ainsi, il est possible de trouver la branche avec le poids le plus léger, ou le plus lourd. Sachez que ce que j'ai fait pour le poids est possible pour la taille installée ou téléchargée, d'où les phrases en «entre» dans l'exemple de sortie de Setup.

Avec ces extrémités, l'utilisateur sait où il va, et il a le contrôle. Setup lui permettra de remonter l'arbre s'il se trompe, l'interface graphique lui affichera l'arbre .

Le pesage automatique est également possible, pour le serveur de construction qui doit tout choisir tout seul. C'est assez simple : il suffit d'explorer l'arbre de haut en bas en prenant à chaque fois la branche dont le poids faible est le plus bas. Si plusieurs branches ont le même poids faible, alors départager avec le poids fort qui doit être le plus bas.

Les bugs que ça corrige

Normalement (je n'ai ni testé ni codé), ça devrait résoudre la lenteur du solveur de Setup. Ça résoudra aussi quelques problèmes :

• Pesage loufoque, comme par exemple une branche qui me supprimer bash (et qui est au passage cassée) en premier résultat, alors que je met simplement à jour readline. Il faut passer à la branche suivante 4 fois pour trouver la bonne. C'est inacceptable, car l'utilisateur appuiera automatiquement sur "y" .
• Erreur de pesée dans le serveur de compilation. Pour le moment, une branche a comme poids la version moyenne de tous ses paquets (version calculée bizarrement d'ailleurs). On veut la plus récente. Problème, si tous les paquets sont les mêmes dans deux branches, mais qu'une dépend de A~1.1 qui dépend de B~496, et que l'autre dépend de A~2.0 qui s'est débarrassé de la dépendance à B, la première, fausse, sera choisie. Ici, l'algo de pesée peut faire un truc du genre :
  • Pour chaque paquet :
    • S'il n'a qu'un enfant : son poids est 1, peser son enfant
    • S'il a plusieurs enfants : l'enfant le plus récent a un poids de 1, les autres ont un poids énorme (à définir). On pèse uniquement l'enfant le plus récent. Ainsi, on s'assure d'avoir la dernière version de tous les paquets . Il faut juste faire attention à l'ordre des enfantes (vérifier que ce sont les même paquets), donc là je dois faire attention.

Voilà, un gros journal pour un algo intéressant .