Major speedup of CGI

[michael at optusnet.com.au]

"Ethan Galstad" <nagios at nagios.org> 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 sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf