On Sun, Nov 04, 2007 at 05:04:25PM -0800, Scott Lamb wrote: > > * timers are managed by a priority queue (O(1) for important operations > > as opposed to O(log n) in libevent, also resulting in much simpler code). > > In terms of concrete data types, you appear to have used a binary heap? > So by "important operations" you mean removal, correct? Insertion is > still O(log n)? The asymptotic behavior is no different, then, as > insertion happens at least as often as removal.
Not to put on my O-face, but binary heap insert is *average* O(1). There should be a performance win for libevent, when it comes to timer checking, as using a heap will also be O(1) for heap_min() - which will benefit pending timer calculation code. However, early delete w/ pending timer will need some rigging or tombstone games. I wouldn't be surprised that, in a case where one is consistently resetting timers (think read/write before x time passes) and re-adding said event, that in the end it will be the same amount of CPU time. -cl _______________________________________________ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
