[pacman-dev] [GIT] The official pacman repository branch, master, updated. v3.0.0-626-g72f40b3
This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "The official pacman repository". The branch, master has been updated via 72f40b3876263f7a8dcda1390026f43f599f8823 (commit) via d683033d3ea79956faf8786f784ce2e271179892 (commit) via 11133da587ebc1c78478cfcd05d5e8298bd61b84 (commit) via 7d37d9278d0ab6eb46ec4689c8091780382cbb95 (commit) from 1e9a1a0292dbbf8039b8fb7536dbff2af28c7afb (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 72f40b3876263f7a8dcda1390026f43f599f8823 Author: Nagy Gabor <ngaba@bibl.u-szeged.hu> Date: Tue Nov 20 09:57:38 2007 +0100 _alpm_checkconflicts split _alpm_innerconflicts: check for target<->target conflicts _alpm_outerconflicts: check for target<->localpkg conflicts This will be useful in sync.c clean-up and in testdb.c As an application the patch also fixes a misleading message (and a memleak) in add.c Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu> Signed-off-by: Chantry Xavier <shiningxc@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org> commit d683033d3ea79956faf8786f784ce2e271179892 Author: Chantry Xavier <shiningxc@gmail.com> Date: Sun Nov 25 16:13:56 2007 -0600 pacman/query.c : -Qo optimization. I didn't understand why realpath was called on every files of every filelist in query_fileowner : ppath = resolve_path(path); It turns out this is needed for the diverted files. For example, cddb_get installs /usr/lib/perl5/site_perl/5.8.8/CDDB_get.pm which actually ends in /usr/lib/perl5/site_perl/current/CDDB_get.pm . And for making pacman -Qo /usr/lib/perl5/site_perl/current/CDDB_get.pm , realpath has to be called on both the target, and the file in the filelist. However, realpath is costly, and calling it on every single file resulted in a poor -Qo performance. Worst case : pacman -Qo /lib/libz.so.1 0.35s user 1.51s system 99% cpu 1.864 total So I did a little optimization to avoid calling realpath as much as possible: first compare the basename of each file. Result: src/pacman/pacman -Qo /lib/libz.so.1 0.24s user 0.05s system 99% cpu 0.298 total Obviously, the difference will be even bigger at the first run (no fs cache), though it's quite scary on my system : 1.7s vs 40s previously. Signed-off-by: Chantry Xavier <shiningxc@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org> commit 11133da587ebc1c78478cfcd05d5e8298bd61b84 Author: Chantry Xavier <shiningxc@gmail.com> Date: Sun Nov 25 16:13:30 2007 -0600 Move mbasename from pacman.c to util.c This function can be useful in other places. Signed-off-by: Chantry Xavier <shiningxc@gmail.com> Signed-off-by: Dan McGee <dan@archlinux.org> commit 7d37d9278d0ab6eb46ec4689c8091780382cbb95 Author: Nagy Gabor <ngaba@petra.hos.u-szeged.hu> Date: Sun Aug 12 22:26:54 2007 +0200 Fix for sync1003 and sync1004 pactests checkdeps and resolvedeps now take both a remove list and an install list as arguments, allowing dependencies to be calculated correctly. This broke the sync990 pactest, but this pactest used dependencies and provides in an unusual way, so it has been changed. Dan: the sync990 pactest was just plain wrong. It didn't satisfy the dependencies correctly, so should never have succeeded. Signed-off-by: Chantry Xavier <shiningxc@gmail.com> [Dan: some variable renaming, clarification in commit message] Signed-off-by: Dan McGee <dan@archlinux.org> ----------------------------------------------------------------------- Summary of changes: lib/libalpm/add.c | 50 +++------ lib/libalpm/alpm.h | 4 +- lib/libalpm/conflict.c | 29 ++++- lib/libalpm/conflict.h | 2 + lib/libalpm/deps.c | 285 ++++++++++++++++++++-------------------------- lib/libalpm/deps.h | 4 +- lib/libalpm/remove.c | 4 +- lib/libalpm/sync.c | 100 +++++----------- pactest/tests/sync990.py | 7 +- src/pacman/pacman.c | 22 ---- src/pacman/query.c | 8 ++ src/pacman/util.c | 22 ++++ src/pacman/util.h | 1 + src/util/testdb.c | 2 +- 14 files changed, 233 insertions(+), 307 deletions(-) hooks/post-receive -- The official pacman repository
commit 7d37d9278d0ab6eb46ec4689c8091780382cbb95 Author: Nagy Gabor <ngaba@petra.hos.u-szeged.hu> Date: Sun Aug 12 22:26:54 2007 +0200
Fix for sync1003 and sync1004 pactests
checkdeps and resolvedeps now take both a remove list and an install list as arguments, allowing dependencies to be calculated correctly.
This broke the sync990 pactest, but this pactest used dependencies and provides in an unusual way, so it has been changed.
Dan: the sync990 pactest was just plain wrong. It didn't satisfy the dependencies correctly, so should never have succeeded.
Signed-off-by: Chantry Xavier <shiningxc@gmail.com> [Dan: some variable renaming, clarification in commit message] Signed-off-by: Dan McGee <dan@archlinux.org>
Wow, thanks. Special thanks to Xavier, who keep this patch in sync with the current tree. 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] 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). Bye, ngaba ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/
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.
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.
Patch attached ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/
On Nov 29, 2007 6:59 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> 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 Fri, Nov 30, 2007 at 12:10:33AM -0600, Aaron Griffin wrote:
On Nov 29, 2007 6:59 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> 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.
On Nov 30, 2007 12:45 AM, Xavier <shiningxc@gmail.com> wrote:
On Fri, Nov 30, 2007 at 12:10:33AM -0600, Aaron Griffin wrote:
On Nov 29, 2007 6:59 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> 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 Nov 30, 2007 8:37 AM, Dan McGee <dpmcgee@gmail.com> wrote:
On Nov 30, 2007 12:45 AM, Xavier <shiningxc@gmail.com> wrote:
On Fri, Nov 30, 2007 at 12:10:33AM -0600, Aaron Griffin wrote:
On Nov 29, 2007 6:59 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> 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.
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)
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.
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.
Fri, 30 Nov 2007 22:45:06 +0100 -n Xavier <shiningxc@gmail.com> í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
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.
Patch attached
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). 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... 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) Bye, ngaba
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.
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.
Bye
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 ?
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. Well, then you must compute it... If we know a dependency that would be broken after -R, we just find a satisfier in the target list and keep that target.
One note (the same holds for checkconflicts): Using pmdb_t* in the parameter list is "elegant" but usually only pkgcache is needed <- I mean checkdeps now. Sometimes alpm_list_t* pkgcache param would be more efficient: You must do a "checkdeps loop" in -Ru, because consider the following example: "pacman -Ru a b c" where localpkg->a->b->c (-> stands for 'depends on') First -Ru will detect that you cannot remove a, because that would break ->a dependency of localpkg, thus it removes a from the target list. In the next loop it will detect then you cannot remove b neither ... But after a target-removal it is enough to pass the old targetlist to checkdeps instead of the whole localdb, since we know that all packages of localdb - oldtargetlist won't be broken after newtargetlist removal. Bye
On Sat, Dec 01, 2007 at 11:25:45PM +0100, Nagy Gabor wrote:
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. Well, then you must compute it... If we know a dependency that would be broken after -R, we just find a satisfier in the target list and keep that target.
Well, I rebased your -Ru patch, and it seems to work fine (at least it didn't break any pactest), but just in case, here is the important part of the rebased patch (I will attach the whole patch as well) : @@ -295,10 +296,17 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(pmdb_t *db, int reversedeps, pmpkg_t *lp = i->data; for(j = alpm_pkg_get_depends(lp); j; j = j->next) { pmdepend_t *depend = j->data; + int found = 0; + pmpkg_t *causingpkg = NULL; /* we won't break this depend, if it is already broken, we ignore it */ + for(k = modified; k && !found; k = k->next) { + causingpkg = k->data; + found = alpm_depcmp(causingpkg, depend); + } + /* 1. check upgrade list for satisfiers */ /* 2. check dblist for satisfiers */ - if(alpm_list_find(modified, depend, satisfycmp) && + if(found && !alpm_list_find(upgrade, depend, satisfycmp) && !alpm_list_find(dblist, depend, satisfycmp)) { char *missdepstring = alpm_dep_get_string(depend); @@ -306,7 +314,7 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(pmdb_t *db, int reversedeps, missdepstring, alpm_pkg_get_name(lp)); free(missdepstring); miss = _alpm_depmiss_new(lp->name, depend->mod, - depend->name, depend->version); + depend->name, depend->version, alpm_pkg_get_name(causingpkg)); baddeps = alpm_list_add(baddeps, miss); } }
Idézés Xavier <shiningxc@gmail.com>:
On Sat, Dec 01, 2007 at 11:25:45PM +0100, Nagy Gabor wrote:
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. Well, then you must compute it... If we know a dependency that would be broken after -R, we just find a satisfier in the target list and keep that target.
Well, I rebased your -Ru patch, and it seems to work fine (at least it didn't break any pactest), but just in case, here is the important part of the rebased patch (I will attach the whole patch as well) :
@@ -295,10 +296,17 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(pmdb_t *db, int reversedeps, pmpkg_t *lp = i->data; for(j = alpm_pkg_get_depends(lp); j; j = j->next) { pmdepend_t *depend = j->data; + int found = 0; + pmpkg_t *causingpkg = NULL; /* we won't break this depend, if it is already broken, we ignore it */ + for(k = modified; k && !found; k = k->next) { + causingpkg = k->data; + found = alpm_depcmp(causingpkg, depend); + } + /* 1. check upgrade list for satisfiers */ /* 2. check dblist for satisfiers */ - if(alpm_list_find(modified, depend, satisfycmp) && + if(found && !alpm_list_find(upgrade, depend, satisfycmp) && !alpm_list_find(dblist, depend, satisfycmp)) { char *missdepstring = alpm_dep_get_string(depend); @@ -306,7 +314,7 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(pmdb_t *db, int reversedeps, missdepstring, alpm_pkg_get_name(lp)); free(missdepstring); miss = _alpm_depmiss_new(lp->name, depend->mod, - depend->name, depend->version); + depend->name, depend->version, alpm_pkg_get_name(causingpkg)); baddeps = alpm_list_add(baddeps, miss); } }
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. Bye ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/
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.
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...
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.
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?
Sun, 2 Dec 2007 00:02:20 +0100 -n Xavier <shiningxc@gmail.com> írta:
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 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
participants (5)
-
Aaron Griffin
-
Dan McGee
-
Dan McGee
-
Nagy Gabor
-
Xavier