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