[Twisted-Python] Re: r15451 - Fix test failures under windows by changing the eventual-send operation to
Yes it does: order of method call.
Ah. That's useful to know: I would prefer to use a non-threading-related call to achieve this eventual-send functionality. I'll add a TODO test to check that this promise is being met.
It should be fixable by storing the last time of an element added to the queue, and adding epsilon if current time is the same.
Wouldn't you have to guarantee that epsilon is smaller than the resolution of your time.time() return value? What if you sorted on a tuple of (time, counter) instead? (the down side is that you'd have to search for all existing timers with the same time value to figure out what counter value you ought to use. ick.). We should clarify what guarantees are made by callLater. I think there may be several separate ones here: 1: callLater(0, A); callLater(0, B) will result in A being invoked before B will result in both A and B being invoked before any other DelayedCalls 2: callLater(N, A); callLater(N, B) will result in A being invoked before B 3: callLater(N, A); callLater(N+M, C); callLater(N, B) will result in A being invoked before B (think of this as a unit test for the adding-epsilon concern above) The second and third ones are not so important to me, just in terms of what I need to use it as a plan-coordination tool. I only intend to use this with N=0. To that end, using a separate queue for timers that are ready to go "now" (i.e. ones that will be fired before calling select() or the like) might be useful, basically making N=0 a special case. This would avoid the overhead of inserting the DelayedCall into an arbitrary place and maintaining the ordering guarantees of #2 and #3, and would avoid an extra select() spin between the time an N=0 timer was inserted and the time it was fired. The existing threadCallQueue happens to behave exactly this way, although I'd want to write some additional tests to make sure it gets serviced as many times as it's supposed to be (specifically, when threads are unavailable and therefore wakeUp() is not used, does a call inserted from within an N=0 callback get serviced before the reactor sleeps again?). The problem is both the word "thread" in the name, and the fact that we might not be making the same guarantees about the behavior of callFromThread as we are about that of callLater. Hmm. Most reactors split off a list of timers that are ready to go "now" on each spin, right? And/or there's that _pendingTimedCalls list I see in t.i.base .. maybe we could take advantage of one of those, just appending the call to those lists and making sure they'll be serviced again, rather than adding the overhead of maintaining ordering guarantees #2 and #3. hmm-ingly, -Brian
----- Original Message ----- From: "Brian Warner" <warner@lothar.com> To: "Twisted general discussion" <twisted-python@twistedmatrix.com> Sent: Saturday, December 31, 2005 1:57 PM Subject: [Twisted-Python] Re: r15451 - Fix test failures under windows by changing the eventual-send operation to
To that end, using a separate queue for timers that are ready to go "now" (i.e. ones that will be fired before calling select() or the like) might be useful, basically making N=0 a special case. This would avoid the overhead of inserting the DelayedCall into an arbitrary place and maintaining the ordering guarantees of #2 and #3, and would avoid an extra select() spin between the time an N=0 timer was inserted and the time it was fired.
specialcasing this is ugly, imo, not that i get any votes ;) you need to decide: 1. what cost you want insert, traversal and possibly async sorting/ordering passes to carry 2. what guarantees you want to provide, in the general case eg, it would be reasonable to say 'we want to be O(1) on traversal' (at least O(1) in terms of getting a list of events that fire now) and we want to guarantee ordering in this case, you can decide to take the full ordering/sorting hit on inserts. if you think a little harder, this can be made fairly efficient with a sparse circular list of event buckets, with each bucket being a fifo queue of events to be fired at that time. whether it's worth bothering with the additional complexity is up for discussion. i'm sleep deprived, so apologies in advance if this made no sense at all. -p
Paul G wrote:
full ordering/sorting hit on inserts. if you think a little harder, this can be made fairly efficient with a sparse circular list of event buckets, with each bucket being a fifo queue of events to be fired at that time. whether it's worth bothering with the additional complexity is up for discussion.
Sounds like a not-yet-polished version of what the kernel does. http://lwn.net/Articles/156329/ (note I'm not really convinced twisted should implement a similar thing, atleast right now)
----- Original Message ----- From: "Tommi Virtanen" <tv@twistedmatrix.com> To: "Twisted general discussion" <twisted-python@twistedmatrix.com> Sent: Monday, January 02, 2006 4:19 AM Subject: Re: [Twisted-Python] Re: r15451 - Fix test failures under windowsby changing the eventual-send operation to
Paul G wrote:
full ordering/sorting hit on inserts. if you think a little harder, this can be made fairly efficient with a sparse circular list of event buckets, with each bucket being a fifo queue of events to be fired at that time. whether it's worth bothering with the additional complexity is up for discussion.
Sounds like a not-yet-polished version of what the kernel does.
http://lwn.net/Articles/156329/
(note I'm not really convinced twisted should implement a similar thing, atleast right now)
yep, the kernel implementation is another (similar) way to skin the same cat. please note that the kenel implementation makes a certain tradeoff because: 1) it expects most timers to be deleted before expiring 2) it has a bounded jiffies range. in the context of twisted, i'd rather take the hits piecemeal on inserts/deletes with a sparse circular array rather than all at once as with their logarithmic bucket scheme. i have some of this implemented in some scheduling code i wrote a while back, but it'd need some massaging. if there's any interest, i may produce a patch, but i don't want to do the work if it's not gonna get accepted (i'm lazy ;). with that said, the specific issue warner is having could be fixed at the source if the current implementation is deemed sufficient. this can be accomplished by finding a better time source to use under windows and/or implementing a crude version of lagrange timestamps to use as indices. -p
On Sat, 31 Dec 2005 10:57:21 -0800 (PST), Brian Warner <warner@lothar.com> wrote:
Yes it does: order of method call.
Hmm. Does it? The interface documentation is pretty light on guarantees, and that's on purpose: what happens if the user does callLater(0), then sets the system clock back, then does callLater(0) again?
Ah. That's useful to know: I would prefer to use a non-threading-related call to achieve this eventual-send functionality. I'll add a TODO test to check that this promise is being met.
I think that your eventual-send queue should probably be its own event-queuing API. If you have: callLater(0, foo); callLater(0, bar) and you expect ordering between them, something like this is better: callLater(0, lambda : foo(); bar()) or perhaps myRunQueue.put(foo); myRunQueue.put(bar); callLater(0, myRunQueue.activate) You get the idea. That's not to say that stabilizing ordering in the win32 reactor is necessarily bad; but I think we should be careful with specifying overly strict behaviors with respect to the exact ordering that the reactor applies to different invocations of events, whether they're time or network or whatever. There should be some wiggle-room so that faster/fairer approaches can be tried.
participants (4)
-
Brian Warner
-
glyph@divmod.com
-
Paul G
-
Tommi Virtanen