Skip Menu |
Report information
Id: 130716
Status: open
Priority: 0/
Queue: perl6

Owner: Nobody
Requestors: gjb [at] google.com
Cc:
AdminCc:

Severity: (no value)
Tag: (no value)
Platform: (no value)
Patch Status: (no value)
VM: (no value)



Date: Fri, 3 Feb 2017 21:20:12 -0800
To: rakudobug [...] perl.org
From: Geoffrey Broadwell <gjb [...] google.com>
Subject: [CONC] unbounded supply {} + react {} = pseudo-hang
Download (untitled) / with headers
text/plain 519b
See the following gist:


(If you run that at the command line, you'll probably want to pipe it to `head -30` or so; it will output a lot of lines very quickly!)

Essentially it appears that unlike the friendly one-at-a-time behavior of .act, react/whenever will try to exhaust all the emits from an unbounded supply *before* delivering any of them to the whenever code -- which makes it awfully hard to have the whenever tell the supply when to stop.

RT-Send-CC: perl6-compiler [...] perl.org
Download (untitled) / with headers
text/plain 5.5k
On Fri, 03 Feb 2017 21:20:59 -0800, gjb@google.com wrote: Show quoted text
> See the following gist: > > https://gist.github.com/japhb/40772099ed24e20ec2c37c06f434594b > > (If you run that at the command line, you'll probably want to pipe it to > `head -30` or so; it will output a lot of lines very quickly!) > > Essentially it appears that unlike the friendly one-at-a-time behavior of > .act, react/whenever will try to exhaust all the emits from an unbounded > supply *before* delivering any of them to the whenever code -- which makes > it awfully hard to have the whenever tell the supply when to stop.
Firstly, the boring observations: there are two mistakes in the gist. 1) A role is not a closure, so: } does role { method done { $done = True } } Will not behave as you want. 2) In the react example, there is $s1.done, when I presume $s2.done was meant. Even with these corrected, the behavior under consideration still occurs. The deadlock we're seeing here is thanks to the intersection of two individually reasonable things. The first is the general principle that supplies are about taming, not introducing, concurrency. There are, of course, a number of Supply factory methods that will introduce concurrency (Supply.interval, for example), together with a number of supply operators that also will - typically, anything involving time, such as the delay method. Naturally, schedule-on also can. But these are all quite explicitly asking for the concurrency (and all are delegating to something else - a scheduler - to actually provide it). The second, which is in some ways a follow-on from the first, is the actor-like semantics of supply and react blocks. Only one thread may be inside of a given instance of a supply or react block at a time, including any of the whenever blocks inside of it. This has two important consequences: 1) You can be sure your setup logic inside of the supply or react block will complete before any messages are processed. 2) You can be sure that you'll never end up with data races on any of the variables declared inside of your supply or react block because only one message will be processed at a time. This all works out well if the supply being tapped truly *is* an asynchronous source of data - which is what supplies are primarily aimed at. In the case we're considering here, however, it is not. Thanks to the first principle, we don't introduce concurrency, so we tap the supply on the thread running the react block's body. It never hands back control due to the loop inside of it, running straight into the concurrency control mechanism. A one-word fix is to introduce a bit of concurrency explicitly: react { start whenever $s2 -> $n { say "Received $n"; $s2.done if $n >= 5; } } With this, the react block's setup can complete, and then it starts processing the messages. Longer term, a back-pressure model for supplies is something that wants looking in to, designing, and implementing. I put this off on the basis that Rx.Net is plenty useful without one, and RxJava introduced one after its initial release. Taken together, there was no incentive to rush one in. However, we might be able to find a solution in that space for this particular case. That said, back when I was teaching async programming, I always made a point to note that the places where synchrony and asynchrony meet are often sources of trouble. Here, a supply block whose body runs synchronously runs up against a construct (react) and data structure (Supply) whose designs are optimized for dealing with asynchronous data. Reduced to its essence, the code submitted here and the C# code I would show my students to illustrate the problem look strikingly similar: a blocking subscription prevents message processing, leading to a deadlock. It's worth noting that this general problem can *not* be solved through a back-pressure mechanism; it can only solve cases like the one in this ticket where when emit can serve as a preemption point in the case of back-pressure being applied. The consequences of making emit have such semantics, however, will probably run deep once we get into non-toy examples. (For example, will it end up with us declaring `emit` as being like `await` in 6.d where you may be on a different OS thread afterwards if you do it inside of the thread pool?) A perhaps simpler solution space to explore is providing an API that separates the obtaining of a Tap from the starting of processing. That would allow us to run the setup logic to completion. But...then what? Again, it's easy to make this toy example work because there's only one whenever block. But if there are more, then we're just moving the problem, and making it harder to diagnose, because instead of a "where are we deadlocked" backtrace showing the whenever line, it'd instead show...some other location in supply internals. So, a back-pressure model that allows us to round-robin is probably a bit better than this. tl;dr use "start whenever $supply { }" when $supply is going to work synchronously. We should also consider implementing a missing "tap-on" supply operator, so you can also write: whenever $supply.tap-on(ThreadPoolScheduler) { } Or do it at the source: supply { ...sync code here... }.tap-on(ThreadPoolScheduler) A simple implementation would likely be: method tap-on(Scheduler:D $scheduler) { supply { $scheduler.cue: { whenever self { .emit } } } } Making the code as originally submitted work is an interesting problem to ponder, but raises a bunch of non-trivial questions, and should be considered together with various other challenges. Hope this helps, /jnthn
Download (untitled) / with headers
text/plain 566b
On Sat, 04 Feb 2017 07:08:04 -0800, jnthn@jnthn.net wrote: Show quoted text
> A simple implementation would likely be: > > method tap-on(Scheduler:D $scheduler) { > supply { > $scheduler.cue: { whenever self { .emit } } > } > } >
That would also be a wrong implementation, since cue doesn't bring dynamic context along for the ride, which is how a whenever locates its enclosing supply block. Would need to be: method tap-on(Scheduler:D $scheduler) { supply { start whenever self { .emit } } } That'll teach me to prematurely optimize. :-) /jnthn
To: perl6-bugs-followup [...] perl.org
Subject: Re: [perl #130716] [CONC] unbounded supply {} + react {} = pseudo-hang
From: Geoffrey Broadwell via perl6-compiler <perl6-compiler [...] perl.org>
Date: Sun, 5 Feb 2017 11:02:02 -0800
Download (untitled) / with headers
text/plain 9.1k
Download (untitled) / with headers
text/html 10.8k
Responses inline ...

On Sat, Feb 4, 2017 at 7:08 AM, jnthn@jnthn.net via RT <perl6-bugs-followup@perl.org> wrote:
Show quoted text
On Fri, 03 Feb 2017 21:20:59 -0800, gjb@google.com wrote:
> See the following gist:
>
>     https://gist.github.com/japhb/40772099ed24e20ec2c37c06f434594b
>
> (If you run that at the command line, you'll probably want to pipe it to
> `head -30` or so; it will output a lot of lines very quickly!)
>
> Essentially it appears that unlike the friendly one-at-a-time behavior of
> .act, react/whenever will try to exhaust all the emits from an unbounded
> supply *before* delivering any of them to the whenever code -- which makes
> it awfully hard to have the whenever tell the supply when to stop.

Firstly, the boring observations: there are two mistakes in the gist.

1) A role is not a closure, so:
    } does role { method done { $done = True } }
Will not behave as you want.

It took me a minute to realize this was true, because if you move the `my $s2 = make-supply;` from the react section right up under the creation of $s1, it's clear that things go terribly wrong -- it apparently only worked for me because I was only creating one at a time and finishing with one before creating the next.

That said, this raises two questions:

A. How did this work in the first place?  Was the role's reference to $done pointing to a single static slot?

B. Why isn't a role declaration a closure?  I understand that the attributes and methods need to be flattened into the composed class; is this because the contents of the role and the class are inserted into one combined block that can only have one outer lexical context?

Show quoted text
2) In the react example, there is $s1.done, when I presume $s2.done was meant.

Yup, didn't notice that pasto because the gist was essentially a merge of two different cases, and the behavior after merging was the same as before.
 
Show quoted text
Even with these corrected, the behavior under consideration still occurs.

The deadlock we're seeing here is thanks to the intersection of two individually reasonable things.

The first is the general principle that supplies are about taming, not introducing, concurrency. There are, of course, a number of Supply factory methods that will introduce concurrency (Supply.interval, for example), together with a number of supply operators that also will - typically, anything involving time, such as the delay method. Naturally, schedule-on also can. But these are all quite explicitly asking for the concurrency (and all are delegating to something else - a scheduler - to actually provide it).

The second, which is in some ways a follow-on from the first, is the actor-like semantics of supply and react blocks. Only one thread may be inside of a given instance of a supply or react block at a time, including any of the whenever blocks inside of it. This has two important consequences:

1) You can be sure your setup logic inside of the supply or react block will complete before any messages are processed.

2) You can be sure that you'll never end up with data races on any of the variables declared inside of your supply or react block because only one message will be processed at a time.

This all works out well if the supply being tapped truly *is* an asynchronous source of data - which is what supplies are primarily aimed at. In the case we're considering here, however, it is not. Thanks to the first principle, we don't introduce concurrency, so we tap the supply on the thread running the react block's body. It never hands back control due to the loop inside of it, running straight into the concurrency control mechanism.

OK, the above makes sense to me, but why does the .act version work properly then?  When I first read that react {} was supplying actor-like semantics, I assumed that meant it works just like .act -- but it doesn't.  Why not?  What am I missing here?
 
Show quoted text
A one-word fix is to introduce a bit of concurrency explicitly:

react {
    start whenever $s2 -> $n {
        say "Received $n";
        $s2.done if $n >= 5;
    }
}

With this, the react block's setup can complete, and then it starts processing the messages.

Well ... that kinda works.  As I tried this (with a `sleep 2` added at program end) and a few other variants -- using `last` instead of `$s2.done` as recommended in the irclog, using `loop` instead of `until $done`, getting rid of the role application and instead putting `my $done = False; CLOSE $done = True;` inside the supply {} block, etc. -- I found that every variation I tried sometimes worked, and sometimes led to sadness.  For example, it might emit a largish number of times, then stop emitting and just hang (way past the length of the sleep).  The version using `last` and `CLOSE` together would sometimes emit quite a few times before exiting, with the last few emits interspersed with `===SORRY!===` and `last without loop construct`.  I assume the pile of emits before stopping is just a matter of which thread was getting scheduled -- standard concurrency issues.  But the hang and the error make no sense.

With all the things I tried, at this point I'm not even sure which problems were results of my ignorance and which were actual bugs of their own.  What is the *correct and always working* version of this gist?  Note that in the real input-processing code from which this toy example was extracted, it's critical to do cleanup after the supply is stopped, because otherwise the terminal will be stuck in raw input mode ... and that cleanup depends on restoring state saved just before the supply is set up.

Show quoted text
Longer term, a back-pressure model for supplies is something that wants looking in to, designing, and implementing. I put this off on the basis that Rx.Net is plenty useful without one, and RxJava introduced one after its initial release. Taken together, there was no incentive to rush one in. However, we might be able to find a solution in that space for this particular case.

That said, back when I was teaching async programming, I always made a point to note that the places where synchrony and asynchrony meet are often sources of trouble. Here, a supply block whose body runs synchronously runs up against a construct (react) and data structure (Supply) whose designs are optimized for dealing with asynchronous data. Reduced to its essence, the code submitted here and the C# code I would show my students to illustrate the problem look strikingly similar: a blocking subscription prevents message processing, leading to a deadlock.

It's worth noting that this general problem can *not* be solved through a back-pressure mechanism; it can only solve cases like the one in this ticket where when emit can serve as a preemption point in the case of back-pressure being applied. The consequences of making emit have such semantics, however, will probably run deep once we get into non-toy examples. (For example, will it end up with us declaring `emit` as being like `await` in 6.d where you may be on a different OS thread afterwards if you do it inside of the thread pool?)

I can understand that problem -- though it does lead me to wonder what exactly .act() used on the receiving side is doing now that makes it more amenable to this use case.
 
Show quoted text
A perhaps simpler solution space to explore is providing an API that separates the obtaining of a Tap from the starting of processing. That would allow us to run the setup logic to completion. But...then what? Again, it's easy to make this toy example work because there's only one whenever block. But if there are more, then we're just moving the problem, and making it harder to diagnose, because instead of a "where are we deadlocked" backtrace showing the whenever line, it'd instead show...some other location in supply internals. So, a back-pressure model that allows us to round-robin is probably a bit better than this.

tl;dr use "start whenever $supply { }" when $supply is going to work synchronously.

I thought the initial point of Supply was to address a few fundamental limitations of Channel, one of which was to not force so much thread switching just to send a stream of values through.  My understanding was that (in the case of not explicitly starting a new thread for the receiver), each value emitted would simply travel through a tree of taps depth first before emitting the next value.  In other words, `emit` had coroutine status similar to `take`.  And with .act() on the taps, that seems to match my mental model.  So why doesn't that work with react {}?

Show quoted text
We should also consider implementing a missing "tap-on" supply operator, so you can also write:

whenever $supply.tap-on(ThreadPoolScheduler) { }

Or do it at the source:

supply {
    ...sync code here...
}.tap-on(ThreadPoolScheduler)

A simple implementation would likely be:

method tap-on(Scheduler:D $scheduler) {
    supply {
        $scheduler.cue: { whenever self { .emit } }
    }
}

Making the code as originally submitted work is an interesting problem to ponder, but raises a bunch of non-trivial questions, and should be considered together with various other challenges.

Hope this helps,

/jnthn

RT-Send-CC: perl6-compiler [...] perl.org
On Sun, 05 Feb 2017 16:14:15 -0800, gjb@google.com wrote: Show quoted text
> > 1) A role is not a closure, so: > > } does role { method done { $done = True } } > > Will not behave as you want. > >
> > It took me a minute to realize this was true, because if you move the > `my > $s2 = make-supply;` from the react section right up under the creation > of > $s1, it's clear that things go terribly wrong -- it apparently only > worked > for me because I was only creating one at a time and finishing with > one > before creating the next. > > That said, this raises two questions: > > A. How did this work in the first place? Was the role's reference to > $done > pointing to a single static slot? >
Yes. Show quoted text
> B. Why isn't a role declaration a closure? I understand that the > attributes and methods need to be flattened into the composed class; > is > this because the contents of the role and the class are inserted into > one > combined block that can only have one outer lexical context? >
It's because classes and roles are constructed at compile time; by runtime we're just referencing the one thing that was created at compile time. So, the role meta-object points to the single static instance of the role body block, and runs that every time. (The role body does run at runtime since this is a runtime mixin. However, even those get interned. Even if they didn't, we'd still be in the same situation, however, since there's a single static instance of the role body block.) Show quoted text
> OK, the above makes sense to me, but why does the .act version work > properly then? When I first read that react {} was supplying actor- > like > semantics, I assumed that meant it works just like .act -- but it > doesn't. > Why not? What am I missing here? >
The `act` version does have a problem too, in a sense. `act` returns a Tap object, and calling `.close` on that would be the correct way to close the supply being tapped. However, since that supply works synchronously, the call to `act` gets control and the `Tap` object doesn't become available. Really, `.act` just means `.serialize.sanitize.tap`. However, a `supply` block cannot emit multiple concurrent messages, so is already serial. It's also sanitary (follows the supply protocol), so the behavior in this case really is just `.tap`. So, the "actor-like" behavior of `.act` just means that there will never be concurrent calls to any of the blocks passed to that particular `.act` call. The `react` and `supply` constructs allow establishing of richer actors. The one-at-a-time applies to all of the whenever blocks. So: my $i = 0; $s1.act: { $i++ } $s2.act: { $i++ } Is a data race on $i, but: my $i = 0; react { whenever $s1 { $i++ } whenever $s2 { $i++ } } Is not. The problem you're running in to is that we also promise that: my $i = 0; react { whenever $s1 { $i++ } $i++; whenever $s2 { $i++ } } Will not be a data race - that is, the code inside of the main body of the react block holds the "lock" until it completes and all subscriptions and state are set up. But if $s1 or $s2 here do not give control back upon being tapped, then the react block's main body never completes and releases the lock either, and so it's impossible to process messages. Show quoted text
> Well ... that kinda works. As I tried this (with a `sleep 2` added at > program end) and a few other variants -- using `last` instead of > `$s2.done` > as recommended in the irclog, using `loop` instead of `until $done`, > getting rid of the role application and instead putting `my $done = > False; > CLOSE $done = True;` inside the supply {} block, etc. -- I found that > every > variation I tried sometimes worked, and sometimes led to sadness. For > example, it might emit a largish number of times, then stop emitting > and > just hang (way past the length of the sleep). The version using > `last` and > `CLOSE` together would sometimes emit quite a few times before > exiting, > with the last few emits interspersed with `===SORRY!===` and `last > without > loop construct`. I assume the pile of emits before stopping is just a > matter of which thread was getting scheduled -- standard concurrency > issues. But the hang and the error make no sense. >
Turns out the support for `last` inside of whenever blocks didn't get merged yet (it's in a PR, which I've looked at today, but seems to have some issues that need looking over beforehand). So that's the issue with `last`. Even if it was merged, there'd still be trouble. The real difficulty here is down to react/supply so far making the assumption that they are dealing with supplies that will deliver data asynchronously, and that will not block upon subscription. When the tap handle from subscription is not handed back before messages are emitted, there's no way for it to close the Supply. I'm still considering various ways we might be able to address this limitation, but it'll need some thinking time. Show quoted text
> With all the things I tried, at this point I'm not even sure which > problems > were results of my ignorance and which were actual bugs of their own. > What > is the *correct and always working* version of this gist? Note that > in the > real input-processing code from which this toy example was extracted, > it's > critical to do cleanup after the supply is stopped, because otherwise > the > terminal will be stuck in raw input mode ... and that cleanup depends > on > restoring state saved just before the supply is set up. >
I'd suggest something like this: sub make-supply() { my $s = Supplier::Preserving.new; my $done = False; start { until $done { $s.emit: ++$ } } $s.Supply.on-close({ say 'closing'; $done = True }) } say "\nUSING react"; my $s2 = make-supply; react { whenever $s2 -> $n { say "Received $n"; done if $n >= 5; } } Show quoted text
> I thought the initial point of Supply was to address a few fundamental > limitations of Channel, one of which was to not force so much thread > switching just to send a stream of values through.
It's a bit deeper than that. Supply and Channel are for different processing models. Channels are for when you want a queue that a producer can place things in to quickly, without blocking on whatever will process them. Something else receives and processes the messages. A channel is typically used to *introduce* parallel processing, and has the concurrency control in place to cope with that being 1:N, M:1, or N:M. Supplies were introduced to provide for the reactive paradigm, where values are being produced asynchronously and we wish to react to them in various ways and compose those various reactors. These values may come from a range of sources and arrive concurrently. Supplies are thus about taming/controlling concurrency. So, supplies don't replace channels; they solve a different set of problems that channels would not be suited to. It is true that supplies will process messages on the producing thread unless you explicitly say otherwise. Note that in the solution above, while we introduce a worker with the `start` block, all the `whenever` blocks inside of the `react` will be run on the thread of that `start` block. The thread doing the react will just wait for the react to be done (or, in 6.d.PREVIEW, if the react is in the thread pool, it will return to thread to the pool to get on with other work). Show quoted text
> My understanding was > that (in the case of not explicitly starting a new thread for the > receiver), each value emitted would simply travel through a tree of > taps depth first before emitting the next value. In other words, `emit` > had coroutine status similar to `take`.
It essentially does, but in the reactive space the yield just becomes a call (to process the reaction), and the resume is the return from that call. In common they have that the call is "abstract" (that is, with `take` the code is abstracted from a particular consumer, and with `emit` from a particular reactor). Show quoted text
> And with .act() on the taps, that > seems to match my mental model. So why doesn't that work with react > {}?
Because, as hopefully clarified above, react is trying to perform more concurrency control than act. Hope this helps, and I'll keep the issue under consideration.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org