On Mon, Nov 26, 2007 at 11:35:51AM +0100, Nagy Gabor wrote:

I noticed a little memleak in the patch: ---------- +char *missdepstring = alpm_dep_get_string(depend); -... +if(!alpm_depcmp(oldpkg, depend)) { + continue; +} ----------

Well, I will create a cosmetics patch for this, soon [I am also quite busy now, be patient ;-)]: 1. get rid of the ugly joined list [maybe with two for-loops] <- I used this to avoid duplicated code, and indeed... the result is _really_ ugly 2. remove compute_requiredby, and check the whole "untouched" localdb by hand [this is more suggestive imho, and a _little bit_ faster]

sounds good.

3. I need your feedback here: Well, the "universal" alpm_list_find is reimplemented in many places, for example we could use this as a search-for-satisfier with the help of alpm_depcmp, the only problem is, that alpm_depcmp's match is 1, not 0 <- So shall I implement a trivial not_alpm_depcmp function as a helper function (my opinion: no) or give a new "compare-function-indicates-match-with" parameter to alpm_list_find (my opinion: yes).

Oh crap, that's confusing. I don't even know which way I prefer, both sound ugly. But I have a small preference for the helper (helper functions are generally needed for using alpm_list_find anyway), rather than a confusing and additional parameter.

On Nov 29, 2007 6:59 AM, Nagy Gabor wrote:

Patch attached

Yay, simpler code is always fun. This looks MUCH simpler. It's a big chunk of changes to digest, but I think it all looks good. At least all the pactests pass - anyone have an opinion here?

On Nov 30, 2007 12:45 AM, Xavier wrote:

On Fri, Nov 30, 2007 at 12:10:33AM -0600, Aaron Griffin wrote:

...

On Nov 29, 2007 6:59 AM, Nagy Gabor wrote:

...

Patch attached

Yay, simpler code is always fun. This looks MUCH simpler.

It's a big chunk of changes to digest, but I think it all looks good. At least all the pactests pass - anyone have an opinion here?

Having a more careful look at it is on my TODO list for the next few days :) But if you think it's fine, you can always merge it, and I'll review it later.

I'll be looking at it this weekend for sure. The "check localdb by hand" comment scares me a bit, but I haven't dove into the code yet. -Dan

On Fri, Nov 30, 2007 at 11:05:31AM -0600, Aaron Griffin wrote:

Yeah, I did a rough review. It looked well done, so I applied and checked, and got no errors, but I do need to do a side-by-side compare. I was hoping someone else did already 8)

It looks perfect to me, sign-off.

Fri, 30 Nov 2007 22:45:06 +0100 -n Xavier írta:

On Fri, Nov 30, 2007 at 08:37:13AM -0600, Dan McGee wrote:

...

I'll be looking at it this weekend for sure. The "check localdb by hand" comment scares me a bit, but I haven't dove into the code yet.

Maybe some pseudo-code could help, but not sure if it's a good idea.

compute_requiredby(pkg) : for p in localdb for dep in p.deps if pkg satisfies dep add p to the return list

checkdeps : for p in {upgrade U remove} for q in compute_requiredby(p) for dep in q.deps if p satisfies dep /* check if dep is still satisfied by another pkg */

The minor problems with the above : 1) the localdb is scanned n times, with n = length of upgrade + remove lists. 2) the dependency that is the cause of q being required by p is lost (the "for dep in q.deps; if p satisfies dep ..." is done twice : first in compute_requiredby , then again in checkdeps)

Instead of that, the localdb just needs to be scanned once. And for each package, we check if it depends on a package going to be upgraded or removed. Some other small "issues": And when you compute requiredby you needn't check the whole db, dblist (see my patch) is enough (what's more: needed), which can be much smaller with -Su for example [however, you must dblist once] And compute_requiredby returns with a list of strings (grr), and you must do pkgcache scan for find the package. Bye

On Sat, Dec 01, 2007 at 12:43:21AM +0100, Nagy Gabor wrote:

Some notes: 1. + joined = alpm_list_join(alpm_list_copy(remove), alpm_list_copy(upgrade)); + dblist = alpm_list_diff(_alpm_db_get_pkgcache(db), joined, _alpm_pkg_cmp); + alpm_list_free(joined); Well, this is done immediately after checkdeps call, which may be unneeded (remove == NULL or upgrade == NULL, this is a usual case), and dblist shouldn't be calculated if reverse==0 and we don't need it (packages have no dependencies or satisfied by upgrade list).

Right, feel free to do these little optimizations :)

2. + alpm_list_t *modified = alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp); I would prefer "intersect(dbcache, joined)", because usually joined is a smaller list than dblist, but we have no such function.

Maybe that would also make that part clearer, especially if you rename joined to targets or something :) That would also add yet another list function, and I'm not sure there will be many use cases for it, but it's general enough, so it's acceptable imo.

3. alpm_list_diff is quite fast (n+m), but it needs to order lists first O(nlogn)+O(mlogm); however dbcache is initially(?) ordered. Note: We had some alpm_list problems nowadays, after this patch alpm_list_diff function becomes crucial...

This would depend on the order in which readdir reads the file on the filesystem, right? So on the order on the filesystem? I am not sure if there is any garanty it will always be in the order we want (on any filesystem, any os), but I may be totally off, so hopefully someone else knows better :) 4. Hmm, how am I supposed to rebase your unneeded patch now? :) Seems like the "causingpkg" is now hidden behind the alpm_list_find + satisfycmp function.

Summary: Overall the new version is much more powerful (imho) if it must check many targets, but point 1. shows that the current resolvedeps may becomes slower after this patch, because checkdeps is called on all packages (but see also my resolvedeps patch, which reduces checkdeps calls in "usual" cases -- not smoke001.py-like)

Hm ok. let's discuss that in that other thread.

On Sat, Dec 01, 2007 at 10:52:23PM +0100, Nagy Gabor wrote:

...

...

3. alpm_list_diff is quite fast (n+m), but it needs to order lists first O(nlogn)+O(mlogm); however dbcache is initially(?) ordered. Note: We had some alpm_list problems nowadays, after this patch alpm_list_diff function becomes crucial...

This would depend on the order in which readdir reads the file on the filesystem, right? So on the order on the filesystem? I am not sure if there is any garanty it will always be in the order we want (on any filesystem, any os), but I may be totally off, so hopefully someone else knows better :) cache.c, lines: 71, 134.

Oh ok, I missed this explicit msort call, I didn't know about that :) So why not having an alpm_list_diff_sorted function, and making alpm_list_diff sort the two lists, then call alpm_list_diff_sorted ?

On Sun, Dec 02, 2007 at 11:09:03PM +0100, Nagy Gabor wrote:

Looks fine. We also can modify alpm_list_find to return NULL if no element was found or return with a pointer to the "found" element.

Of course, I was even wondering why it didn't return the element I wanted, but I didn't even consider actually modifying the function :p

On Sat, Dec 01, 2007 at 12:43:21AM +0100, Nagy Gabor wrote:

...

Some notes: 2. + alpm_list_t *modified = alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp); I would prefer "intersect(dbcache, joined)", because usually joined is a smaller list than dblist, but we have no such function. 3. alpm_list_diff is quite fast (n+m), but it needs to order lists first O(nlogn)+O(mlogm); however dbcache is initially(?) ordered. Note: We had some alpm_list problems nowadays, after this patch alpm_list_diff function becomes crucial...

Slightly off-topic, but a note related to list_diff and list_intersect function : fileconflicts have apparently its own functions (check_filedifference and check_fileconflicts). I wonder if these could be replaced to use generic list functions instead.

+1 And I was totally wrong, alpm_list_diff is SLOW, I thought that it uses a more clever algorithm <- so it doesn't sort anything [*], and alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp) is also much slower than I expected. Some other notes: 1. Why pkgcache is sorted? Do we use this somewhere? Yes, sorted lists are more efficient, we can find or remove elements faster, but as I see, we don't assume anywhere that this is a sorted list [well, we call list_add_sorted in add_pkgincache, but this is slower then pkg_add_last ;-]. Probably no, and that's why you didn't know about this. 2. I warn you, that alpm_list_intersect would be a funny function: that would be _asymmetric_, because we use a compare function for compare: In the example above: intersect(dbcache, joined) finds the to-be-modified local packages, but intersect(joined, dbcache) finds packages in the target which has old version installed, these are not the same! 3. pointercmp and satisfycmp warning. These are NOT real compare functions, so you should NEVER use ptrcmp in a clever (like in check_fileconflicts) alpm_list_diff. Probably this is the main reason for [*] Bye

On Sat, Dec 01, 2007 at 11:43:19PM +0100, Nagy Gabor wrote:

...

+1 And I was totally wrong, alpm_list_diff is SLOW, I thought that it uses a more clever algorithm <- so it doesn't sort anything [*], and alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp) is also much slower than I expected.

Ok, I found your previous mail a bit strange, I understand now.

...

Some other notes: 1. Why pkgcache is sorted? Do we use this somewhere? Yes, sorted lists are more efficient, we can find or remove elements faster, but as I see, we don't assume anywhere that this is a sorted list [well, we call list_add_sorted in add_pkgincache, but this is slower then pkg_add_last ;-]. Probably no, and that's why you didn't know about this.

Well, I'm confused. First you seemed to think it was a good idea to sort the list at the base, and then use this for having more efficient functions. And now, it seems like you are saying it's a bad idea... To be clear: _Currently_ we don't benefit (in speed) from our sorted

Sun, 2 Dec 2007 00:02:20 +0100 -n Xavier írta: pkgcaches -- but they are sorted now <- this is bad. Hmm... maybe sorted pkgcache is good for 'pacman -Qi', and well, this makes our search-for-provider method deterministic. So now I could answer my 'Why pkgcache is sorted?' question. Usually I don't have clear opinion about complex things first, I just try to find pros and contras (and listen yours) and _then_ make decision.

...

2. I warn you, that alpm_list_intersect would be a funny function: that would be _asymmetric_, because we use a compare function for compare: In the example above: intersect(dbcache, joined) finds the to-be-modified local packages, but intersect(joined, dbcache) finds packages in the target which has old version installed, these are not the same!

I don't understand this at all.

alpm_pkg_cmp(package1, package2) == 0 doesn't mean that 'package1 == package2', this just implies that they have the same pkgname. So how do you define intersection? Which package (package1 or package2) do you want to select to intersect of A and B?

...

3. pointercmp and satisfycmp warning. These are NOT real compare functions, so you should NEVER use ptrcmp in a clever (like in check_fileconflicts) alpm_list_diff. Probably this is the main reason for [*]

I don't understand this either. check_fileconflicts uses strcmp, what's the problem with this? This was just a warning, that they are not real compare-functions (trichotomy doesn't hold) and you should keep this in mind, when you want to use clever chk_filedifference-like fast alpm_list_diff algorithm (you can easily say first that the current ptrcmp would be enough for a simple 'A - B' set operation, because an 'a equals b' function is enough for doing this, but it isn't.)

Bye