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

Re: Make built-in list functions continuous

Thread Previous | Thread Next
Graham Barr
April 1, 2008 07:45
Re: Make built-in list functions continuous
Message ID:
On Apr 1, 2008, at 8:49 AM, Nicholas Clark wrote:
>> 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
> I'm not personally, but given that there are over 400 subscribers  
> to the
> list, I suspect than there are quite a few people who are.
>>     @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;

I am not convinced that is always "better" performance. It depends  
what you metric is. While it may use less memory, it is more OPs to  
run and may result in slower runtime performance in some cases.

>> 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.

There should not be much copying going on. the values on the stack as  
a result of the map should be TEMPs so the assignment should be able  
to just steal the SV in exactly the same way that push does.

>> 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;
>> ...becomes:
>>     foreach (@ys) {
>>         p1($_);
>>         p2($_);
>>         ...
>>         if (pn($_)) {
>>             f1($_);
>>             f2($_);
>>             ...
>>             push @xs, fn($_);
>>         }
>>     }

Again I am not convinced that CPU-wise this is always going to be a  

>> 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;
> I think you made a typo and meant
>      @xs = map {$_ = g($_); f($_)} @ys;

No they are not the same. The context of g() has changed. In the  
first case g() may return multiple or even zero results and each will  
be processed by f()

> given the right to left nature of the map pipeline. But in the Perl  
> general
> case, I don't think that the rewrite is equivalent, as the context  
> of &g is
> wrong
>      @xs = map {my @a = g($_); f(@a)} @ys;
> except that isn't correct in the general case either, as the map  
> pipeline
> calls &f many times with exactly one argument, so I think it ends  
> up as
>      @xs = map {my @a = g($_); my @b = f($_) foreach @a; @b} @ys;

You mean

    @xs = map {my @a = g($_); my @b; push @b, f($_) foreach @a; @b} @ys;

Which probably does result in more copying than the original map  
because the intermediate values are assigned to an array instead of  
just being TEMPs on the stack.

> (which at least avoids needing a full length temporary list, and  
> would combine
> with your previous re-write to become
>      my @xs;
>      foreach my $y (@ys) {
> 	push @xs, f($_) foreach g($y);
>      }

That is probably the best you can do to save memory

> I suspect that the number of people who have good knowledge of the  
> entire
> parsing/compilation code worldwide is under 10. I suspect that I  
> count as
> "fast learner" for the purposes of this exercise, and it took me an  
> entire
> full time week to figure out how to optimise `reverse sort` and  
> `foreach
> (reverse @zam)` at the optree level, and I think a day for cutting  
> [] and {}
> construction from 3 ops to 1. I don't know how long it took Dave to
> implement in-place sort (`@glurp = sort @glurp`), or Yves to  
> implement a
> faster `if (%hash)` but these are the only optree level  
> optimisations that
> I'm aware of in the past 3 years. I didn't find it easy at all.

It is not. I have not worked on the parser for some 8 years and I  
still have the scars :-)

> The re-writes certainly look interesting, and I can't see any scope  
> related
> reasons why they would fail in the general case, but I suspect that  
> actually
> implementing them in C from the ground up right now would even tax  
> Robin
> Houston (who knows the optree well, and now has a PhD in computer  
> science)

The extent that map/grep go to to keep the calling overhead of the  
block is horrendous and getting that to work for reduce in List::Util  
was difficult. Doing it with multiple blocks is going to be potential  
very difficult.

> What might be a much better start is to get optimize and  
> B::Generate to the
> state where it's viable to write the optree re-writers themselves  
> in pure
> Perl, and that way get the bugs out of them (and see where the real  
> wins are).
> That would make it easier for more people to prototype things in  
> Perl, and
> much reduce the amount of human time needed to write C, just down to
> "re-implement this", instead of "prototype, develop and debug".



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