> Ethan Galstad wrote:
>> Andreas Ericsson wrote:
>>> So, I started looking into revamping the event queue logic, but ended up
>>> with a migraine from the cumbersome way logging is done, so I decided to
>>> try doing something about it, and the attached 3-patch series is the
>>> result from it.
>>>
>>> It compiles alright, both for nagios and the cgi's. I haven't done much
>>> in the way of checking past that though, so testing would be welcome.
>>>
>>> Given that the patches don't change much in the way of logic, they
>>> shouldn't really affect anything in significant way.
>>>
>> [snip]
>>
>> Thanks for the patches - they are excellent ideas. I'll get them
>> implemented when I get back to the US later this week.
>>
>
> Anytime. I guess the conference spurred some Nagios-hackativity into
> me
>
>> For the event queue, I was thinking that a skip list structure might be
>> best for efficiency (http://en.wikipedia.org/wiki/Skip_list). The event
>> queue is used in primarily two situations:
>>
>> 1. Popping events from the head of the list to be executed
>> 2. Inserting events into the list (mid- or endpoint).
>>
>> #1 is very efficient with a linked list, but performance with #2 can be
>> quite bad in large lists. Since a check event usually appears for each
>> host/service that is defined, this can lead to bad performance - O(n^2)
>> I believe - with large installations. A skip list would bring the
>> performance closer to O(log n).
>>
>> Anyone have comments/experiences they care to share about the
>> performance of skip lists and/or better alternatives?
>>
>
> A skiplist would probably do wonders. I've been experimenting with one
> now, actually using the timestamp for when next to execute
Scratch that. I only glossed the skiplist page you linked, and
misunderstood completely. I've been experimenting with a hash, except
the time used for input is the key. Implementation is trivial and
performance improvement should be fairly close to or better than a
skip-list.
In particular, I'm worried about this snippet:
---%<---%<---%<---
Insertions and deletions are implemented much like the corresponding
linked-list operations, except that "tall" elements must be inserted
into or deleted from more than one linked list.
---%<---%<---%<---
I'm sure it'd be good if one gets it completely right, but it sounds
non-trivial, and with a large object base (100k list-nodes or more),
I'm guessing that "inserted into or delete from more than one
linked list" will eat up the performance gains, unless one sacrifices
lots of memory to keep a very large number of "buckets", although I
fail to see how that would help, since one would then have to walk
a larger number of lists in order to find the right one.
Hmm... I'll have to read that article top to bottom (and when it's
not 2AM), it seems.
--
Andreas Ericsson [email protected]
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
This post was automatically imported from historical nagios-devel mailing list archives
Original poster: [email protected]