[pacman-dev] [PATCH 4/4] Used hashed package name in _alpm_pkg_find

[Dan McGee]

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 at 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