Nagios Support Forum

"Ethan Galstad" writes:
> Daniel Drown submitted a patch a few months (or more) back to add
> chained hash support for speeding up searches. His patch (with
> alterations) has been incorporated into the 2.0 code and results in
> major speedups in the CGIs, so that's probably good enough for now
> (considering the CGIs will go away in 3.0).

Note that the problem still exists in the 2.0 source
tree.

For example, common/objects.c:3260 still builds
the service list by finding the tail of the list
with a linear search.

This is O(n^2) and with a 10,000 element service list
chews a considerable amount of CPU time (i.e. something
like 2 - 4 seconds on a gigahertz class processor each
page display).

Changing the service list to a balanced binary tree shrinks that by a
factor of about 30.

Note that this isn't finding a service, this is just
building the sorted list of services.

Michael.





This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]