hashing optimizations
Andreas Ericsson
ae at op5.se
Wed Jun 15 16:33:40 CEST 2005
Sorry for the previous noise. This patch is useless without a rewrite of
hash_init() (it's in objects.c). I guess I should have thought to test
that before, eh?
Anyways, the fixed version of the patch isn't too hot either. It's still
a good idea to apply it, since it should speed up the process of
accepting passive checks quite a bit, and it cleans up the code a little
too.
I can rework it to make it better, but that means more extensive
modifications.
Every service in the config causes two hashes to be calculated and
folded together. The traversal that follows the hashing always has to
compare two strings. This is a bit stupid really, as we already know
that each service belongs to only one host (at hashing-time, that is).
Every object that is a "slave" to a host-object has its own hash-table.
This waste memory while accomplishing very little (as they all hash the
same key anyways).
A better approach would be to use a hash_entry type specifically
designed for finding hosts as quickly as possible. Each hash_entry can
contain a pointer to a host object, a hostextinfo object,
hostescalations, hostdependencies, services and whatnot (this also goes
hand in hand with normalizing the structure of the objects).
The gains of such an approach would be less memory used (fewer
hash-tables), faster lookups, less redundant string-mangling, cleaner
code and a robust abstraction layer for quick object lookups.
So... Do or don't?
Andreas Ericsson wrote:
> Ahoy.
>
> The attached patch provides proper hashing for Nagios and the cgi's.
>
> The various functions are implemented in include/hash.h (so they can be
> properly inlined in the functions that use them).
>
> Some minor changes were necessary to other files as well. Notably, I've
> hoisted the initialization of the hashtables to a function of its own to
> save a lot of conditionals (the add_*_to_hashlist are always called from
> an inner loop with tons of iterations).
>
> I've also resized the hash-tables somewhat. Let me know if this turns
> into a memory hog.
>
> Note that I haven't tested this patch yet (except buildtests ofcourse).
> I thought it would be prudent to have a few people compile this on
> different platforms first to find the easy-to-fix showstoppers with odd
> archs/platforms/compilers/whatever.
>
> Heads up for performance tests in a bit. I'll run all tests with Nagios'
> default optimization levels and no arch-specific gcc options, as I
> suppose that's how the vast majority of people running nagios will use it.
>
--
Andreas Ericsson andreas.ericsson at op5.se
OP5 AB www.op5.se
Lead Developer
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
More information about the Developers
mailing list