[pacman-dev] _alpm_sortbydeps is slow and buggy
Hi! I don't really understand how this function does 'topological sorting', but it is buggy. If n is the number of targets, maxscans=sqrt(n) is not enough: See the following example: Let the targets foo[1], ... foo[n]; where foo[i] depends on foo[j] iff i<j. It's easy to see that the function would sort correctly these target in 'n-1' steps; but it is stopped after sqrt(n) steps. (libm seems to be needed for libalpm because of these _one_ sqrt() only, so libm "depend" should be removed too). In the example above O(n^3) operations needed (+ I think first compute the dependency graph would much more effective; because for example we compute (n-1) times that foo[n-1] depends on foo[n], which is needless.). Well known O(n+e)~O(n^2) algorithms exists for topological sorting (see google). And I'm not sure that even maxscans=n enough (I cannot prove that this algorithm is correct yet, this is probably my fault;), and I cannot find an extreme example where this algorithm sucks. Bye, Nagy Gabor
Hi! As I see, the algorithm is correct (but slow) anyway, and (n-1) steps are enough. I won't go into details, but one can think to this algorithm as if we ensure the order of foo[i] and its dependencies in the ith step, where foo[i] is the ith in the topological sorted list. So the graph contains a circle <=> n-1 steps are not enough. As a hotfix, plz change sqrt(n) to n-1 (or n) and remove libm; and you can replace "possible dependency cycle detected" to "dependency cycle detected". Bye, ngaba PS.: This function is not so important, because depcheck is done before this (I think we should merge the 2 functions to efficiency).
Na Sat, Apr 14, 2007 at 11:42:44AM +0200, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> pisal(a):
As a hotfix, plz change sqrt(n) to n-1 (or n) and remove libm; and
please do a benchmark with this change for 5000 pkgs. it'll be *very* slow. currently it is done in a minute even on a slower machine. it may be buggy, but the fix should not be about slowing down the function so much thanks, VMiklos -- developer of Frugalware Linux - http://frugalware.org
... it may be buggy, but the fix should not be about slowing down the function so much I don't agree on this. This will be slower iff the old one produces a wrong result. If the result is not important why don't you delete this function from source?
currently it is done in a minute even on a slower machine. Jesus, do you mean that this is fast? :-S This is an other reason for implementing this function correctly or remove it completely.
Bye, ngaba
Na Mon, Apr 16, 2007 at 02:14:22PM +0200, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> pisal(a):
Jesus, do you mean that this is fast? :-S This is an other reason for implementing this function correctly or remove it completely.
how Aaron uses to say? "patches are welcome" :) thanks, VMiklos -- developer of Frugalware Linux - http://frugalware.org
> how Aaron uses to say? "patches are welcome" :) OK. I may do it, but 1. I think it's more difficult to understand an other person's thought than "doing it yourself". And I hope that developers check my patches before committing because I don't trust on myself ;-) 2. First I collect opinions because I don't want to do needless work (again :-). I think that almost whole deps.c should be rewritten (and most of the function should be merged: _alpm_checkdeps, _alpm_resolvedeps and _alpm_sortbydeps for example) Bye, ngaba
On 4/16/07, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> wrote: > > how Aaron uses to say? "patches are welcome" :) > OK. I may do it, but > 1. I think it's more difficult to understand an other > person's thought than "doing it yourself". And I hope that developers > check my patches before committing because I don't trust on myself ;-) > 2. First I collect opinions because I don't want to do needless work > (again :-). I think that almost whole deps.c should be rewritten (and > most of the function should be merged: _alpm_checkdeps, > _alpm_resolvedeps and _alpm_sortbydeps for example) Yes, sort-by-deps is slow. The easiest fix is to convert it from a set of nested loops to a topological sort algorithm. This is mentioned in a few places. As it stands, it works well enough (that's the reason for the sqrt - VMiklos pointed this out a while back when I actually wanted to remove it for n/2 - it's "good enough"). Tolopogical sort is a simple algorithm, but the problem is that it's hard to convert a list with chained lists as the dependencies into a graph structure. Feel free to try any option, but, for correctness's sake, I'd rather convert the dep list itself to a list of packages (all from the package cache, loaded on demand), which makes the topo sort much easier.
I'd rather convert the dep list itself to a list of packages (all from the package cache, loaded on demand), which makes the topo sort much easier. Yes, I also thought something similar ;-) We may also add a (void *)tmp entry to pmpkg_t struct (or to pmdepend_t ?) to make our life easier. Anyway, thinking packages with dependencies as a graph in the whole libalpm is much nicer and more efficient, but it's difficult to implement because the vertexes and edges change often and we cannot compute the whole graph (of all packages) just parts which are needed. Back to deps.c: I think that the slow sortbydeps should be merged into checkdeps (which should be merged into resolvedeps:-) instead of running it separately. Because as I think while we do a topological sort we can recognize that a dependency is missing (checkdeps) and optionally we can resolve it (resolvedeps). I don't like the slow way that resolvedeps uses now.
Bye, ngaba
On 4/17/07, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> wrote:
I'd rather convert the dep list itself to a list of packages (all from the package cache, loaded on demand), which makes the topo sort much easier. Yes, I also thought something similar ;-) We may also add a (void *)tmp entry to pmpkg_t struct (or to pmdepend_t ?) to make our life easier. Anyway, thinking packages with dependencies as a graph in the whole libalpm is much nicer and more efficient, but it's difficult to implement because the vertexes and edges change often and we cannot compute the whole graph (of all packages) just parts which are needed. Back to deps.c: I think that the slow sortbydeps should be merged into checkdeps (which should be merged into resolvedeps:-) instead of running it separately. Because as I think while we do a topological sort we can recognize that a dependency is missing (checkdeps) and optionally we can resolve it (resolvedeps). I don't like the slow way that resolvedeps uses now.
Bye, ngaba
-1 on (void *) pointers. These have already gotten us in trouble. Type correctness is maybe something I'm a stickler on, but it solves a lot of errors down the road when new coders come on board. -Dan
Na Tue, Apr 17, 2007 at 02:23:43AM -0400, Dan McGee <dpmcgee@gmail.com> pisal(a):
-1 on (void *) pointers. These have already gotten us in trouble. Type correctness is maybe something I'm a stickler on, but it solves a lot of errors down the road when new coders come on board.
so experienced developers can't use such features because of newbie "coders"? :) that's a bit funny VMiklos -- developer of Frugalware Linux - http://frugalware.org
please do a benchmark with this change for 5000 pkgs. it'll be *very* slow. Hi!
I did the test, the result is really disappointing (with the original pacman, without my patch!): pacman -S `cat n.txt` (<- n.txt contains all packages of sync repos which are not installed.) resolving dependencies... 100% CPU usage, wait for 32 minutes, nothing happens, ctrl-c :-S. So someone really must rewrite deps.c (I found this in TODO.dan), I may try it this weekend. Bye
Na Fri, Apr 20, 2007 at 05:32:46PM +0200, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> pisal(a):
resolving dependencies... 100% CPU usage, wait for 32 minutes, nothing happens, ctrl-c :-S.
welcome to the world of the pacman-g1 development ;) at least it passes here with our packages (3000+) in less than a minute
So someone really must rewrite deps.c (I found this in TODO.dan), I may try it this weekend.
okay, if it still works and faster, that would be great ;) thanks, VMiklos -- developer of Frugalware Linux - http://frugalware.org
welcome to the world of the pacman-g1 development ;) at least it passes here with our packages (3000+) in less than a minute Hi!
Hm. I haven't found any interesting difference between the 2 sortbydeps (except that you renamed libalpm to libpacman ;-). So I may have run into a dependency cycle which forces sortbydeps to do all the sqrt(n) steps, which doesn't exist in your repos. It would be helpful if you'd do your test with AL repos (I did the test with current, extra and community). Note: there are some broken deps in community ;-). Bye, ngaba PS: I may also repeat the test for one repo only.
Na Fri, Apr 20, 2007 at 06:34:14PM +0200, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> pisal(a):
the sqrt(n) steps, which doesn't exist in your repos. It would be helpful if you'd do your test with AL repos
that _would_ be as easy as installing -g2 on your machine ;)
Note: there are some broken deps in community ;-).
yupp, probably their are needed because of The Arch Way. or maybe it was the KISS philosophy? sorry, i already forgot it..
PS: I may also repeat the test for one repo only.
this is totally unrelated to multiple repos i'm sure VMiklos -- developer of Frugalware Linux - http://frugalware.org
On 19:46 Fri 20 Apr , VMiklos wrote:
Na Fri, Apr 20, 2007 at 06:34:14PM +0200, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> pisal(a):
the sqrt(n) steps, which doesn't exist in your repos. It would be helpful if you'd do your test with AL repos
that _would_ be as easy as installing -g2 on your machine ;)
Note: there are some broken deps in community ;-).
yupp, probably their are needed because of The Arch Way. or maybe it was the KISS philosophy? sorry, i already forgot it..
VMiklos, there is no need to remind us that Arch Linux "is teh shit" so often. Nagy, could you please report the broken deps of community to me or to tur-users@archlinux.org ? Cheers, -- Alessio 'mOLOk' Bolognino Arch Linux Trusted User Public Key @ http://themolok.netsons.org/uploads/themolok.asc Key ID = 1024D / FE0270FB 2007-04-11 Key Fingerprint = 9AF8 9011 F271 450D 59CF 2D7D 96C9 8F2A FE02 70FB
Nagy, could you please report the broken deps of community to me or to tur-users@archlinux.org ? Cheers,
fvwm-themes-devel->fvwm-devel gresolver->perl-gettext perl-color-calc->perl-graphics-colornames-www->perl-graphics-colornames->perl-module-load Bye
Na Fri, Apr 20, 2007 at 08:48:32PM +0200, Alessio 'mOLOk' Bolognino <themolok.ml@gmail.com> pisal(a):
VMiklos, there is no need to remind us that Arch Linux "is teh shit" so often.
okay, let me be more constructive, here is a python script to detect broken dependencies: http://darcs.frugalware.org/darcsweb/darcsweb.cgi?r=frugalware-current;a=hea... VMiklos -- developer of Frugalware Linux - http://frugalware.org
On 21:15 Fri 20 Apr , VMiklos wrote:
Na Fri, Apr 20, 2007 at 08:48:32PM +0200, Alessio 'mOLOk' Bolognino <themolok.ml@gmail.com> pisal(a):
VMiklos, there is no need to remind us that Arch Linux "is teh shit" so often.
okay, let me be more constructive, here is a python script to detect broken dependencies:
http://darcs.frugalware.org/darcsweb/darcsweb.cgi?r=frugalware-current;a=hea...
Thanks, I'll take a look at it. Thank you Nagy too. -- Alessio 'mOLOk' Bolognino Arch Linux Trusted User Public Key @ http://themolok.netsons.org/uploads/themolok.asc Key ID = 1024D / FE0270FB 2007-04-11 Key Fingerprint = 9AF8 9011 F271 450D 59CF 2D7D 96C9 8F2A FE02 70FB
this is totally unrelated to multiple repos i'm sure Yes, I am too. But I want to find out which repo contains a dep circle. I repeated the test with one-one repos: the sortbydeps part took about <1 min for each repo. But with 3 repos I got the terrible result again. I looked into the source again... ... and I found a bug: for(l = alpm_pkg_get_provides(q); l; l = l->next) { const char *provname = l->data; if(!strcmp(depend->name, provname)) { if(!_alpm_pkg_find(provname, tmptargs)) { change = 1; tmptargs = alpm_list_add(tmptargs, q); } break; } } Look at _alpm_pkg_find(provname, tmptargs): this should be _alpm_pkg_find(qname, tmptargs) !!!
Bye, ngaba
On 4/20/07, Nagy Gabor <ngaba@petra.hos.u-szeged.hu> wrote:
this is totally unrelated to multiple repos i'm sure Yes, I am too. But I want to find out which repo contains a dep circle. I repeated the test with one-one repos: the sortbydeps part took about <1 min for each repo. But with 3 repos I got the terrible result again. I looked into the source again... ... and I found a bug: for(l = alpm_pkg_get_provides(q); l; l = l->next) { const char *provname = l->data; if(!strcmp(depend->name, provname)) { if(!_alpm_pkg_find(provname, tmptargs)) { change = 1; tmptargs = alpm_list_add(tmptargs, q); } break; } } Look at _alpm_pkg_find(provname, tmptargs): this should be _alpm_pkg_find(qname, tmptargs) !!!
Where is qname defined? And can you please explain why and not just what the bug is? In addition, patch format is much easier for everyone to put in context- it has line numbers, function names, etc. -Dan
Where is qname defined? And can you please explain why and not just what the bug is? Yes, this function is quite messy;-) In each step we permute the objects (tmptargs list) we want to sort (we try to ensure that each package follows its dependencies in the list). So tmptargs stores packages not provides. And in most cases _alpm_pkg_find(provname, tmptargs) is false, so we may add duplicate entries to tmptargs; here we want to check whether q has been added to tmptargs already or not (qname is the name of q). In addition, patch format is much easier for everyone to put in context- it has line numbers, function names, etc.
-Dan ------patch----------- diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c --- pacman-lib/lib/libalpm/deps.c 2007-04-21 08:01:40.000000000 +0200 +++ pacman-lib.new/lib/libalpm/deps.c 2007-04-21 08:05:16.000000000 +0200 @@ -163,7 +163,7 @@ for(l = alpm_pkg_get_provides(q); l; l = l->next) { const char *provname = l->data; if(!strcmp(depend->name, provname)) {
+ if(!_alpm_pkg_find(qname, tmptargs)) { change = 1; tmptargs = alpm_list_add(tmptargs, q); } ---------------------- Bye, ngaba
participants (5)
-
Aaron Griffin
-
Alessio 'mOLOk' Bolognino
-
Dan McGee
-
Nagy Gabor
-
VMiklos