[Swift-devel] Standard Library Proposal/Discussion Page

[Tim Armstrong]

I'm aware K supports execution loops out of order -  I think the out of
order execution is the "right" behavior.  But it doesn't coexist with
versioned variables nicely.  In your example the dataflow matches the
serial control flow dependencies, so there's no direct ordering conflict,
and anyway, there are no versioned variables to cause problems.

 If you reverse it though, then the data flow and implied serial control
flow don't match.  This code should work according to my understanding of
Swift's current semantics, but the implementation would have to infer that
executing the iteration for v=1000 first didn't violate any dependencies
arising from sequential control flow:

float a[];
a[1000] = 10;

foreach v, k in a {
  if (a[k] > 0.01) {
    a[k - 1] = f(a[k]);
  }
}

If you add in a versioned variable, then the code is definitely going to
deadlock because the data dependencies and control dependencies go in
opposite directions:

float a[];
a[1000] = 10;
versioned float x = 1;

foreach v, k in a {
  if (a[k] > x) {
    a[k - 1] = f(a[k]);
    x += a[k];
  }
}

There's also another problem even with ascending indices if you add in a
versioned variable. In order for the k = 1 iteration to execute and the
program to make progress, it has to infer that there is no iteration for k
< 1 that would have a version of x that precedes the version of x for the k
= 1 iteration.  In this example it's possible to prove by induction, but in
general it's equivalent to solving the halting problem:

float a[];
versioned float x = 1
a[1] = 10;

foreach v, k in a {
  if (a[k] > x) {
    a[k + 1] = f(a[k]);
    x = x + a[k]
  }
}

So to do some kind of variable versioning you need a sequential foreach
loop that has semantics that are not entirely compatible with Swift's
existing foreach loop.  The only way I can see to make this compatible with
existing Swift semantics is to automatically switch between the two foreach
loops depending on whether a versioned variable is being modified in the
loop.  I.e. if you use a versioned variable, you asked for a sequential
foreach loop and your code might deadlock.

I think having two versions of the foreach loop that are explicitly
different may be a good idea with use cases, but it's not a good idea to
have them be syntactically identical and switch between incompatible
behaviors based on the presence or absence of a variable of a particular
type.

- Tim

On Thu, Jan 22, 2015 at 1:12 AM, Mihael Hategan <hategan at mcs.anl.gov> wrote:

> On Thu, 2015-01-22 at 00:26 -0600, Tim Armstrong wrote:
> > I agree that the language can pick whatever schedule with whatever degree
> > of parallelism as long as it satisfies the partial order defined by data
> > flow and there are no false control dependencies inserted that will
> prevent
> > progress.
>
> Right. There would be no false dependencies. But if the user has a data
> dependency
>
> a[i + 1] = f(a[i])
>
> then we can't say that they shouldn't. So the issue is not what
> dependencies are there but whether we would allow that statement to be
> written as "a = f(a)". This would allow nothing that isn't already
> allowed.
>
> We should probably drop this though. I think we went past usefulness and
> I do think that a functional approach is more clear and easy to
> implement, it has no blanks to fill in, and is almost certainly less
> contentious.
>
> [...]
> > in the loop body to prevent them from doing so, since otherwise the
> program
> > might fail to make progress when it should, or even deadlock if there is
> > some sort of recursive dependency where the array being iterated over
> > depends directly or indirectly on the computation in the loop body.
>
> Hmm. Maybe I shouldn't point out that K allows this already and perhaps
> this is the missing piece in the conversation. You can write the
> following code:
>
> float a[];
> a[0] = 10;
>
> foreach v, k in a {
>   if (a[k] > 0.01) {
>     a[k + 1] = f(a[k]);
>   }
> }
>
> It's meant as a pure dataflow replacement for iterate{}.
>
> Mihael
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20150122/a09bde3c/attachment.html>