Hi! On Sat, Apr 22, 2006 at 02:15:15AM -0700, Mark D. Anderson wrote: >[...]
>an alternative approach for example would be to use an >array instead and do this for the loop: >1. sort the array if any timeouts have been added/removed since last >sort. >treated removed events as having infinite timeout, so they are moved to >the end of the array which can be used for empty space. Not efficient I guess. In worst case O(n^2 * log n), if I'm correct with this estimate. >[...] >A benefit of the above approach is that changing the >timeout value in a persistent event doesn't affect performance >much. But then, what's the problem in spending 2*log n for changing the timeout? >Yet another choice would be a "Judy tree". Wouldn't you then spend the time for deletion and re-insertion, too? >Yet another approacch that would be very fast is to take advantage >of the fact that the programmer likely doesn't care too much about >exact timeout values. Suppose that the longest timeout value to >be used is 1 minute, and the programmer doesn't care about anything >better than 5 second resolution. Then all that is needed is 12 linked >lists, one for each 5-second interval in a minute. Each list is itself >unsorted. Then every operation is very fast: > add - push the event onto list number = timeout / 12 : O(1) > del - remove from linked list: O(1) > min - find first list with > 0 entries: effectively O(1) > foreach - drain all lists up to expiration / 12 : O(1) >This is only applicable in the conditions stated, but I believe those >to be quite typical. I don't. I care for relatively exact timeouts and I use libevent for that. >I guess the easiest way to do the experiment would be to override >the RB_* macros in event.c. Then just do so. :-) Perhaps the Judy tree thing could be efficient for some cases indeed. However the implementation that I found with google is LGPL, which is IIRC more restrictive than libevent's current license, which would discourage me, at least, from using that code. >-mda Kind regards, Hannah. _______________________________________________ Libevent-users mailing list [email protected] http://monkey.org/mailman/listinfo/libevent-users
