develooper Front page | perl.perl5.porters | Postings from April 2008

Re: Make built-in list functions continuous

Thread Previous | Thread Next
wren argetlahm
April 1, 2008 01:55
Re: Make built-in list functions continuous
Message ID:
Nicholas Clark wrote:
> At
> I spot:
>   Make built-in list functions continuous
>   Functions like map often build up intermediate lists
>   unnecessarily, fix this.
>   Mentor: wren ng thornton
> I was wondering if you had more detail on this, as it's
>  not something currently in the core's TODO file:
> Nicholas Clark

It was mainly something I ran into while optimizing some data-mining 
code a little while back. The margin for speedups is quite dramatic for 
large arrays, and simple cases can be dealt with by fairly trivial 
rewrites. I'm not sure how much more involved a comprehensive solution 
would be; the answer to that would depend on the approach taken (e.g. 
transforming the Perl code before running it, vs rewriting the offending 
functions) as well as the coverage for ferreting out everywhere it happens.

The general genre of this sort of optimization is called 
"deforestation". If you're familiar with Haskell or other ML-like 
languages, this paper[1] discusses a high-level example of the sort of 
thing involved. The details of their solution may not be very pertinent 
to the Perl interpreter, but they give an excellent background on the 
problem and on the known solutions.

The problem is when you have a pipeline of functions and some function 
constructs an intermediate array which will then be read and destroyed 
right away by the next function in the pipeline. A simple example of 
this is the following code where the pipeline is formed by the (=) 
assignment function and the `map` function:

     @xs = map { f($_) } @ys;

In that code, `map` will construct an array in memory, but when it 
returns it, the array will be copied cell by cell into a new array 
constructed as @xs. We can optimize this to remove that intermediate 
array by using the following code instead:

     @xs = ();
     push @xs, f($_) foreach @ys;

This version constructs each element of @xs and then immediately pushes 
it through the "assignment" rather than building them up in memory first.

A different approach would be to rewrite the original code to use a 
different (=) function which just makes @xs an alias to the intermediate 
array returned by map, rather than copying it. This would be along the 
lines of the lexical aliasing task on the perltodo, but it doesn't 
generalize. For example, when we have longer pipelines and so the 
intermediate array needs to be pushed onto @_:

     @xs = map {f($_)} grep {p($_)} @ys;

But, this too can be rewritten as a foreach-loop:

     foreach (@ys) {
         push @xs, f($_) if p($_);

We can transform the majority of the offending cases into foreach-loops 
which capture the fact that these chains of functions are actually 
forming a pipeline through which we're funneling the data streaming from 
@ys. But these rewrites aren't very amenable to using the Filter modules 
since the first argument to `grep` and `map` are blocks, so:

     @xs = map { f1($_) ; f2($_) ;...; fn($_) }
          grep { p1($_) ; p2($_) ;...; pn($_) } @ys;


     foreach (@ys) {
         if (pn($_)) {
             push @xs, fn($_);

Because of this ugliness, the rewrite needs to take place within the 
parsing/compilation pass in order to have access to the AST.

There are other cases where we can't perform this transformation at all, 
such as when we have multiple streams coming together and we need to 
combine them into a single stream to pass along:

     @xs = (map {f($_)} @ys, map {g($_)} @zs);

Granted, that's something of a contrived example, but you get the idea. 
There's also a related optimization which takes the composition of maps 
as the map of composition. I.e. these two lines are equivalent, but the 
latter is more efficient:

     @xs = map {f($_)} map {g($_)} @ys;
     @xs = map {$_ = f($_); g($_)} @ys;

(If you're familiar with Haskell, that's saying that "map f . map g == 
map (f . g)" and the latter is more efficient since it only iterates 
over the list once, as well as not constructing the intermediate list.)

The most-general solution which also captures cases where we need to 
combine streams is to reimplement the offending functions as "continuous 
functions" which explicitly take a stream datastructure as input and 
return a stream as output. The trick is that unlike normal arrays, these 
streams are lazily constructed so the function can read one element off 
at a time, process it, and write anything appropriate into the return 
stream before reading the next element. When the right function writes 
to its return stream the left function gets notified and processes the 
elements right away; thus the only intermediate arrays built up are the 
size of each atomic write to the stream (usually only one element).

One method of implementing continuous functions is to use a lazy array 
like mentioned above; though integrating this into an otherwise non-lazy 
language can require thought. Another approach is to actually spawn off 
threads and pass messages between them; while nicely parallel for 
multi-core folks, usually the overhead is too much unless the functions 
are doing some heavy computations (using a thread pool can reduce the 
overhead somewhat). Yet another approach is to use continuation passing 
in order to capture the flow of control; how nice this approach is 
depends on the implementation of closures. And of course there are other 
approaches as well.

Going all the way and implementing continuous functions would be 
awesome, but it'd also be a good deal of work which might be better 
spent elsewhere. But even just doing the rewrites can improve 
performance for data-heavy programs by 160~200% (== +60~+100%), even 
though it doesn't catch everything. For someone who knows how the 
parsing/compilation sweep works (or can quickly learn) so they can to 
manipulate the ASTs/opcode tree, adding the rewrites should be about the 
right size for a Google Summer of Code project.


Live well,

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About