> 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é.
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 steckdenis . En réponse au journal Résolution des dépendances par système de branches. É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).