Nagios Support Forum

In message ,
Andreas Ericsson writes:

>Andreas Ericsson wrote:
>> Ethan Galstad wrote:
>>> 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.

Hmm, maybe I am missing something, but if I have an element with a
known key, I see how a hash table pointing into a conventional linked
list will speed up access. But doesn't case 2 take the form:

insert node X that should run at time t into the linked list

mean a sequential scan of the linked list? How do you know what time
to hash to find the node before time t?

E.G. I want node X inserted at 10:24:33, how do I know if the prior
node is at 10:24:32, or 10:14:32?

>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.

Does this agree with what you are thinking? As I understand skip
lists, you have a node that looks like:

struct node {
listN_forward * node;
listN_reverse * node;
listN-1_forward * node;
listN-1_reverse * node;
...
list0-forward * node;
list0-reverse * node;
data...
}

Please exclude the explicit hard coded lists pointers.

where my "listN" is your bucket (note some (most) implementations use
only forward and not reverse pointers). So a single node can be on
multiple lists. Then you have something like:



node1 node2 node3 node4 node5 node6 node7

N

N-1

N-2

...

0

So to find node3, you search the N linked list starting a node1, and
end up at node 4 (by following the ----> forward pointer). Since
node4's key is > node 3's key, you realize you have overshot node3, so
you go back to node1 and search the linked list N-1.

Following the forward link from node1(N-1) leads you right to node3.

If you wanted node6, again start at node1 follow the N forward link to
node4, follow the N forward link to node7, you have overshot, so
follow the link back to node 4 and follow the node4(N-1) forward link
to node5. Then node5((N-1) leads to node7, which overshoots node 6, so
follow the node5(0) link to node6, and you have success.

To find node 6 is 5 traversals. Which is really not much of a savings,
but with thousands of services I would expect a larg

...[email truncated]...


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