Na Sat, Apr 14, 2007 at 11:42:44AM +0200, Nagy Gabor 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

Na Mon, Apr 16, 2007 at 02:14:22PM +0200, Nagy Gabor 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

On 4/16/07, Nagy Gabor  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.

On 4/17/07, Nagy Gabor 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

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

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.

On 19:46 Fri 20 Apr , VMiklos wrote:

Na Fri, Apr 20, 2007 at 06:34:14PM +0200, Nagy Gabor 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

Na Fri, Apr 20, 2007 at 08:48:32PM +0200, Alessio 'mOLOk' Bolognino 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

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