Aujourd'hui, je vais vous parler de ce que j'ai codé cet après-midi, mais surtout de ce que j'ai pensé depuis maintenant un peu plus d'un mois.
Sous Linux, nous bénéficions généralement d'un système de gestion des paquets, assez performant. Un des problèmes que chacun de ces gestionnaires doit vaincre est la gestion des dépendances.
En effet, des paquets peuvent ne pas vouloir s'installer en compagnie d'autres, ou peuvent en nécessiter. Tout ceci peut vite devenir très complexe, quand un système de dépôt, de versions multiples, etc, sont mis en jeu.
Nous avons actuellement deux solveurs de dépendances qui sont fort connus, et quelques autres. Un des plus utilisé est APT (Advanced Packaging Tool) de Debian, qui résoud très bien tout un tas de dépendances très complexes, et ce très rapidement. C'en est presque devenu une référence. Un autre est Zypp, utilisé par OpenSuSE. Il a ouvert la voie à tous les autres en étant le premier à utiliser un algorithme de satisfaction booléenne. Nous pouvons également citer Yum de Fedora, et URPMI de Mandriva.
Après ces solveurs, il y a les "incomplets", c'est à dire ceux qui marchent mais ne permettent pas de gérer tous les cas. Nous avons Portage chez Gentoo qui ne permet pas de gérer les reverse-dependencies (donc si vous supprimez une bibliothèque, tous les programmes qui en dépendent restent, cassés), ainsi que Pacman de Arch Linux, qui semble également ne pas gérer les dépendances inverses. Il y a aussi les gestionnaires de paquets de distributions comme Slackware. Les autres, je ne les connais pas assez.
Après cette longue introduction, venons-en au fait : j'ai créé un solveur de dépendances assez intéressant :
- Il est complet à tous points : les reverse-dependencies sont gérées, les provides le seront également bientôt, et il trouve toutes les possibilités, et est capable de les présenter à l'utilisateur
- Il est extrêmement rapide : il ne fait jouer que les paquets nécessaires. Par exemple, le solveur SAT de OpenSuSE et APT nécessitent de lire toute la base de donnée des paquets, tandis que mon solveur ne charge que les paquets qui sont des dépendances, conflits, dépendances inverses, suggestions, remplaçants, etc
- Il est incroyablement simple : solver.cpp ne fait que 235 lignes !
Il utilise un concept assez intéressant, ou plutôt plusieurs :
- Une base de donnée "à la OpenSuSE", c'est à dire binaire, gérée par le solveur lui-même, et partant de principe qu'il faut éviter tous les for() (instructions de boucle qui rendent rapidement un programme très lent quand il a des millions d'entrées). Trouver les dépendances d'un paquet n'a que la complexité O(nombre de dépendances), et non O(nombre de paquets de la BDD) comme chez les autres. Trouver toutes les informations d'un paquet est en temps constant, trouver les versions d'un nom de paquet est O(nombre de versions), etc. C'est difficile à gérer (et à construire, je prend pour preuve databasewriter.cpp qui pèse 727 lignes), mais c'est foudroyant à l'utilisation
- Setup, le gestionnaire de paquets autour, a une particularité assez intéressante : il est très user-friendly (bien que seulement en console pour le moment) : sortie colorée, absolument toutes les chaînes sont traduites (y compris le titre, la description courte et la description longue d'un paquet)
- Logrammien. Ce système a été développé en premier lieu pour Logram, mon projet de distribution utilisant comme environnement de bureau KDE et son propre mini-environnement de bureau. Logram sera le plus user-friendly possible, et toutes les touches sont apportées (dont un système de paquet internationalisé et rapide, une intégration des outils à KDE, etc)
- Le solveur lui-même (pour revenir au sujet) utilise un système de branches, que je détaille maintenant
L'idée m'est venue en utilisant des systèmes de contrôles de versions (VCS). On peut aisément créer une branche, travailler dedans, et la supprimer si ça ne va pas. J'ai simplement appliqué ce principe aux gestionnaires de paquets, et ça a l'air de bien marcher.
Le principe est simple : au début de la résolution, on crée une branche (la branche principale). Dans cette branche, on place le paquet qu'on veut installer.
Ensuite, on explore ses dépendances. S'il n'y a pas de "choix", donc qu'on dépend par exemple de libqt4-gui et qu'il n'existe qu'une seule version de cette bibliothèque dans les dépôts, on la prend. S'il y a plusieurs choix possibles (ici plusieurs versions), on crée une branche par choix.
Ainsi, les branches divergent, et si quelque-chose n'est pas possible (conflit insoluble), on élimine la branche. A la fin de la résolution, devenue "bête et méchante" (c'est à dire qu'on installe les dépendances, supprime les conflits, etc sans se soucier du reste), on obtiens la liste des branches possibles.
Reste alors à les "peser", c'est à dire à obtenir un score pour chacune d'elle, en fonction de critères divers (nombre de paquets à installer/supprimer, mises à jour, taille à télécharger, etc). La branche la plus lourde est présentée à l'utilisateur, c'est potentiellement la meilleure. Les autres sont gardées, pour permettre à l'utilisateur de cliquer sur un bouton «Autre possibilité» si la solution présentée lui désinstalle son paquet de-la-mort-qui-tue qu'il veut garder.
Le résultat est élégant, et Qt aide (oui, c'est développé avec Qt). Le code est court, et marche. Il n'est pas encore assez propre, pas encore fini, mais est disponible sur le SVN de Logram à l'adresse svn://logram-project.org/logram/trunk/Distro/libs/libpackage (architecture bibliothèque/client powa :) ). Le client console est là : svn://logram-project.org/logram/trunk/Distro/base/setup .
Pour le moment, cette bibliothèque et son client ne savent pas installer de paquets. C'est une affaire de semaines, la partie "difficile" étant faite (encore quelques détails à régler avec les provides et la liste des paquets installés, et c'est bon). Toute la partie création de paquets, mise sur le serveur et gestion des miroirs est faite.
Exemple concret
Mes explications sur l'architecture par branches ne me semblent pas assez claire. Je vais vous montrer un exemple, avec le dépôt contenant les paquet suivants :
- initng-plugins, qui dépend de initng >= 0.6.0
- initng en version 0.6.0
- initng en version 0.6.99-gitAug3009, dépendant de libinitng == 0.6.99-gitAug3009
- libinitng en version 0.6.99-gitAug3009
Je veux donc installer initng-plugins, donc je lance :
setup add initng-plugins(note: pourquoi add ? Parce que install ne va pas, car si on préfixe le nom d'un paquet par "-", on le désinstalle, ce qui est plus pratique :
setup add initng-plugins -libinitng-dev)Voici simplement les étapes qui sont exécutées par le solveur :
- Créer la branche master, et y placer initng-plugins
- initng-plugins dépend de deux version (0.6.0 ou 0.6.99-gitAug3009) de initng
- Création d'une branche, dans laquelle on place initng-0.6.0
- initng-0.6.0 ne dépend plus de rien, on retourne true :)
- Dans la branche principale (oui, on recycle), on ajoute initng-0.6.99-gitAug3009
- initng-0.6.99-gitAug3009 dépend de libinitng-0.6.99-gitAug3009. On l'ajoute dans cette branche
- Il n'y a plus de dépendances, on peut retourner true :)
C'est un exemple simplissime, mais qui montre comment les branches permettent de facilement se tirer du problème dans devoir sortir une artillerie telle que SAT. Au final, on a deux branches, contenant respectivement :
- initng-plugins, initng-0.6.99-gitAug3009 et libinitng-0.6.99-gitAug3009
- initng-plugins, initng-0.6.0
On les pèse, et en fonction de ce que l'utilisateur veut (du bleeding endge ou du stable), on installera la première ou la deuxième.
Voilà, le journal du vendredi qui ne trolle pas trop. J'espère que je ne fais pas fausse route, mais chez moi, avec un dépôt un peu plus complexe, ça marche :
$ ./setup add initng-plugins
{
"initng-plugins" "0.6.99+gitAug302009~1"
"initng" "0.6.99+gitAug302009~1"
"libinitng" "0.6.99+gitAug302009~1"
}
{
"initng-plugins" "0.6.99+gitAug302009~1"
"initng" "0.6.98"
"libinitng" "0.6.99+gitAug302009~1"
}
{
"initng-plugins" "0.6.98"
"initng" "0.6.99+gitAug302009~1"
"libinitng" "0.6.99+gitAug302009~1"
}PS: Oui, dans mon résultat, les *-0.6.98 dépendent des version Git, c'est normal, j'avais la flemme de changer la version des dépendances :-° (surtout que comme c'est maintenant, ça induit un petit stress en plus du côté des reverse-dependencies, donc on va pouvoir s'amuser :) )
# Bravo
Posté par Pierre Bourdon . Évalué à 10.
[^] # Re: Bravo
Posté par Pierre Carrier . Évalué à 9.
steckdenis, gères-tu les dépendances circulaires (en:Circular_dependency) ?
Il y en a un paquet dans Debian : http://debian.semistable.com/debgraph.out.html
En leur absence, les paquets et leurs dépendances forment un graphe acyclique orienté [http://en.wikipedia.org/wiki/Directed_acyclic_graph].
Amusez-vous bien avec ces quelques liens...
[^] # Re: Bravo
Posté par steckdenis (site web personnel) . Évalué à 2.
Je n'ai pas testé, mais ça ne devrait pas casser. Pour le moment, ça ferait une boucle infinie (code minimal sans rien), mais dans quelques minutes, j'aurai intégré un truc qui fait qu'on ne demande pas l'installation d'un paquet déjà en attente d'installation :
* On demande libgcc1
* On a besoin de libc6
* Libc6 a besoin de libcc1, mais il est déjà dedans, on retourne.
Ca devrait aller :) . Merci beaucoup pour les liens (Debian a vraiment un univers encore plus grand que ce que je pensais autour de lui !)
[^] # Re: Bravo
Posté par Zakath (site web personnel) . Évalué à 7.
Et tu n'expliques pas comment tu gères les dépendances inverses, non plus.
[^] # Re: Bravo
Posté par steckdenis (site web personnel) . Évalué à 2.
Le packageur crée un fichier de la sorte :
[paquet]Name=nom
Version=version
Distribution=section de la distrib
Depends=dépendances (>= version); ...
Ces fichiers sont envoyés sur le serveur, qui en fonction de Distribution crée les dists/distro/packages.lzma. Ce fichier compressé est la simple concaténation des fichiers écrits par les packageurs.
Du côté de Setup, ces fichiers sont récupérés, et inscrits dans la base de donnée (par un code monstrueux de 700 lignes d'ailleurs).
C'est là que tout est joué : dans la base de donnée, chaque paquet a une simple liste de dépendances, et chaque dépendant est une structure :
struct _Depend{
int8_t type; // DEPEND_TYPE
int8_t op; // DEPEND_OP
int32_t pkgname; // Index de la chaîne du nom du paquet de la dépendance
int32_t pkgver; // Index de la chaîne de la version du paquet de la dépendance
};
Type permet de spécifier le type, c'est à dire une dépendance, une suggestion, un conflit, une fourniture, et une dépendance inverse. Les dépendances inverses ne sont pas données par le packageur, mais c'est databasewriter.cpp, qui connaissant tous les paquets de la BDD, s'occupe de faire les liens inverse (pour chaque dépendance, une dépendance inverse est crée de l'autre côté).
Ainsi, du côté du solveur, le code de gestion des dépendances inverses se limite à ... ceci :
else if (dep->type == DEPEND_TYPE_REVDEP && action == Solver::Remove){
act = Solver::Remove;
// TODO: Vérifier que la dépendance inverse est installée avant de surcharger l'arbre
}
Donc, si on retire un paquet, on retire également ses dépendances inverses (et le TODO est là pour me rappeler que quand j'aurai codé l'installation, je devrai voir si le paquet n'est pas déjà non-installé, pour ne pas le supprimer deux fois, et donc créer trop de branches).
C'est simple, ça marche :
$ ./setup add -libinitng{
"libinitng" "0.6.99+gitAug302009~1"
"initng" "0.6.99+gitAug302009~1"
"initng-plugins" "0.6.99+gitAug302009~1"
"initng-plugins" "0.6.98"
"initng" "0.6.98"
}
{
"libinitng" "0.6.98"
}
Ici, on voit qu'on a deux solutions :
* Retirer libinitng-0.6.98 dont rien ne dépend
* Retirer tous les autres paquets (puisque je n'ai pas encore la gestion des paquets supprimés/installés, tout est supprimés). On voit qu'on a correctement remonté tout l'arbre : initng dépend de libinitng, et les initng-plugins dépendent de initng.
C'est ok :) .
[^] # Re: Bravo
Posté par Zakath (site web personnel) . Évalué à 6.
Je ne suis pas sûr que ton algorithme soit consistent (je doute fortement que ce soit le cas, mais j'ai la flemme de chercher un contre-exemple), mais il n'est en tout cas pas complet :
A dépend de B et C
J'installe A, il installe B et C automatiquement
Je veux désinstaller C. Ton algorithme voit que ca va casser A, donc il le désinstalle aussi. Mais il ne va pas aller voir si B est toujours nécessaire sur ta machine, ce qu'il devrait faire en regardant si il n'existe pas un D qui dépende de B et qui soit installé.
Par ailleurs, tu n'expliques pas non plus comment tu gères les conflits (l'opposé d'une dépendance, donc). Mes deux centimes, c'est que tu devrais passer moins de temps à coder les détails, optimiser la base de données et faire des sorties colorées, et vraiment réfléchir aux algorithmes que tu utilises et à tous les cas vicieux que tu peux rencontrer.
[^] # Re: Bravo
Posté par Pierre Carrier . Évalué à 2.
Le problème de dépendances inverses étant coûteux, certaines sous-solutions pourraient-elles être précalculées côté serveur et/ou mises en cache côté client ?
On devrait pouvoir splitter le graphe des paquets en sous-graphes "intéressants" en ramenant toutes les versions d'un paquet à un nœud avec pour poids une fonction logarithmique sur le nombre de versions (O(n) sur le nombre de paquets), en le désorientant (O(n) sur le nombre de dépendances), en réduisant les chaînes isolées (conserver la longueur originale dans le poids des liens, O(n log n) sur le nombre de dépendances déversionnées il me semble), en calculant l'arbre couvrant minimal (en:Minimum_spanning_tree, à peu près linéaire d'après Wikipedia), puis en tronçonnant l'arbre comme un bourrin.
Il y a plusieurs techniques à essayer pour tronçonner, mais j'ai le sentiment qu'on aurait facilement de jolis sous-graphes dans lesquels précalculer.
De toute façon je suis définitivement moins bon que les gens qui bossent là-dessus et n'y pense que vaguement dans le bus, mais j'avais envie de le raconter ;)
Pour revenir à ton outil steckdenis, fais gaffe à ce que tu veux calculer à chaque opération : nombre d'entre elles sont des mises à jour.
Or à chaque mise à jour on "désinstalle" la version actuelle et "installe" la nouvelle. Et "souvent" il "suffit" de vérifier que ça n'impacte personne.
Bref l'opération la plus courante est peu coûteuse dans le cas général, essaye de conserver cette propriété !
Il y a un super algo en O(n) basé sur une fable de La Fontaine ([http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algor(...)]) pour résoudre parfaitement le problème des dépendances inverses. J'ai un prototype de preuve en 50 caractères de Brainfuck en tête mais pas la place dans la marge pour le reproduire !
[^] # Re: Bravo
Posté par IsNotGood . Évalué à 3.
C'est un peu n'importe quoi.
Les conflits sont le complément les dépendances.
> en utilisant des scripts de configuration des alternatives.
Ce qui revient à gérer les conflits...
[^] # Re: Bravo
Posté par Pierre Carrier . Évalué à 1.
Gestion des alternatives : tu veux installer vim et as déjà nvi, on te demande vers lequel tu veux que /usr/bin/vi pointe.
Et tu pourrais peut-être argumenter au lieu d'affirmer que "c'est un peu n'importe quoi".
[^] # Re: Bravo
Posté par steckdenis (site web personnel) . Évalué à 3.
Pour les conflit, c'est assez simple (quoique j'avoue que ça peut être un peu idiot) : si je veux installer le paquet A, et qu'il est en conflit avec B, je supprime B. Je dois encore voir s'il est mieux de faire ça méchamment (on supprime B), ou intelligemment (on supprime B uniquement s'il est installés).
[^] # Re: Bravo
Posté par BAud (site web personnel) . Évalué à 3.
dont dépend C (par exemple), tu supprimes C aussi ?
Tu peux regarder quelques use-cases sur
http://wiki.mandriva.com/en/RPM_Dependency_Optimization
http://wiki.mandriva.com/en/Core_Dependency_Sanitization
un exemple de cas tordu http://wiki.mandriva.com/en/Unzip_Dependency (obligeant à revoir les dépendances)
pour voir si tu es déjà robuste par rapport à ces cas et, comme indiqué ci-dessus, le projet Mancoosi http://wiki.mandriva.com/en/Mancoosi_Project doit avoir d'autres cas types qu'il vaut mieux prendre en compte. N'hésite pas à te constituer des jeux de dépendances "réels" issus des listes de debian ou d'autres distributions (parser les fichiers de liste automatiquement ne devrait pas être trop dur) pour avérer que tes hypothèses de complexité sont avérés.
[^] # Re: Bravo
Posté par steckdenis (site web personnel) . Évalué à 2.
* Une pour supprimer C (et ce qui en dépend)
* Une pour chaque paquet du même nom que B, mais avec une version différente, et qui peut être pris comme dépendance de C
Ainsi, si C dépend de B>=0.1, et qu'on supprime B=0.5, on pourrait ne pas supprimer C, mais installer B=0.6, qui ira peut-être dans le problème :) .
[^] # Re: Bravo
Posté par BAud (site web personnel) . Évalué à 2.
ma suggestion sur C était de pousser le raisonnement par récurrence hein : tu as D qui peut dépendre de C et, de proche en proche, tu peux en arriver à désinstaller tout plein de choses, ce qui est mis en évidence dans les liens que je t'ai fournis, que tu peux prendre un peu de temps à parcourir.
Identifier les cas que tu traites et ceux que tu ne traites pas encore permet tout de même d'assurer un début de complétude, d'où la suggestion de regarder des listes existantes de dépendances et d'éprouver tes modèles sur des cas plus réels.
[^] # Re: Bravo
Posté par steckdenis (site web personnel) . Évalué à 2.
Pour le moment, mon solveur doit être assez proche de la complétude, car il ne quitte ses boucles récursives que très difficilement (pour le moment, seulement si un paquet dépend d'un autre qui n'existe pas, ou si on veut supprimer A après avoir dit qu'il faut installer A).
Par contre, ça risque d'être très lent, donc je cherche pour le moment des conditions d'arrêt supplémentaires gardant au maximum cette complétude, pour vraiment éviter d'avoir un problème solvable qui échoue.
Je suis actuellement en train de tester les cas ou A dépend de B, et C fourni également B (exemple de chez Archlinux : fluxbox-svn fournit fluxbox, qui est aussi un paquet). Ca me crée bien deux branches, avec les paquets qu'on va installer, mais je dois voir si c'est bien robuste avec les conflits, les dépendances inverses, etc.
[^] # Re: Bravo
Posté par Spyhawk . Évalué à 2.
[^] # Re: Bravo
Posté par Thomas Debesse (site web personnel) . Évalué à 3.
Un paquet dans Debian ? un seul ?
→ ◧
ce commentaire est sous licence cc by 4 et précédentes
# Dépendances inverse
Posté par Skunnyk (site web personnel) . Évalué à 6.
Je ne sais pas si ta solution est la solution 'idéale' (je ne connais pas assez le comportement les autres gestionnaires de paquets), mais pour archlinux, pacman gère bien la dépendance inverse, si j'ai bien compris ce dont tu parles, il suffit d'utiliser les bonnes options : pacman -Rcs ; par exemple:
# sudo pacman -Rcs tcl
Vérification des dépendances...
Suppression (10): fretsonfire-1.3.110-1 python-opengl-3.0.1a1-1 freenx-0.7.3-4 weechat-0.3.0-2 tk-8.5.7-1 extremetuxracer-0.4-1.1 expect-5.44.1.10-1
tcl-8.5.7-1 gnu-netcat-0.7.1-3 nxserver-3.3.0-6
Taille totale des paquets (suppression): 94,06 Mo
Voulez-vous désinstaller ces paquets ? [O/n] n
Mis à part ça, bon courage à toi dans ce projet !
[^] # Re: Dépendances inverse
Posté par steckdenis (site web personnel) . Évalué à 2.
Pour les dépendances inverses, je fais au plus simples. Ce sont en fait des dépendances normales, gérées comme telles. La différence est qu'elles sont calculées par une grosse fonction revdep() dans databasewriter.cpp. Voici ici pour le code : http://wiki.logram-project.org/websvn/listing.php?repname=Lo(...) .
Merci pour les encouragements :) .
[^] # Re: Dépendances inverse
Posté par Thomas Douillard . Évalué à 6.
Par exemple, du comportement d'aptitude, on peut déduire qu'il utilise déja certaines de tes techniques lors de la résolution de dépendance : ouverture de branche sur les différents package installables (notion de noeud), attribution d'un score à chaque noeud, ...
Les algos SAT font aussi ce genre de chose : baktracking, test de cohérence des différents choix. Parler "d'artillerie lourde" en parlant d'algo de résolution SAT c'est aussi un peu exagéré à mon sens en comparaison d'algo de résolutions d'autre type de problèmes, les algos SAT ne sont pas si compliqués, ni même si lourds. Genre ton algo à toi est très très similaire dans l'idée à un DPLL de base. En moins bien parce que tu n'as rien prouvé de sa correction :)
Bref, l'idée de ce post c'est d'essayer de te montrer que tes idées ne sont pas idiotes, mais que je trouve un peu prétentieuse ta manière de les présenter.
[^] # Re: Dépendances inverse
Posté par Thomas Douillard . Évalué à 2.
http://en.wikipedia.org/wiki/Unit_propagation
[^] # Re: Dépendances inverse
Posté par monde_de_merde . Évalué à 1.
Tu aurais ça dans un coin ?
[^] # Re: Dépendances inverse
Posté par Spyhawk . Évalué à 3.
L'article de Daniel Burrows sur Apt est très instructif puisqu'il représente grosso modo ce que font la majorité des gestionnaires de paquets. L'article "EDOS" présente le problème vu sous un angle SAT.
# NP-complet
Posté par arenthis . Évalué à 10.
Il semble donc probable que ton algo soit incomplet. Si tu t'intéresses à ce genre de chose, le projet européen EDOS[2] et son successeur MANCOOSI[3] ont fait pas mal de boulot sur le sujet.
[1] http://www.edos-project.org/xwiki/bin/download/Main/Delivera(...)
[2] http://www.edos-project.org
[3] http://www.mancoosi.org
[^] # Re: NP-complet
Posté par Thomas Douillard . Évalué à 2.
Pas sur qu'il est rencontré ces cas lors de ses tests, cependant, il faudrait essayer de lui fournir le dépot "sudoku" pour voir :)
[^] # Re: NP-complet
Posté par Anonyme . Évalué à 3.
http://algebraicthunk.net/~dburrows/blog/entry/package-manag(...)
# Trouver le paquet?
Posté par Brioche4012 (site web personnel) . Évalué à 4.
Utilise-tu une base de données? Si oui ça veut dire que du fais une requête dans ta base à chaque dépendance que tu rencontres. Est-ce que ça ne prend pas trop de temps? Le maintien de la BDD de APT est ce qui semble prendre le plus de tems pour l'installeur de debian.
Une autre question est que ton système à l'air vraiment très bien, mais pourquoi le fais-tu dépendre de QT? S'il est vraiment efficace, nombre d'autres gestionnaires aimeront sans doute s'en servir. Limiter les dépendances serait alors un choix judicieux.
[^] # Format de la base de donnée
Posté par steckdenis (site web personnel) . Évalué à 3.
La base de donnée utilise deux concepts intéressants. D'une part, elle est binaire, et d'autre part, elle est lue grâce à des fichiers mappés.
L'immense avantage des fichiers mappés est que l'OS se charge de toutes les entrées sorties. Pour un solveur de type SAT, qui doit construire le problème, tous les paquets doivent être lus et mis dans le problème. On a donc beaucoup d'IO sur le disque.
Ici, mon système n'utilise que les dépendances d'un paquet (avec les conflits, les dépendances inverses, etc). Si le paquet A dépend de B et est en conflit avec C, je ne vois absolument pas pourquoi je dois mettre D, E et F dans le problème.
Pour illustrer par un cas réel, imaginez que vous souhaitiez installer OpenOffice.org. Vous avez vraiment besoin que votre solveur perde son temps à tester s'il doit installer Wormux ?
Donc, c'est un fichier mappé en mémoire, et ça accélère/simplifie grandement les choses. Il n'y à qu'à voir comment on récupère un paquet quand on connait son ID :
_Package *PackageSystemPrivate::package(int index)
{
// Trouver l'adresse du paquet
if (index >= *(int *)m_packages)
{
return 0;
}
// Début de la liste des paquets
uchar *pkg = m_packages;
pkg += 4;
// Paquet au bon index
pkg += (index * sizeof(_Package));
return (_Package *)pkg;
}
Seulement des pointeurs. Et ce qui est vraiment excellent, c'est que GCC sait très bien compiler et optimiser du code de ce genre. Ceci est compilé en ce code assembleur, uniquement :
movq 40(%rdi), %rdxxorl %eax, %eax
cmpl %esi, (%rdx)
jle .L3
movslq %esi,%rax
leaq (%rax,%rax,4), %rax
leaq 4(%rdx,%rax,4), %rax
.L3:
rep
ret
9 instructions, en O(1), pour récupérer un paquet dans la BDD. Qui dit mieux ?
Même chose quand on a une chaîne :
const char *PackageSystemPrivate::string(uchar *map, int index)
{
// Si map == 0, on prend m_strings (c'est qu'on a été appelé d'ailleurs)
if (map == 0)
{
map = m_strings;
}
// Vérifier l'index
if (index >= *(int *)map)
{
return 0;
}
// Trouver la chaîne à l'index spécifié
uchar *str = map;
int count = *(int *)map; // count
str += 4; // Sauter count
// Index
str += (index * sizeof(_String));
// En fonction du pointeur, trouver l'adresse de la chaîne
const char *ptr = (const char *)map;
ptr += ((_String *)(str))->ptr; // Ajouter l'adresse du pointeur
ptr += 4; // Sauter le count
ptr += (count * sizeof(_String)); // Sauter la table des chaînes
return ptr;
}
Egalement en temps constant, très rapide. Ca s'utilise comme ça :
QString PackageSystemPrivate::packageName(int index)
{
_Package *pkg = package(index);
if (pkg == 0) return QString();
return QString(string(m_strings, pkg->name));
}
Pour la dépendance de Qt, c'est simplement qu'il est totalement idiot de ne pas l'utiliser alors qu'il marche si bien. Libpackage et Setup ne dépendent que de QtCore, mais bien. Par exemple, mon code utilise beaucoup de QHash, QList, QVector, QFile, QString, etc. Qt est vraiment très confortable, et permet de raccourcir le code.
Je n'ai pas de temps à perdre à coder mon propre Hash, ou ma propre liste. C'est une source de bugs potentielle. Je préfère me concentrer sur l'algo, pas sur le codage en dessous. Pour ça, Qt est excellent : il propose tous les trucs dont on a besoin, mais qui prennent pas mal de temps à coder. Utiliser QString::split() ou QString::section est un bonheur quand on a des trucs comme splitter "machin>=chose" pour récupérer le nom et la version.
# Paludis?
Posté par YLD . Évalué à 3.
Il gère aussi les branches de façon astucieuse et pratique [http://ciaranm.wordpress.com/2009/04/16/distributed-distribu(...)] mais en les mélangeant au lieu de les pondérer (à l'utilisateur de cacher ou non tel ou tel composant).
Il propose encore plusieurs façons d'outrepasser les dépendances circulaires (...) bref, il vaut peut être le détour...
# SAT, une artillerie lourde ?
Posté par Spyhawk . Évalué à 7.
Il est complet à tous points... Il est extrêmement rapide : il ne fait jouer que les paquets nécessaires. ... Il est incroyablement simple
Ces phrases m'ont un peu surpris. Ton solveur fait peut être ~250 lignes, mais comme ça a déjà été remarqué plus haut, le problème de gestion des dépendances est NP-complet et ton solveur.. loin d'être "complet".
D'autre part, le solveur implémenté dans ZYpp est basé sur le solveur open-source MiniSAT (http://minisat.se/ ) qui fait dans les 600 lignes. Pas mal pour un solveur complet qui s'affranchit de l'exponentialité des solutions possible avec le nombre de paquets disponibles.
Enfin, tu sous entends que le solveur d'openSUSE nécessite de chargé la base de données en mémoire avant de pouvoir effectuer les calculs de dépendances et que ceci ralenti considérablement sa vitesse.
Ce n'est pas exactement vrai, puisque en pratique on voit que l'utilisation d'une BDD binaire (que tu sembles aussi utiliser) est foudroyant à l'exécution. Il ne faut que quelques millisecondes pour lire la base de données entière et ce n'est en tout cas pas un "bottleneck".
Using a data dictionary approach to store and retrieve package and dependency information. A new solv format was created, which stores a repository as a string dictionary, a relation dictionary and then all package dependencies. Reading and merging multiple solv repositories takes just some milliseconds.
Là où les choses peuvent être améliorées est la vitesse de création des équivalents binaires des méta-données des dépôts, par exemple, en les générant à la volée directement sur le serveur, et pas après téléchargement des md-data par le client.
A noter aussi que Apt, Yum et URPMI sont incomplets et utilisent plutôt des méthodes heuristiques. A ma connaissance, le seul PM non expérimental qui utilise un algo "avancé" de type SAT et est possiblement complet est Smart.
Sinon, j'aime bien tes journaux/concepts, y'a de bonne idées mais je pense qu'un peu plus de modestie serait un plus concernant ta crédibilité.
http://en.wikipedia.org/wiki/ZYpp
[^] # Re: SAT, une artillerie lourde ?
Posté par Spyhawk . Évalué à 2.
[^] # Re: SAT, une artillerie lourde ?
Posté par steckdenis (site web personnel) . Évalué à 1.
Merci :) . Pour la modestie, c'est toujours un effet de bord. Quand je viens de terminer quelque-chose, et que j'ai passé plusieurs jours pour y arriver, je suis toujours très (trop ?) content.
Pour le solveur SAT, rien que le fait qu'on doive lire tous les paquets est lourds. Il y a peut-être moyen de l'éviter, mais le but est de construire un problème à base de clauses, une ou plusieurs clauses par paquets. Oui, ce sont des clauses simples (comme dit dans la page Zypp, ça doit faire quelques mois que je lis presque tous les jours ce wiki et la doc Doxygen de libzypp), mais il y en a beaucoup.
On peut avoir une BDD aussi optimisée qu'on veut, si on doit lire 40Mio sur le disque dur pour résoudre un problème, le disque dur ne va pas aimer. Chez moi, comme seuls les paquets entrant directement dans le problème sont lus, la BDD peut faire plusieurs Gio qu'il n'y aura pas de problèmes.
J'ai conçu mon gestionnaire de paquets avec dans la tête l'informatique qu'on aura dans 10 ou 20 ans : plus de logiciels propriétaires (ou très peu), énormément de logiciels libres, et un bon million de paquets dans les distros. Le moindre algo en O(nombre de paquets) est immédiatement écarté, car même s'il est rapide, faire 40 millions de tours de boucle, c'est trop.
Mes algos sont généralement en O(1) (pour les simples) ou en O(nombre d'éléments en jeu). Par exemple, pour trouver tous les paquets qui ont un nom (donc par exemple pour voir quels paquets correspondent à "libfoo>=0.4.88"), je prend la structure _String de libfoo, et cette structure a un pointeur vers des _StrPackage. Je les explore, et j'obtiens la liste de tous les paquets et leurs versions qui ont ce nom.
Au passage, c'est effroyablement simple pour un autre problème de dépendances : les Provides. Quand un paquet en fournit d'autres (par exemple "machin" qui fourni "truc = 0.5"), il me suffit de rajouter dans les StrPackages de "truc" une entrée "0.5"->id_du_paquet_truc.
Le solveur de dépendance n'aura même pas à s'en occuper, c'est directement pré-résolu dans la BDD.
Pourquoi je cherche tant de rapidité ? Après tout, on n'installe pas un paquet tous les jours. Simplement, quand on installe un paquet, je compte faire un truc à la Synaptic, c'est à dire rajouter en temps réel les dépendances que notre action précédente entraîne. Il fait donc qu'il n'y ait pas de lag, et donc que la résolution soit foudroyante (attendre 0,1s, c'est déjà trop).
[^] # Re: SAT, une artillerie lourde ?
Posté par Spyhawk . Évalué à 5.
A te lire, j'ai vraiment l'impression qu'on parle de 2 choses totalement différentes et que tu n'a pas saisi comment le solver d'openSUSE fonctionne. Tu devrais aussi lire la doc de Daniel Burrows et celle du projet EDOS, ainsi que jeter un oeil au fonctionnement du SatSolver ZYpp en utilisation réelle.
Pour mémoire, voici le fonctionnement basic de ZYpp :
1/ teléchargement des métadonnées depuis les dépôts
2/ transformation des métadonnées en fichiers binaires .solv, qui contiennent les règles de dépendances de chacun des paquets
3/ calcul des dépendances
4/ application du résultat
L'étape 1/ est "bottleneck", elle ne dépend pas du solveur, mais du format des md-data et de la qualité de la connexion aux dépôts.
L'étape 2/ utilise une "dictionary approach" pour stocker les dépendances sous la forme d'un nombre 32bits unique, permettant une comparaison très rapide de 2 chaines de "charactères", principe de base du solveur SAT, un espace disque moindre, puisqu'un nombre est plus petit qu'une chaine de charactère (j'ai 4.7 Mo, 4.5 Mo, 3.6 Mo, 406 Ko pour les 4 plus gros dépôts activés qui représentent à eux seul un peu plus de 16'000 paquets, 1.4 Mo pour ma base RPM locale .solv, et mes 14 autres ne font que quelques Ko) et la representation mémoire ne prend pas plus de place sur un système 64bits où un pointer est 2x la taille d'un nombre 32bits (cf. doc SatSolver).
Un refresh forcé de ces fichiers me prends ~9 secondes, mais est surévalué puisque le dépôt principal, qui ne change jamais, est recré (5 sec est plus realiste pour une utilisation standard.. et encore).
L'étape 3/ me calcul les dépendances (par exemple un dist-upgrade me propose une solution en ~2.5 secondes), enfin l'étape 4/ valide les changements et télécharge les paquets proposés.
Au final, le calcul des dépendances est extrêmement rapide malgré le fait qu'un grand nombre de paquets sont pris en compte en mémoire (~2.5 secondes pour +16'000 paquets). J'ai l'impression que le problème que tu essaies de résoudre n'existe tout simplement pas avec un solver sat couplé avec une approche metadonnés-binaire telle qu'implémentée par ZYpp. De plus, la résolution est complète.
[^] # Re: SAT, une artillerie lourde ?
Posté par steckdenis (site web personnel) . Évalué à 1.
Justement. Est-il normal, pour par exemple mettre à jour Wormux, d'avoir à gérer 16000 paquets. Là, ça prend 2,5 secondes, ce qui est correct. Maintenant, si t'as 160 000 paquets, ça va prendre 25 secondes, et là ça fait mal, très mal (et 160 000 paquets, c'est une affaire d'années).
Il me semble qu'un problème SAT est une suite de clauses, comme ceci (format utilisé par MiniSAT en entrée) :
-1 2 33 4 -5
...
Construire une telle liste nécessite de lire tous les paquets de la base de donnée, c'est à dire un minimum un for() sur les paquets.
Pour chaque paquet, il faut lister ses dépendances (ce qui est rapide en binaire), etc. Au final, la construction du problème prend presque autant de temps que sa résolution.
Maintenant, je me trompe peut-être.
[^] # Re: SAT, une artillerie lourde ?
Posté par Spyhawk . Évalué à 5.
En l'occurence, avec un solveur sat, le "bottleneck" n'est pas la résolution des dépendances ni la lecture des métadonnées mais le téléchargement et l'installation des paquets.
D'autre part, ces 2.0 - 2.5 secondes ne sont pas linéairement dédiées à la résolution :
zypper dup
Loading repository data... -> 1 sec
Reading installed packages... -> 1 sec
Computing distribution upgrade... -> 0.5 sec
Pour finir, je ne vois strictement pas l'intérêt de créer une solution pour un scénario viable dans 10 ou 20 ans alors que tu ne connais strictement rien aux conditions du futur environment (capacité de bande passante, performance disque dur et CPU, calcul quantique ?).
Quitte à créer un solution, autant qu'elle réponde à un besoin d'aujourd'hui, ou elle aura toute les chance d'être obsolète avant même d'être utile.
[^] # Re: SAT, une artillerie lourde ?
Posté par steckdenis (site web personnel) . Évalué à 2.
Reading installed packages... -> 1 sec
Computing distribution upgrade... -> 0.5 sec
Justement. On n'a pas l'air de vraiment se comprendre, et la faute est peut-être de mon côté, mais tu viens de me montrer ce que je dénonce.
Sur les 2,5 secondes, seulement 0.5 secondes sont effectivement utilisées pour du calcul. Le reste est, comme le dit «Loading repository data», la lecture de tous les paquets et la construction du problème (avec «Reading installed packages» qui applique des contraintes supplémentaires, ou qui complète le problème).
On a donc 0,5 secondes réellement utiles, et 2 secondes de perdues parce que le SAT nécessite de lire la base de donnée de tous les paquets de la distribution (et c'est de ça que je parle, ça n'a rien à voir avec le SAT justement, le SAT est rapide et léger, mais il nécessite, avant lui, un traitement lourd de construction du problème).
Avec Setup, les deux secondes ne sont pas perdues, et comme le problème est nettement plus court, ce ne sera pas 0,5 secondes, mais peut-être moins (quoique, le solveur SAT simplifie très fortement le problème en première passe pour éliminer les «-wormux | wormux-data» totalement inutiles si t'installes OOo).
[^] # Re: SAT, une artillerie lourde ?
Posté par Brioche4012 (site web personnel) . Évalué à 2.
Je connais beaucoup de gens qui sont passés de debian à arch pour la seule raison que pacman est plus rapide que apt, même si les paquets debian sont de meilleure facture (enfin, c'est mon avis, pas taper!)
Et puis, 2.5s pour résoudre des dépendances est toujours trop long.
Pour illustrer mon propos, j'ai mesuré les temps mis par apt et pacman pour installer vim sur le même ordinateur, apt prends environ 10s et pacman 2s, et je les trouve toujours trop lents.
[^] # Re: SAT, une artillerie lourde ?
Posté par Watchwolf . Évalué à 3.
[^] # Re: SAT, une artillerie lourde ?
Posté par Spyhawk . Évalué à 2.
Pour illustrer mon propos, j'ai mesuré les temps mis par apt et pacman pour installer vim sur le même ordinateur, apt prends environ 10s et pacman 2s, et je les trouve toujours trop lents.
~2.5s pour me calculer un dist-upgrade (sur un laptop vieux de 3 ans avec un DD 5400tpm), pas l'install d'un paquet unique.
# Cas complexes
Posté par Pascal Terjan (site web personnel) . Évalué à 5.
Je me rappelle que l'approche de smart avait l'avantagee de gérer des cas mal gérés par les autres outils. Cette phrase me laisse penser que ce n'est pas le cas de ton outil.
Si je me souviens bien un des cas est :
A et B sont installés
A necessite plop
B fournit plop
On demande d'installer C
C necessite D
D est en conflit avec B
Il existe E qui fournit plop mais n'est pas en conflit avec D et il faut proposer de remplacer B par E pour pouvoir installer C
[^] # Re: Cas complexes
Posté par ecyrbe . Évalué à 0.
Sinon, si E n'est pas une autre version de B, je ne vois pas pourquoi on devrait parcourir la base pour trouver une solution à l'action de l'utilisateur... dans ce cas on ne devrait que lui présenter l'information du conflit et pas d'autre solution que de désinstaller B.
[^] # Re: Cas complexes
Posté par steckdenis (site web personnel) . Évalué à 2.
Pour le moment, si B fournit Plop, ça crée un "paquet virtuel" Plop. En fait, comme paquet virtuel, c'est une simple entrée dans la table des chaînes de caractères (mais bon, c'est un détail technique).
Bref, C install D, et D supprime B. Actuellement, ça supprimera A (car avec les provides, des dépendances inverses sont crées, etc). Seulement, comme c'est un simple système de dépendances inverses, ce n'est pas répété dans le code, et je peux faire un truc plus complexe.
Prenons A qui dépend de B, C ou D. Je veux supprimer D. Nous crées donc 3 branches : une où on supprime D et A, une où on supprime D et installe C, une où on supprime D et installe B. C'est simple à faire, le format de la BDD le permet (j'aime ce format, il permet plein de choses).
Reprenons donc notre exemple : D supprime B. B va donc créer deux branches : une où il supprime A ... et une où il installe E ! Voilà, c'est fait, le problème est résolu, et en quelques lignes seulement (enfin de crois, j'ai pas encore codé).
# les branches, c'est déjà dans SAT
Posté par geh . Évalué à 2.
Je veux dire, tu as ton problème représenté sous forme de formule de logique booléenne et tu cherches les modèles (= assignements de valeurs de vérités aux variables booléennes) qui la satisfont. Soit tu te bricoles ton algo qui le fait (tu te modifies un DPLL), soit il existe déjà des algos (implémentés) qui t'énumèrent tous les modèles possibles d'une formule booléenne (cherche AllSAT algorithm sur le net). Après, tu prends tous tes modèles trouvés, tu leur mets un score comme tu l'as décrit pour tes branches, et tu présente à l'utilisateur les modèles du meilleur au plus mauvais. Si tu regardes l'ultraclassique algorithme DPLL, sa règle "split" est une règle de branchement.
(Je n'ai pas lu ton code).
# Question
Posté par alice . Évalué à 1.
# apt-git
Posté par davux (site web personnel) . Évalué à 1.
http://da.weeno.net/blog/ (article "apt-git", désolé, pas de lien permanent pour cause de rewrites temporairement pétés)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.