On Tue, Dec 14, 2010 at 7:46 PM, Dan McGee <dan@archlinux.org> wrote:
This series of patches makes finding a package in our linked list implementation a whole lot faster, if that search is using the standard _alpm_pkg_find, which nearly all are (after the first patch).
It does this by adding a hash function to util.c which is nothing too complicated and named after a publicly available algorithm. When packages are created, we fill in this hash value as soon as the pkgname is read. Finally, the _alpm_pkg_find function is rewritten to take advantage of this field, avoiding repeated strcmp() calls and only falling back to that if a hash is not available and to verify the hash value was not some sort of collision.
Performance figures and numbers are available in the last patch. This actually speeds up operations by nearly 33%, so this is not a total waste of time to consider. :) Review and questions/comments/concerns welcome!
That's nice and short :)
-Dan
Dan McGee (4): Use _alpm_pkg_find in deps search Add hash_sdbm function When setting package name, set hash value as well Used hashed package name in _alpm_pkg_find
lib/libalpm/be_package.c | 1 + lib/libalpm/deps.c | 4 ++-- lib/libalpm/package.c | 16 ++++++++++++++-- lib/libalpm/package.h | 1 + lib/libalpm/util.c | 22 ++++++++++++++++++++++ lib/libalpm/util.h | 1 + 6 files changed, 41 insertions(+), 4 deletions(-)
-- 1.7.3.3