diff options
author | Dan McGee <dan@archlinux.org> | 2010-12-14 12:36:02 -0600 |
---|---|---|
committer | Dan McGee <dan@archlinux.org> | 2010-12-14 12:36:02 -0600 |
commit | 919bb6c9e00820c3930067b5985a246a455bef57 (patch) | |
tree | aff800a6e65184a873c02bcb908196b0022047c5 /lib/libalpm | |
parent | c2a73ba989fffb59c1b8ac7edb265a996dfc184d (diff) |
Used hashed package name in _alpm_pkg_find
This results in huge gains to a lot of our codepaths since this is the most
frequent method of random access to packages in a list. The gains are seen
in both profiling and real life.
$ pacman -Sii zvbi
real: 0.41 sec -> 0.32 sec
strcmp: 16,669,760 calls -> 473,942 calls
_alpm_pkg_find: 52.73% -> 26.31% of time
$ pacman -Su (no upgrades found)
real: 0.40 sec -> 0.50 sec
strcmp: 19,497,226 calls -> 524,097 calls
_alpm_pkg_find: 52.36% -> 26.15% of time
There is some minor risk with this patch, but most of it should be avoided
by falling back to strcmp() if we encounter a package with a '0' hash value
(which we should not via any existing code path). We also do a strcmp once
hash values match to ensure against hash collisions. The risk left is that a
package name is modified once it was originally set, but the hash value is
left alone. That would probably result in a lot of other problems anyway.
Signed-off-by: Dan McGee <dan@archlinux.org>
Diffstat (limited to 'lib/libalpm')
-rw-r--r-- | lib/libalpm/package.c | 15 |
1 files changed, 13 insertions, 2 deletions
diff --git a/lib/libalpm/package.c b/lib/libalpm/package.c index 5b479b4f..2ea51251 100644 --- a/lib/libalpm/package.c +++ b/lib/libalpm/package.c @@ -552,6 +552,7 @@ int _alpm_pkg_cmp(const void *p1, const void *p2) pmpkg_t *_alpm_pkg_find(alpm_list_t *haystack, const char *needle) { alpm_list_t *lp; + unsigned long needle_hash; ALPM_LOG_FUNC; @@ -559,11 +560,21 @@ pmpkg_t *_alpm_pkg_find(alpm_list_t *haystack, const char *needle) return(NULL); } + needle_hash = _alpm_hash_sdbm(needle); + for(lp = haystack; lp; lp = lp->next) { pmpkg_t *info = lp->data; - if(info && strcmp(info->name, needle) == 0) { - return(info); + if(info) { + /* a zero hash will cause a fall-through just in case */ + if(info->name_hash && info->name_hash != needle_hash) { + continue; + } + + /* finally: we had hash match, verify string match */ + if(strcmp(info->name, needle) == 0) { + return(info); + } } } return(NULL); |