Re: Sequential bias in S04 (and Perl6 in general)
Springing out of the ashes (and a job where I have to write Java) for my first post in years: On Fri, 04 Jan 2008 13:13:11 -0800, Dave Whipp [EMAIL PROTECTED] wrote: I agree that adding a parallel forall (and similar statements) via a pragma will be easy if the appropriate underlying machinery is there, so maybe I can live with the bias in S04 -- perhaps rename it to Sequential Blocks and Statements. Anywhere that we guarantee sequential behavior, we pretty much rule out concurrency. But if we maximize the number of places where we are explicitly unordered then we also maximize the number of places where implicit concurrency can be added later. From that perspective, it's unfortunate a Cfor loop always iterates arrays in the order of their indices. I wouldn't agree with that at all. I think of arrays as ordered constructs, so I'd want the default iteration over my array to happen in the order of the indices. I wouldn't have a problem with having the ability for Cfor to iterate over a bag or some other inherently unordered, unsorted container in arbitrary possibly-parallel order though. Possibly by default, if the compiler can be satisfied that the closure's not got any unpleasant side effects to interfere with parallel execution. I think you're leaning too far towards concurrency in attempting to address the perceived bias. A lot of the time, the compiler's not going to be able to prove that it's safe to autothread a given closure because it might have side effects. If we were talking about Haskell or some other language which is ordinarily pure, things would be different. Under these circumstances, I would much rather have to explicitly say that I want parallel execution - provided that the ability to do it is there and it's easy to get at and behaves in a sensible manner (naturally this lets you parallelise things the compiler isn't sure are safe to parallelise due to possible side effects. That's fine, since you know which side effects are okay to do that to in your program). Matthew
Re: Sequential bias in S04 (and Perl6 in general)
Matthew Walton wrote: I wouldn't agree with that at all. I think of arrays as ordered constructs, so I'd want the default iteration over my array to happen in the order of the indices. I guess that depends on whether you think of the array as a list or as a ram. I know that a group at microsoft added a ParallelArray datatype (ftp://ftp.research.microsoft.com/pub/tr/TR-2005-184.pdf) to C# as a way to distinguish the intent (they speed up data-parallel code by compiling it down to your GPU/graphics card). Perl6, being an operator-oriented language, associates the distinction with the operators rather than with the datatype. This is probably a better approach, but it does mean that you need an operator whenever you want to treat the array as data-parallel. (BTW, data-parallel arrays differ from bags in that they have an ordered index that is preserved across unordered operations) I think you're leaning too far towards concurrency in attempting to address the perceived bias. Probably true ... though I think that the bias is real, it's just a question of if its a good-bias or a bad-bias. Under these circumstances, I would much rather have to explicitly say that I want parallel execution - provided that the ability to do it is there and it's easy to get at and behaves in a sensible manner (naturally this lets you parallelise things the compiler isn't sure are safe to parallelise due to possible side effects. That's fine, since you know which side effects are okay to do that to in your program). Of course, it's not necessarily true that you know that something is safe -- often you think it's safe but then you get an intermittent failure at runtime,. I would love to be able to tell the compiler I think this is safe and have it tell me you're wrong as a compile-time error (this is one of the things that an explicit type system is good for). But perhaps Perl is too dynamic a language for that.
Re: Sequential bias in S04 (and Perl6 in general)
On Fri, 2008-01-11 at 10:34 -0800, Dave Whipp wrote: Matthew Walton wrote: I wouldn't agree with that at all. I think of arrays as ordered constructs, so I'd want the default iteration over my array to happen in the order of the indices. I guess that depends on whether you think of the array as a list or as a ram. I know that a group at microsoft added a ParallelArray datatype (ftp://ftp.research.microsoft.com/pub/tr/TR-2005-184.pdf) to C# as a way to distinguish the intent (they speed up data-parallel code by compiling it down to your GPU/graphics card). Perl6, being an operator-oriented language, associates the distinction with the operators rather than with the datatype. This is probably a better approach, but it does mean that you need an operator whenever you want to treat the array as data-parallel. (BTW, data-parallel arrays differ from bags in that they have an ordered index that is preserved across unordered operations) Good point, a parallel operation over a list would let you preserve ordering but still benefit from concurrency with operations where iterating in order is irrelevant. Which, come to think of it, covers quite a lot of cases. Of course, it's not necessarily true that you know that something is safe -- often you think it's safe but then you get an intermittent failure at runtime,. I would love to be able to tell the compiler I think this is safe and have it tell me you're wrong as a compile-time error (this is one of the things that an explicit type system is good for). But perhaps Perl is too dynamic a language for that. Well, I was thinking with 'knowing' that something was safe that you'd figured out that it was free of side effects by studying the behaviour of everything you use within the relevant routines... ...in the real world, you need the compiler to be able to do some of that for you I guess. And Perl 6's optionally explicit type system might be able to express that sort of thing. signature.asc Description: This is a digitally signed message part
Re: Sequential bias in S04 (and Perl6 in general)
Joe Gottman wrote: On the other hand, this being Perl, I do believe it should be easy to specify the concurrent case. I think that a forall keyword (and a givenall keyword corresponding to given) would be a good idea. These would not be quite parallel to for and given because there would be some subtle differences arising from the concurrent processing. For instance, forall probably should not be used with last, because last should stop subsequent iterations and the subsequent iterations could already have occurred when it is called. Similarly, givenall should not be used with continue, because the next case might already have been checked when continue is called. I don't think that there's need for a 'forall' keyword. Note that Perl 6 has both Lists and Bags, the difference being that a List is ordered while a Bag isn't. So what happens when you feed a Bag into a for statement? Conceptually, you'd expect to get evaluation across its members with no promises concerning the order of evaluation. Likewise, I wonder if there might be a more general way to handle the 'givenall' concept. Say, by marking a block as being concurrent (i.e., parallel) in nature rather than sequential (i.e., series). That is, you normally evaluate a block's statements in order from the first to the last; marking the block as concurrent would tell the parser that the order of evaluation within this block isn't important. If a block of when statements is parallelized in this manner, you get the effect of the proposed 'givenall' keyword without the inherent restrictions that requiring the keyword would impose. -- Jonathan Dataweaver Lang
Re: Sequential bias in S04 (and Perl6 in general)
On Jan 4, 2008 9:18 AM, Jonathan Lang [EMAIL PROTECTED] wrote: Joe Gottman wrote: On the other hand, this being Perl, I do believe it should be easy to specify the concurrent case. I think that a forall keyword (and a givenall keyword corresponding to given) would be a good idea. These would not be quite parallel to for and given because there would be some subtle differences arising from the concurrent processing. For instance, forall probably should not be used with last, because last should stop subsequent iterations and the subsequent iterations could already have occurred when it is called. Similarly, givenall should not be used with continue, because the next case might already have been checked when continue is called. I don't think that there's need for a 'forall' keyword. Note that Perl 6 has both Lists and Bags, the difference being that a List is ordered while a Bag isn't. So what happens when you feed a Bag into a for statement? Conceptually, you'd expect to get evaluation across its members with no promises concerning the order of evaluation. forall was about concurrency, not order of evaluation. There is a difference between running in an arbitrary order serially and running in parallel. for %bag { .say; } If the bag had elements hello, world, I think printing: helworld lo Would definitely count as violating the principle of least surprise. Luke
Re: Sequential bias in S04 (and Perl6 in general)
Luke Palmer wrote: forall was about concurrency, not order of evaluation. There is a difference between running in an arbitrary order serially and running in parallel. for %bag { .say; } If the bag had elements hello, world, I think printing: helworld lo Would definitely count as violating the principle of least surprise. For the specific case of Csay, I think that its implementation should probably be is critical -- The Csay method is designed for simple user messages, and atomicity is probably as useful as the auto-newline for its intended usage. But your general message still stands: concurrency can surprise if not handled properly. Just thinking out load, perhaps one could say that the following constructs are broadly equivalent: * for %bag { .say }; * forall %bag { is locally_critical; .say }; (lets assume for now that is locally_critical is like is critical but protects only against child-threads of the ::OUTER scope) Now lets change the definition of curlies such that they always imply this modified is locally_critical trait. Now, the following would be equivalent: * for %bag { .say }; * forall %bag { isnt locally_critical; .say }; From here I'll just make one more proposal: a new form of curley: * for %bag { .say }; // unordered sequential (locally_critical) * for %bag {{ .say }}; // unordered concurrent (not locally_critical) With these modified forms of braces it becomes much easier to define safe concurrent control structures: the default curlies force the additional safety yet there's a simple alternative that increases concurrency without requiring a new statement (but one would still need a special form of splat operator to morph a sequential container for unordered iteration -- so maybe the general unordered forall statement would still be useful)
Re: Sequential bias in S04 (and Perl6 in general)
Am I the only one having bad flashbacks to Occam, here? (Transputing Will Change Everything!) My $0.02, FWIW: Concurrency is surprising. Humans don't think that way. And programs aren't written that way - any program represented as a byte stream is inherently sequential in nature. Where the system can detect opportunities for parallel execution, great, but you have to be careful. Automatic concurrency should only happen when it doesn't change the results at all (apart from making them appear faster). When I want things to be explicitly parallel in a way that can interfere with the apparent flow of execution, that should be a Big Red Blinking Border around the code, not something subtle like forall instead of foreach or doubled curlies.
Re: Sequential bias in S04 (and Perl6 in general)
Mark J. Reed wrote: Am I the only one having bad flashbacks to Occam, here? (Transputing Will Change Everything!) My $0.02, FWIW: Concurrency is surprising. Humans don't think that way. And programs aren't written that way - any program represented as a byte stream is inherently sequential in nature. ... No, you're not the only person thinking Occam ... though I should point out that none of my suggestions are par blocks -- a par block made every statement within the block execute in parallel with the other statements in that block (much like a Verilog fork/join pair). I disagree with the idea that humans don't think concurrently (though more often they think in terms of data dependencies). If I ask someone to boil a kettle + make a cup of tea, and open a can of dogfood to feed the dog, they'd probably sequence the operations such that the kettle comes to the boil while they're feeding the dog ... they'll probably put teabags in the teacups concurrently, too. If you get a group of people together to achieve some goal (e.g. restore an old building) then the first thing they'll do is to partition the work so that team members can work in parallel. The fact that programs aren't written that way is something that I think needs to change. Though, if done right, then things probably don't need to change too much. A program is not a simple byte stream: it's a random-access array. Multiple cores imply multiple physical program counters. If we assume that the core count will double every 18 months, then three years from now we'll be seeing 32-core machines quite regularly. I wouldn't be surprised to see this grow even faster (Moore's Law doesn't apply to architectural shifts).
Re: Sequential bias in S04 (and Perl6 in general)
I disagree with the idea that humans don't think concurrently (though more often they think in terms of data dependencies). I think this is more analogous to event based programming rather than parallel programming. Event based and parallel based have some similarities but the are fundamentally different. Humans typically interact with events and only occasionally are able to walk and chew gum at the same time. Though not fully specified, Perl 6 will have as all the tools necessary to make event driven programs - but there isn't a way to do so automatically. It will take work. I'd argue the same is true for parallel. Paul
Re: Sequential bias in S04 (and Perl6 in general)
I (impersonally) believe that hyper context is the right solution to this because context can propagate to where it needs to dynamically. As for the fact that it's not the default list context for for, that could easily be changed with a pragma. Maybe that could even be the default someday, but we have to educate people to think about hyper first. As for the other part of the proposal, a parallel smartmatch would need new comb syntax for the compound pattern--I wouldn't overload given/when for that. Or maybe just make a way to attach a mapreduce action to any leg of a junction or hyperoperator. In any case, we need to make sure it's easy to place such a parallel comb of matchers at the pointy end of a feed, and if the source of the feed is also executing in parallel, make sure the feed can be optimized to a full crossbar based on packet destination. (And just as in the case of optimizing given/when to a jump table, this also implies that smartmatching must be assymetrical, not symmetrical. It's just the jump in this case is a packet routing rather than program counter routing.) It's also possible that we should discourage syntactic parallel matching in favor of parallel polymorphic dispatch, given that signatures can also express patterns. Might need to tweak the current multiple dispatch rules a bit though if we want dispatch ambiguity to express nondeterminism. In any case, real mapreduce situations are often generated dynamically, and cannot easily be expressed in a syntactically fixed set of options. And overriding all of this is how to hide all this cool stuff so that it A) doesn't drive newbies mad, but B) is right there at their fingertips when they need it, and C) is easily recognizable as magic so that when they see it in other people's code they'll understand that they don't understand. That's why hyper context is an explicit feature in standard Perl 6. But then, so is the ability to add a pragma like: use hyper; It's really, really easy to misdesign a computer language by overemphasizing one particular design dimension to the detriment of others. With Perl 6 we're trying to make the opposite mistake. Larry
Re: Sequential bias in S04 (and Perl6 in general)
Joe Gottman schreef: if code that should be processed concurrently is instead processed sequentially, the results will be correct Not if parallel sampling of happening stuffs is involved. All of your thousands of temperature sensors in your nuclear factory, all running the same code, should not wait for any of their neighbours. They should interrupt their supervisor if something interesting was detected, by setting a bit in some register, so the supervisor can serially check any interrupts. But even the supervisor could be multiple devices doing that concurrently. though the program will take longer to run than necessary. Not if there is only 1 processor, because then the overhead of interleaving processes will make the concurrent processing take longer. -- Groet, Ruud
Re: Sequential bias in S04 (and Perl6 in general)
Larry Wall wrote: It's really, really easy to misdesign a computer language by overemphasizing one particular design dimension to the detriment of others. I agree that adding a parallel forall (and similar statements) via a pragma will be easy if the appropriate underlying machinery is there, so maybe I can live with the bias in S04 -- perhaps rename it to Sequential Blocks and Statements. Anywhere that we guarantee sequential behavior, we pretty much rule out concurrency. But if we maximize the number of places where we are explicitly unordered then we also maximize the number of places where implicit concurrency can be added later. From that perspective, it's unfortunate a Cfor loop always iterates arrays in the order of their indices. As I see it, parallelism is easy: it's synchronization that's hard. Specifically, it's hard to get exactly the right scoping of constraints. And it seems to me that hyper addresses the parallelization aspect but not synchronization. Concurrency.pod (S17) defines a few basic mechanisms, but it's not obvious that they're really easy, or sufficiently declarative. There seem to be synchronization scopes analogous to state and to hypotheticals, but not my, our, temp, and has. (I'm not sure exactly what primitives are needed: we could discover that by doing more parallel programming ... which won't happen unless it's easy) The way humans seem to work is that they'll say I'll do this and this separately, but I won't worry about that unless something goes wrong. We employ a mixture of course grain threading, fine grain locking, exceptions, and recoverable transactions; that we juggle dynamically. That's pretty hard to do when writing a program, which is why I want to place the burden on the language designer, not the language user. With Perl 6 we're trying to make the opposite mistake. I fear you may be successfully underemphasizing one dimension to the detriment of others :-). But considering that you do a pretty good job most of the time, I'm not too worried.
Re: Sequential bias in S04 (and Perl6 in general)
On Fri, Jan 04, 2008 at 01:13:11PM -0800, Dave Whipp wrote: From that perspective, it's unfortunate a Cfor loop always iterates arrays in the order of their indices. But it doesn't, in hyper context. In Perl 6, Cfor and Cmap are really the same thing, and both respond to hyper context. As I see it, parallelism is easy: it's synchronization that's hard. Specifically, it's hard to get exactly the right scoping of constraints. And it seems to me that hyper addresses the parallelization aspect but not synchronization. Concurrency.pod (S17) defines a few basic mechanisms, but it's not obvious that they're really easy, or sufficiently declarative. There seem to be synchronization scopes analogous to state and to hypotheticals, but not my, our, temp, and has. (I'm not sure exactly what primitives are needed: we could discover that by doing more parallel programming ... which won't happen unless it's easy) My only feeling on the matter currently is that Ctemp and Clet are probably evil when used on anything shareable, whereas lexicals and contextual vars are probably better behaved. But I'm quite certain people will be playing with the declarative parallelism we've already put in via hyperops, junctions, and feeds, not to mention transactions to manage cooperating events. The way humans seem to work is that they'll say I'll do this and this separately, but I won't worry about that unless something goes wrong. We employ a mixture of course grain threading, fine grain locking, exceptions, and recoverable transactions; that we juggle dynamically. That's pretty hard to do when writing a program, which is why I want to place the burden on the language designer, not the language user. Sure, my hope is that we can delegate locking entirely to the innards of the implementation and never mention it at all on the language level. STM may or may not be the solution to that. Exceptions are also evil when it comes to concurrency; that's why we've gone to great pains to allow unthrown exceptions to be returned as data when failures occur. You really, really don't want your hyperops throwing exceptions just because one value in a million was bogus. With Perl 6 we're trying to make the opposite mistake. I fear you may be successfully underemphasizing one dimension to the detriment of others :-). But considering that you do a pretty good job most of the time, I'm not too worried. Well, I don't profess to be omniscient, or even prescient. All I can point out is that I'm also trying very hard to make a language that can mutate away from Evil and towards Good, however they choose to define themselves in the cybersphere this year. And that is why grammars must do completely fair longest-token matching across all base and derived grammars (maybe even in parallel :). It is a mistake to privilege either the old over the new or the new over the old, to the extent that they can coexist. In ecological terms, I hope Perl 6 will have a very wide gene pool. Larry
Re: Sequential bias in S04 (and Perl6 in general)
Dave Whipp wrote: No, you're not the only person thinking Occam ... though I should point out that none of my suggestions are par blocks -- a par block made every statement within the block execute in parallel with the other statements in that block (much like a Verilog fork/join pair). No; that was me. Although, as Luke pointed out, I wasn't thinking parallel execution so much as arbitrarily ordered execution (which, as Dave points out, is a prerequisite for true parallel execution). Paul Seamons wrote: I disagree with the idea that humans don't think concurrently (though more often they think in terms of data dependencies). I think this is more analogous to event based programming rather than parallel programming. Event based and parallel based have some similarities but the are fundamentally different. Humans typically interact with events and only occasionally are able to walk and chew gum at the same time. As a human (as opposed to that weird creature known as a professional programmer), I tend to do one thing at a time, though I'm more than capable of prioritizing a set of tasks that are handed to me, even if new tasks are added to my workload while I'm still working on others. And if I'm working as part of a team, I know how to delegate tasks to others. As Dave points out, it isn't parallelism that's hard so much as it is coordination with the rest of the team in order to prevent conflicts involving shared resources. -- Jonathan Dataweaver Lang
Re: Sequential bias in S04 (and Perl6 in general)
Larry Wall wrote: I (impersonally) believe that hyper context is the right solution to this because context can propagate to where it needs to dynamically. As for the fact that it's not the default list context for for, that could easily be changed with a pragma. Maybe that could even be the default someday, but we have to educate people to think about hyper first. As I just indicated, I'm a mere mortal; so some of the terminology you're using here is throwing me. When I hear hyper context, my gut instinct is to think he's advocating some sort of application of the hyperoperator. Is that what you mean, or would the substitution of a bag for a list in a for statement qualify as hyper context? Or maybe you mean something like the use of a junction in a given statement as the parallelized equivalent of a for statement? for @x { ... } # executes the block for each element of @x in series given all(@x) { ... } # executes the block for each element of @x in parallel As for the other part of the proposal, a parallel smartmatch would need new comb syntax for the compound pattern--I wouldn't overload given/when for that. Or maybe just make a way to attach a mapreduce action to any leg of a junction or hyperoperator. Again, I'm not up on the terminology being used here. But if I'm getting the gist of it right, the following is in the spirit of what you're suggesting: Introduce a function that does given/when-type smart-matching, but geared around pattern/code Pairs: e.g., match $x: 1..3 = { dothis() }, 4..6 = { dothat() } # equivalent to: given $x { when 1..3 { dothis() } when 4..6 { dothat() } } Then you could use a junction of Pairs in place of a single Pair to smart-match the patterns in parallel: match $x: 1..3 = { dothis() } 2..4 = { dothat() } # smart-matches 1..3 and 2..4 in parallel In any case, we need to make sure it's easy to place such a parallel comb of matchers at the pointy end of a feed, and if the source of the feed is also executing in parallel, make sure the feed can be optimized to a full crossbar based on packet destination. In the above example, you might say: @x».match 1..3 = { dothis() } 2..4 = { dothat() } or match any(@x): 1..3 = { dothis() } 2..4 = { dothat() } in order to get a full crossbar. It's also possible that we should discourage syntactic parallel matching in favor of parallel polymorphic dispatch, given that signatures can also express patterns. Might need to tweak the current multiple dispatch rules a bit though if we want dispatch ambiguity to express nondeterminism. In any case, real mapreduce situations are often generated dynamically, and cannot easily be expressed in a syntactically fixed set of options. No idea what you're talking about here. -- Jonathan Dataweaver Lang
Re: Sequential bias in S04 (and Perl6 in general)
Larry Wall wrote: my hope is that we can delegate locking entirely to the innards of the implementation and never mention it at all on the language level. Hmm, sounds to me analogous to hoping that type inference will avoid the need to expose type-annotations at the language level (synchronization constraints can be seen as an extension the type system -- that is, the formal theory that defines what it means for a program to be well behaved). Even if it is possible to infer everything automagically, it is still useful for the user to reinforce the inference with explicit, precise, declarations: makes things faster, and avoids pathological corner cases. Plus it catches errors. Which I guess is why perl6 provides a user-visible explicit typing system. Even if locking itself remains under-the-hood, the constraints that imply the locking need to be user-visible. S03 says that a hyperoperator is a promise that the operator is parallelizable; but that promise implies that the author has taken care of any sync issues in the side effects. It cannot simultaneously be both a promise that the code is safe, and a demand that that compiler add locking to make it safe.
Re: Sequential bias in S04 (and Perl6 in general)
Dave Whipp wrote: I was reading Synopsis 4 with regards to multi core programming. It seems to be infused with a bias towards non-parallel models of computation. Concurrently appears to be an add-on feature -- whereas we should have a mindset that explicit sequential constraints are the add-on feature. That sounds really like a bad idea for simple just do it scripts. Just imagine explaining concurrency issue to a beginner who is not even confident with variables and blocks... Two statements that are missing from S04 (feel free to change the names) are Cforall; and a form of Cgiven that tests/executes multiple Cwhen clauses in arbitrary order (without needing the sequential Ccontinue statement). forall @a - $x { ... } runs the code block on each element of @a (no defined order). You can achieve that with the hyper list-op (see S02). Also note that an optimizer is free to automatically add the hyper list op if it can prove that the executed block has no side effects. ... Similarly, Cmap, Cclassify, Cgrep, Creduce, ... should all accept this :sequential adverb to force them to iterate their lists sequentially -- and should otherwise iterate in arbitrary/concurrent order. Some of this can be written with hyper ops, just as the dot for method calls has a hyper dot Object.method I'm not too concerned about the exact details: my point is that we should be fully aware of the fact that perl6 will be released into a multicore (some people use the term many-core for devices with hundreds of cores) world, and that exploitation of these parallel resources should be the default (easy) behavior. We shouldn't have a concurrency synopsis (we don't -- but we do have Spec/concurrency.pod). Instead, we should have sequential.pod that defines how to impose additional sequential constraints (e.g. :atomic, :sequential) on top of the those inferred from data dependencies. I think that the concurrency synopsis is still useful for explicit threading, STM and the like. Also note that Perl 6 tries to preserver Perl's soul, and is not an Erlang based language ;-) Cheers, Moritz -- Moritz Lenz http://moritz.faui2k3.org/ | http://perl-6.de/ signature.asc Description: OpenPGP digital signature