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 <shiningxc@gmail.com> í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