This is prepping for the addition of a hash field to each package to greatly speed up the string comparisons we frequently do on package name in _alpm_pkg_find. Signed-off-by: Dan McGee <dan@archlinux.org> --- lib/libalpm/util.c | 21 +++++++++++++++++++++ lib/libalpm/util.h | 1 + 2 files changed, 22 insertions(+), 0 deletions(-) diff --git a/lib/libalpm/util.c b/lib/libalpm/util.c index e425fa4..8e83bda 100644 --- a/lib/libalpm/util.c +++ b/lib/libalpm/util.c @@ -845,4 +845,25 @@ int _alpm_splitname(const char *target, pmpkg_t *pkg) return(0); } +/** + * Hash the given string to an unsigned long value. + * This is the standard sdbm hashing algorithm. + * @param str string to hash + * @return the hash value of the given string + */ +unsigned long _alpm_hash_sdbm(const char *str) +{ + unsigned long hash = 0; + int c; + + if(!str) { + return(hash); + } + while((c = *str++)) { + hash = c + (hash << 6) + (hash << 16) - hash; + } + + return(hash); +} + /* vim: set ts=2 sw=2 noet: */ diff --git a/lib/libalpm/util.h b/lib/libalpm/util.h index 78877a2..0b80420 100644 --- a/lib/libalpm/util.h +++ b/lib/libalpm/util.h @@ -78,6 +78,7 @@ int _alpm_lstat(const char *path, struct stat *buf); int _alpm_test_md5sum(const char *filepath, const char *md5sum); char *_alpm_archive_fgets(char *line, size_t size, struct archive *a); int _alpm_splitname(const char *target, pmpkg_t *pkg); +unsigned long _alpm_hash_sdbm(const char *str); #ifndef HAVE_STRSEP char *strsep(char **, const char *); -- 1.7.3.3

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> --- 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 5b479b4..2ea5125 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); -- 1.7.3.3