On 7/1/09, Nick Mathewson ni...@freehaven.net wrote:
On Wed, Jul 01, 2009 at 01:05:33PM +0300, Marko Kreen wrote:
Hm. How about this - keep using min-heap, but let each slot contain
doubly-linked list of events. So equal (abs) timeout values would
share the same slot. This would bring minimal additional complexity
to codebase.
Sorry; this would handle the case where two events are scheduled for
the same _time_, but the more common case I was talking about was the
one where multiple events are scheduled with the same _timeout_. In
other words, it's not so common to see an app where the programmer
schedules 10 events for 10:03:45.0200... but it's very common to see
an app where nearly all events are scheduled to fire 10 seconds from
now.
No, I was talking about the abs scheduled time for those 10s events.
If we assume:
- there are lots of timer events
- they small number of relative timeouts used, or at least the timeouts
are not very fine-grained (and are non-random)
then the abs timeouts for actual launch times will end up nearby
each other.
Also, although cached per-base tv_cache should already create some amount
of equal timeouts, this can be increased by rounding abs timeout values
to fixed granularity positions, depending how far in the future they are:
0.. 1s - 1ms?
1..10s - 100ms
10s - 1s
No, I think rounding is a pretty bad idea. There are people who
actually care about timing accuracy: if they ask for 10.4 seconds and
we give them 10 seconds, they won't be amused.
Obviously the rounding should be done up not down, in this case 10.5
(or 11) secs, not 10...
The granularity would increase the slot sharing. Btw, I stole the idea
from Linux which already does such adaptive granularity, see function
__estimate_accuracy() in fs/select.c.
Ofcourse it is much more conservative than my proposal above.
If the number where too scary there, they can be toned down.
But if anyone schedules for 10.4 sec and expects to be called
after exactly 1040 microseconds - I would call him silly...
The timer are already delayed and the more events you have the
more they can be.
--
marko
___
Libevent-users mailing list
Libevent-users@monkey.org
http://monkeymail.org/mailman/listinfo/libevent-users
