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 10400000 microseconds - I would call him silly...
The timer are already delayed and the more events you have the
more they can be.

Libevent-users mailing list

Reply via email to