[pacman-dev] [PATCH 0/4] Package list find performance improvements

[Xavier Chantry]

On Tue, Dec 14, 2010 at 7:46 PM, Dan McGee <dan at 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
>
>
>