[Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted
Hi Folks: I don't know what to file this under but here goes: Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work). Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting I recently modified the stackless.py library to support yet another new concurrency feature: join patterns. Well I think of my version as a sawed-off version of join patterns. Join patterns are a synchronization and message passing construct. The closest thing to a join pattern in Twisted is a deferred list. Stackless has nothing of the sort. The Santa Claus Problem is a notorious problem in concurrency (http://www.youtube.com/watch?v=pqO6tKN2lc4). I have come up with a relatively short solution. I think one would be hard pressed to come up with a shorter solution in Python. My desire was to compete with Simon Peyton Jones Haskell version in "Beautiful Code." The full solution is here: http://andrewfr.wordpress.com/2011/11/30/the-santa-claus-problem-with-join-p.... The nucleus is: def santa(reindeer, elves): joinObject = stackless.join().addPattern([ch for _, ch, _ in reindeer]).\ addPattern([ch for _, ch, _ in elves],3) reindeerPattern, elfPattern = joinObject.patterns while True: pattern = joinObject.join() if reindeerPattern.ready(): print "*** REINDEER GET PRIORITY ***" reindeerPattern.join() pattern = reindeerPattern if pattern is reindeerPattern: harness(reindeerPattern) deliveryToys(reindeerPattern) unharness(reindeerPattern) elif pattern is elfPattern: consultWithSanta(elfPattern) stopTwisted() In this solution I use Twisted to control the timer (I use the blockOn technique that Christopher Armstrong first used). def tick(seconds): tickCh = stackless.channel() reactor.callLater(seconds, tickCh.send, None) tickCh.receive() However I could just as easily make reindeer and elves web services or RestFull interfaces. I am still working on the Join Pattern API. Also it has also been a goal of mine to write a stacklessreactor to better integrate Stackless with the Twisted Reactor. Cheers, Andrew
reindeers = dict( rudolf = defer.Deferred() , .... ) arrivedElvs = [] threeElvsArrived = defer.Deferred() def onReindeerArrive(who): reindeer[who].callback(True) def onElvArrive(elv): global arrivedElvs if len(arrivedElvs) <= 1: arrivedElvs.append(elv) elif len(arrivedElvs) == 2: arrivedElvs.append(elv) threeElvsArrived.callback(arrivedElvs) else: pass defer.DeferredList(reindeers.values()).addCallback(lambda _ : True).addCallback(playWithReindeers) elvsArrived.addCallback(playWithElvs) Above is my pseudo code. It's not clear if Santa will respond to only to one of these two events. If so, you may block the other when one get fired. I think Twisted's approach is pretty elegant. On Sun, Dec 11, 2011 at 07:05:54PM -0800, Andrew Francis wrote:
Hi Folks:
I don't know what to file this under but here goes:
Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work). Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting
I recently modified the stackless.py library to support yet another new concurrency feature: join patterns. Well I think of my version as a sawed-off version of join patterns. Join patterns are a synchronization and message passing construct. The closest thing to a join pattern in Twisted is a deferred list. Stackless has nothing of the sort.
The Santa Claus Problem is a notorious problem in concurrency (http://www.youtube.com/watch?v=pqO6tKN2lc4). I have come up with a relatively short solution. I think one would be hard pressed to come up with a shorter solution in Python. My desire was to compete with Simon Peyton Jones Haskell version in "Beautiful Code." The full solution is here: http://andrewfr.wordpress.com/2011/11/30/the-santa-claus-problem-with-join-p.... The nucleus is: def santa(reindeer, elves): joinObject = stackless.join().addPattern([ch for _, ch, _ in reindeer]).\ addPattern([ch for _, ch, _ in elves],3)
reindeerPattern, elfPattern = joinObject.patterns
while True: pattern = joinObject.join() if reindeerPattern.ready(): print "*** REINDEER GET PRIORITY ***" reindeerPattern.join() pattern = reindeerPattern if pattern is reindeerPattern: harness(reindeerPattern) deliveryToys(reindeerPattern) unharness(reindeerPattern) elif pattern is elfPattern: consultWithSanta(elfPattern)
stopTwisted()
In this solution I use Twisted to control the timer (I use the blockOn technique that Christopher Armstrong first used).
def tick(seconds): tickCh = stackless.channel() reactor.callLater(seconds, tickCh.send, None) tickCh.receive()
However I could just as easily make reindeer and elves web services or RestFull interfaces. I am still working on the Join Pattern API. Also it has also been a goal of mine to write a stacklessreactor to better integrate Stackless with the Twisted Reactor.
Cheers, Andrew
_______________________________________________ Twisted-Python mailing list Twisted-Python@twistedmatrix.com http://twistedmatrix.com/cgi-bin/mailman/listinfo/twisted-python
From: shhgs <shhgs.efhilt@gmail.com> To: Andrew Francis <andrewfr_ice@yahoo.com>; Twisted general discussion <twisted-python@twistedmatrix.com> Sent: Monday, December 12, 2011 11:15 PM Subject: Re: [Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted Hi Shhgs:
defer.DeferredList(reindeers.values()).addCallback(lambda _ : True).addCallback(playWithReindeers) elvsArrived.addCallback(playWithElvs)
Above is my pseudo code. It's not clear if Santa will respond to only to one of these two events. If so, you may block the other when one get fired. I think Twisted's approach is pretty elegant.
Cool! Okay, I understand your approach: you count the elves and then the right number arrive, you wake Santa. Twisted does have one important ingredient for solving Santa Claus: a join mechanism in the form of a deferred list. Also the non-preemptive nature of the reactor guards against a lot of the problems in another solution. In this regard, I think a Twisted solution may be more efficient than most Python mechanisms out there. The main problem I see with a pure Twisted solution is that it really can't impose the priority rule. Perhaps the way the reactor works makes priority somewhat moot. Let's assume we could put timestamps on elves and reindeer arrival times (or force reindeer and elves to arrival at specific times). Now at time T, there are eight reindeer and two elves ready. At T+1, an additional reindeer and elf are ready (their timestamps are the same, timer resolution notwithstanding). However the Twisted reactor will serialise the events and trigger the callback. For argument, let us pretend the elvesArrive callback is activated and that wakes Santa. Santa consults with the elves. The problem is that all nine reindeer were ready and the priority rule is broken. I am not sure, from inside the callback, one could check to see if nine reindeer were indeed ready. Also I suspect once you actually coded out the solution, the ancillary things (looping, callLater) would make the code more difficult to read. However that is minor compared to aforementioned problem. Cheers, Andrew ________________________________ From: shhgs <shhgs.efhilt@gmail.com> To: Andrew Francis <andrewfr_ice@yahoo.com>; Twisted general discussion <twisted-python@twistedmatrix.com> Sent: Monday, December 12, 2011 11:15 PM Subject: Re: [Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted reindeers = dict( rudolf = defer.Deferred() , .... ) arrivedElvs = [] threeElvsArrived = defer.Deferred() def onReindeerArrive(who): reindeer[who].callback(True) def onElvArrive(elv): global arrivedElvs if len(arrivedElvs) <= 1: arrivedElvs.append(elv) elif len(arrivedElvs) == 2: arrivedElvs.append(elv) threeElvsArrived.callback(arrivedElvs) else: pass defer.DeferredList(reindeers.values()).addCallback(lambda _ : True).addCallback(playWithReindeers) elvsArrived.addCallback(playWithElvs) Above is my pseudo code. It's not clear if Santa will respond to only to one of these two events. If so, you may block the other when one get fired. I think Twisted's approach is pretty elegant. On Sun, Dec 11, 2011 at 07:05:54PM -0800, Andrew Francis wrote:
Hi Folks:
I don't know what to file this under but here goes:
Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work). Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting
I recently modified the stackless.py library to support yet another new concurrency feature: join patterns. Well I think of my version as a sawed-off version of join patterns. Join patterns are a synchronization and message passing construct. The closest thing to a join pattern in Twisted is a deferred list. Stackless has nothing of the sort.
The Santa Claus Problem is a notorious problem in concurrency (http://www.youtube.com/watch?v=pqO6tKN2lc4). I have come up with a relatively short solution. I think one would be hard pressed to come up with a shorter solution in Python. My desire was to compete with Simon Peyton Jones Haskell version in "Beautiful Code." The full solution is here: http://andrewfr.wordpress.com/2011/11/30/the-santa-claus-problem-with-join-p.... The nucleus is: def santa(reindeer, elves): joinObject =
addPattern([ch for _, ch, _ in elves],3)
reindeerPattern, elfPattern = joinObject.patterns
while True: pattern = joinObject.join() if reindeerPattern.ready(): print "*** REINDEER GET PRIORITY ***" reindeerPattern.join() pattern = reindeerPattern if
stackless.join().addPattern([ch for _, ch, _ in reindeer]).\ pattern is reindeerPattern:
harness(reindeerPattern) deliveryToys(reindeerPattern) unharness(reindeerPattern) elif pattern is elfPattern: consultWithSanta(elfPattern)
stopTwisted()
In this solution I use Twisted to control the timer (I use the blockOn technique that Christopher Armstrong first used).
def tick(seconds): tickCh = stackless.channel() reactor.callLater(seconds, tickCh.send, None) tickCh.receive()
However I could just as easily make reindeer and elves web services or RestFull interfaces. I am still working on the Join Pattern API. Also it has also been a goal of mine to write a stacklessreactor to better integrate Stackless with the Twisted Reactor.
Cheers, Andrew
_______________________________________________ Twisted-Python mailing list Twisted-Python@twistedmatrix.com http://twistedmatrix.com/cgi-bin/mailman/listinfo/twisted-python
On Dec 13, 2011, at 2:04 PM, Andrew Francis wrote:
Now at time T, there are eight reindeer and two elves ready. At T+1, an additional reindeer and elf are ready (their timestamps are the same, timer resolution notwithstanding). However the Twisted reactor will serialise the events and trigger the callback. For argument, let us pretend the elvesArrive callback is activated and that wakes Santa. Santa consults with the elves. The problem is that all nine reindeer were ready and the priority rule is broken. I am not sure, from inside the callback, one could check to see if nine reindeer were indeed ready.
This strikes me as a problem with the way that quantum physics works more than the way that Twisted's reactor works :). Broadly speaking, no two events can happen at the exact same time; even if they did, relativity says you wouldn't be able to tell if they happened at the exact same time unless they also happened to be exactly the same distance away from you. (But then "you" would have to be exactly one atom big, which is a pretty demanding size to build a sensor.) Even if it were possible in reality, once a network gets involved, you have a bunch of additional bits of technology serializing everything. If your computer has one ethernet card, the reindeer and the elves have to report their readiness either in separate ethernet frames in one order or the other, or in one order or another within the same ethernet frame. (If it has two ethernet cards, you still only have one PCI bus, et cetera.) Despite the fundamentally sequential nature of reality, Twisted reactor's scheduling mechanism does leave some things to be desired; the quantum time-slice of Twisted is effectively one reactor iteration, and there aren't really any tools for working with those. There's some latency between becoming aware of some work that needs to be done (select(), or your chosen multiplexor, returning) and actually doing the work (calling doRead, doWrite, or your timed event), but you don't get to decide on priorities once Twisted's aware of the work; they're executed in a quasi-arbitrary order. Ultimately however, the order of the work will be arbitrary; if it's not influenced by the vagaries of Twisted's scheduler, it will be influenced by something in the kernel scheduler that you don't understand or can't control, or in the IP stack, or in a switch on your network, or in your hosting provider's firewall configuration, or something on a client machine that you truly have no influence over at all. Having something give priority to an event that occurs at "the same" time given all of these potential sources of interference is basically pointless. The only reason that the Santa problem, expressed as a thread-synchronization problem, has to deal with "simultaneous" arrival of 9 reindeer and 3 elves is a quirk of thread scheduling: the Santa thread can be ready to run but not running. When the final reindeer arrives, a final elf may arrive before the scheduler decides it's time to give Santa a chance to run, and then Santa has the opportunity to make the choice between the two. In an event-driven system, this state doesn't naturally exist: when you call Deferred.callback(), the callback runs the relevant application code immediately. Even in a preemptively threaded system though, the notion of simultaneity is pretty arbitrary; you don't get much control over how long Santa will be left in the ready-to-run-but-not-running state. If you really care about Santa giving priority to the reindeer, then the system requires another input: how long should Santa sleep after the elves become ready, before deciding to go with the elves rather than the reindeer? Effectively in a threaded system Santa is sleeping, just for a very small and not configurable amount of time. -glyph
On 12/14/2011 05:45 AM, Glyph wrote:
On Dec 13, 2011, at 2:04 PM, Andrew Francis wrote:
Now at time T, there are eight reindeer and two elves ready. At T+1, an additional reindeer and elf are ready (their timestamps are the same, timer resolution notwithstanding). However the Twisted reactor will serialise the events and trigger the callback. For argument, let us pretend the elvesArrive callback is activated and that wakes Santa. Santa consults with the elves. The problem is that all nine reindeer were ready and the priority rule is broken. I am not sure, from inside the callback, one could check to see if nine reindeer were indeed ready.
This strikes me as a problem with the way that quantum physics works more than the way that Twisted's reactor works :). Broadly speaking, no two events can happen at the /exact/ same time; even if they did, relativity says you wouldn't be able to /tell/ if they happened at the exact same time unless they also happened to be exactly the same distance away from you. (But then "you" would have to be exactly one atom big, which is a pretty demanding size to build a sensor.) [...] Ultimately however, the order of the work /will/ be arbitrary; if it's not influenced by the vagaries of Twisted's scheduler, it will be influenced by something in the kernel scheduler that you don't understand or can't control, or in the IP stack, or in a switch on your network, or in your hosting provider's firewall configuration, or something on a client machine that you truly have no influence over at all. Having something give priority to an event that occurs at "the same" time given all of these potential sources of interference is basically pointless.
Isn't that what logical clocks, using e.g. Lamport timestamps are for? What can be done is letting the events happen, wait for another logical tick, possibly triggered by a timeout to prevent starvation, looking at the events that have been collected and identified, but not processed yet, treating a certain maximum N of logical ticks as "simultaneous" and then decide on how to prioritize processing, based on arbitrary rules you choose. regards, Johann
participants (4)
-
Andrew Francis -
Glyph -
Johann Borck -
shhgs