Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!decwrl!ucbvax!sprite.berkeley.edu!tve
From: tve@sprite.berkeley.edu (Thorsten von Eicken)
Newsgroups: comp.lang.functional
Subject: Re: performance of array comprehensions in Id
Keywords: dataflow
Message-ID: <37454@ucbvax.BERKELEY.EDU>
Date: 7 Jul 90 08:39:49 GMT
References: <55973@lanl.gov>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: tve@sprite.berkeley.edu (Thorsten von Eicken)
Organization: University of California, Berkeley
Lines: 30

In article <55973@lanl.gov> jashley@lanl.gov (J. Michael Ashley) writes:
>In
>  ({ array (1, middle) | [i] = v[i*2-1] || i <- 1 to middle },
>   { array (1, middle) | [i] = v[i*2]   || i <- 1 to middle })
>} ;
>
>It turns out that the i's get generated sequentially, which is really
>too bad since there is no data dependency between the elements of the two
>arrays being built.

Well, what do you expect?  I don't think anyone has come up with an
ALU that can generate all values for i at once...
Seriously, the "optimal" solution would be to generate the i's in
a tree, but we've found that it's usually sufficient to recode the
loop as two nested loops. Let the outer one go by large increments and
the inner one fill the in-betweens. For example:
{ array (1, mid) | [i] = v[i*2-1] || i <- j to j+15 & j <- 1 to mid by 16}
(I realize I'm not worrying about the bounds very much).

>Thanks
>
>--
>J. Michael Ashley              internet: jashley@lanl.gov
>Los Alamos National Labs                 ashley@occs.cs.oberlin.edu

Hope that helps you a bit...
---
Thorsten von Eicken		tve@sprite.berkeley.edu
Computer Science Div.
UC Berkeley