Re: [Libevent-users] order of timers when attached inside a callback
- Original Message > From: Marko Kreen > To: Nick Mathewson ; [email protected] > Sent: Wednesday, July 1, 2009 4:02:28 PM > Subject: Re: [Libevent-users] order of timers when attached inside a callback > > On 7/1/09, Nick Mathewson wrote: > > On Wed, Jul 01, 2009 at 01:05:33PM +0300, Marko Kreen wrote: > > > 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. [snip] > > 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. Call me silly, but I expect libevent to at least try for 1040 microseconds, and it appears to do a reasonable job even with a large number of timers. If it happened after 1000 microseconds, I would indeed not be amused. :) Larry ___ Libevent-users mailing list [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
On 7/1/09, Nick Mathewson 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 [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
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". > 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. yrs, -- Nick ___ Libevent-users mailing list [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
On 6/30/09, Nick Mathewson wrote: > On Tue, Jun 30, 2009 at 01:00:13PM +0300, Marko Kreen wrote: > [...] > > > The timeouts are kept in min-heap structure, whose goal is to make easy > > to find smallest timeout. It does not store the event addition order > > in a way that works 100% of the time, although it may happen to work 90% > > of the time. This is expected and correct behaviour. > > > > To have a guarantee that order is followed 100% of the time means > > replacing the structure with something more complex that can give such > > guarantees. IMHO it is pointless. > > > Actually, there's a case to be made that we could augment our min-heap > structure with something smarter. Check out the comments on the > bugtracker entry at > > > https://sourceforge.net/tracker/?func=detail&aid=1955777&group_id=50884&atid=461322 > > The idea is that min-heap performs at an asymptotically optimal O(lg > n) in the case where you have a randomly distributed set of timeouts. > But in practice, many programs have a large number of timers that > cluster around a smalr sets of timeout intervals, and for a > distribution like this, a doubly-linked queue could get O(1) > insert/remove. But we wouldn't want a doubly-linked queue in general, > since it has O(n) performance in the general case. So instead, we > might want a facility to let application developers have some timeout > values wind up queued, and others wind up heaped. This would probably > be a tricky design challenge, and would want a fair bit of > benchmarking to make sure it's a real win and doesn't actually hurt > performance. 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. 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 This would result in minimal amount of slots in use in min-heap. -- marko ___ Libevent-users mailing list [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
On Tue, Jun 30, 2009 at 01:00:13PM +0300, Marko Kreen wrote: [...] > The timeouts are kept in min-heap structure, whose goal is to make easy > to find smallest timeout. It does not store the event addition order > in a way that works 100% of the time, although it may happen to work 90% > of the time. This is expected and correct behaviour. > > To have a guarantee that order is followed 100% of the time means > replacing the structure with something more complex that can give such > guarantees. IMHO it is pointless. Actually, there's a case to be made that we could augment our min-heap structure with something smarter. Check out the comments on the bugtracker entry at https://sourceforge.net/tracker/?func=detail&aid=1955777&group_id=50884&atid=461322 The idea is that min-heap performs at an asymptotically optimal O(lg n) in the case where you have a randomly distributed set of timeouts. But in practice, many programs have a large number of timers that cluster around a smalr sets of timeout intervals, and for a distribution like this, a doubly-linked queue could get O(1) insert/remove. But we wouldn't want a doubly-linked queue in general, since it has O(n) performance in the general case. So instead, we might want a facility to let application developers have some timeout values wind up queued, and others wind up heaped. This would probably be a tricky design challenge, and would want a fair bit of benchmarking to make sure it's a real win and doesn't actually hurt performance. -- Nick ___ Libevent-users mailing list [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
On 6/30/09, Denis Bilenko wrote: > On Thu, Jun 25, 2009 at 12:39 PM, Adrian Chadd wrote: > > I didn't think this was documented. As such, why would you expect them > > to fire in-order? :) > > > On Thu, Jun 25, 2009 at 12:53 PM, Clint Webb wrote: > > If you need things to happen in a particular order, you need to sequence > > your timeouts from each other. In an event based system, you cannot > > guarantee the order that the events will be fired. > > > Why not? There is nothing that prevents the scheduler to fire such > events in the order > they were added. In fact, that what libevent seems to do when I call > event_add() before > entering the loop. > > However, if I do the same inside a callback, the order is exactly > reversed except for the first event. > > This suggests that (although I haven't looked through the code, so I > might be wrong) > this is accidental and libevent can be fixed to behave like that, but > nobody needed such > feature so far. It could also be that this is by design or that it's > impossible to implement > without performance penalty, in which case it's not worth bothering. > Could someone familiar > with the code shed the light on this? > > I am implementing libevent hub for eventlet [1] and it has come to > depend on such behavior, > so I had to work around the issue. I don't like the workaround though. > > [1] http://bitbucket.org/denis/eventlet/ The timeouts are kept in min-heap structure, whose goal is to make easy to find smallest timeout. It does not store the event addition order in a way that works 100% of the time, although it may happen to work 90% of the time. This is expected and correct behaviour. To have a guarantee that order is followed 100% of the time means replacing the structure with something more complex that can give such guarantees. IMHO it is pointless. IOW, you need to fix your code. Increasing the timeval sort of works but is ugly and will cause more wakeups for event loop. Better is to write your own API on top of libevent that can queue sequence of callbacks to single libevent timer. Or simply get rid of the requirement. -- marko ___ Libevent-users mailing list [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
On Thu, Jun 25, 2009 at 12:39 PM, Adrian Chadd wrote: > I didn't think this was documented. As such, why would you expect them > to fire in-order? :) On Thu, Jun 25, 2009 at 12:53 PM, Clint Webb wrote: > If you need things to happen in a particular order, you need to sequence > your timeouts from each other. In an event based system, you cannot > guarantee the order that the events will be fired. Why not? There is nothing that prevents the scheduler to fire such events in the order they were added. In fact, that what libevent seems to do when I call event_add() before entering the loop. However, if I do the same inside a callback, the order is exactly reversed except for the first event. This suggests that (although I haven't looked through the code, so I might be wrong) this is accidental and libevent can be fixed to behave like that, but nobody needed such feature so far. It could also be that this is by design or that it's impossible to implement without performance penalty, in which case it's not worth bothering. Could someone familiar with the code shed the light on this? I am implementing libevent hub for eventlet [1] and it has come to depend on such behavior, so I had to work around the issue. I don't like the workaround though. [1] http://bitbucket.org/denis/eventlet/ ___ Libevent-users mailing list [email protected] http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
If you need things to happen in a particular order, you need to sequence
your timeouts from each other. In an event based system, you cannot
guarantee the order that the events will be fired.
Instead of creating A B and C at the same time, if you need them to go in
that order, you will need to create A, when it fires let it create B, and
when it fires let it create C.
On Thu, Jun 25, 2009 at 1:28 PM, Denis Bilenko wrote:
> Hi,
>
> I've run into an issue that surprised me a bit. I'm installing a few
> timeouts to be
> executed on a following loop iteration, i.e. after zero seconds. I
> would expect the timeouts
> happen in the order they were installed, however, this is not the
> case. Here's the code
> that shows the issue:
>
> #include
> #include "event.h"
>
> struct event e[3];
> struct timeval zero = {0, 0};
>
> void print(int fd, short events, char * text)
> {
>printf(text);
> }
>
> void callback(int fd, short events, void * arg)
> {
>timeout_set(&e[0], print, "A\n");
>timeout_add(&e[0], &zero);
>timeout_set(&e[1], print, "B\n");
>timeout_add(&e[1], &zero);
>timeout_set(&e[2], print, "C\n");
>timeout_add(&e[2], &zero);
> }
>
> int main()
> {
>struct event e;
>event_init();
>timeout_set(&e, callback, NULL);
>timeout_add(&e, &zero);
>event_dispatch();
> }
>
> The output of this program is
> libevent$ ./a.out
> A
> C
> B
>
> not ABC as I would like.
>
> If I do the same outside of the callback, the order is maintained as
> expected.
>
> Adding more timers suggests that all of them except the first one (A)
> are executed in the reverse order.
> Again, doing the same outside of a callback makes them run in the
> expected order.
>
> Is this a bug or it's supposed to work this way? Maybe I'm doing
> something wrong and there is a way
> of getting the expected behavior without resorting to increasing
> timeval for each new call?
>
> Thanks,
> Denis.
> ___
> Libevent-users mailing list
> [email protected]
> http://monkeymail.org/mailman/listinfo/libevent-users
>
--
"Be excellent to each other"
___
Libevent-users mailing list
[email protected]
http://monkeymail.org/mailman/listinfo/libevent-users
Re: [Libevent-users] order of timers when attached inside a callback
On Thu, Jun 25, 2009, Denis Bilenko wrote:
> Hi,
>
> I've run into an issue that surprised me a bit. I'm installing a few
> timeouts to be
> executed on a following loop iteration, i.e. after zero seconds. I
> would expect the timeouts
> happen in the order they were installed, however, this is not the
> case. Here's the code
I didn't think this was documented. As such, why would you expect them
to fire in-order? :)
> that shows the issue:
>
> #include
> #include "event.h"
>
> struct event e[3];
> struct timeval zero = {0, 0};
>
> void print(int fd, short events, char * text)
> {
> printf(text);
> }
>
> void callback(int fd, short events, void * arg)
> {
> timeout_set(&e[0], print, "A\n");
> timeout_add(&e[0], &zero);
> timeout_set(&e[1], print, "B\n");
> timeout_add(&e[1], &zero);
> timeout_set(&e[2], print, "C\n");
> timeout_add(&e[2], &zero);
> }
>
> int main()
> {
> struct event e;
> event_init();
> timeout_set(&e, callback, NULL);
> timeout_add(&e, &zero);
> event_dispatch();
> }
>
> The output of this program is
> libevent$ ./a.out
> A
> C
> B
>
> not ABC as I would like.
>
> If I do the same outside of the callback, the order is maintained as expected.
>
> Adding more timers suggests that all of them except the first one (A)
> are executed in the reverse order.
> Again, doing the same outside of a callback makes them run in the
> expected order.
>
> Is this a bug or it's supposed to work this way? Maybe I'm doing
> something wrong and there is a way
> of getting the expected behavior without resorting to increasing
> timeval for each new call?
>
> Thanks,
> Denis.
> ___
> Libevent-users mailing list
> [email protected]
> http://monkeymail.org/mailman/listinfo/libevent-users
--
- Xenion - http://www.xenion.com.au/ - VPS Hosting - Commercial Squid Support -
- $25/pm entry-level VPSes w/ capped bandwidth charges available in WA -
___
Libevent-users mailing list
[email protected]
http://monkeymail.org/mailman/listinfo/libevent-users
