Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Perl and common subexpressions

by Stevie-O (Friar)
on Dec 23, 2004 at 06:24 UTC ( #417006=perlmeditation: print w/ replies, xml ) Need Help??

While talking to revdiablo about the details behind the behavior of $_ vs. argument passing, I threw together this example of where things in Perl aren't always well-understood.

In C, the following code:

// hypothetical struct x if (flag) { x->y->z->a->b[5]->q = 8; x->y->z->a->b[5]->r = 9; }
gets compiled very efficiently with optimizations turned on, due to a standard optimization called 'common subexpression elimination' (heretofore referred to as 'CSE'). In effect, the compiler does this:
if (flag) { t = x->y->z->a->b[5]; t->q = 8; t->r = 9; }
Thus, the compiler only has to perform all these dereferences *once*. Unfortunately, unlike C, Perl has to contend with something a little crazier: Tied hashes and arrays. The nature of tied hashes and arrays makes certain things impossible, including CSE. To illustrate my point, I created a benchmark:
#!/usr/bin/perl use strict; use warnings; use Time::HiRes; use Benchmark qw(cmpthese :hireswallclock); my @bogus; $bogus[1]{foo}[2]{bar}[3]{baz} = 5; $bogus[1]{foo}[2]{bar}[3]{quux} = 6; our @bogus2; $bogus2[1]{foo}[2]{bar}[3]{baz} = 5; $bogus2[1]{foo}[2]{bar}[3]{quux} = 6; cmpthese(1_000_000, { without_common => sub { my $prod = $bogus[1]{foo}[2]{bar}[3]{baz} * $bogus[1]{foo}[2]{bar}[3]{quux}; }, with_common => sub { my $common = $bogus[1]{foo}[2]{bar}[3]; my $prod = $common->{baz} * $common->{quux}; }, without_common_g => sub { my $prod = $bogus2[1]{foo}[2]{bar}[3]{baz} * $bogus2[1]{foo}[2]{bar}[3]{quux}; }, with_common_g => sub { my $common = $bogus2[1]{foo}[2]{bar}[3]; my $prod = $common->{baz} * $common->{quux}; }, });
The results on my machine are as such:
Rate without_common_g without_common with_common_ +g with_common without_common_g 341880/s -- -4% -20 +% -23% without_common 357910/s 5% -- -16 +% -19% with_common_g 428449/s 25% 20% - +- -3% with_common 443853/s 30% 24% 4 +% --
Note carefully that with_common runs 24% faster than without_common. That's because, even with the extra variable, the three array index and two hash key lookups saved in with_common more than compensate for the extra variable assignment.

Also note the 4-5% difference between with_common/without_common and their _g equivalents. This is *entirely* due to the extra hash lookup required to get the address of the global 'bogus2'. This hash lookup is ALWAYS required due to dynamic scoping requirements.

Morals of the story:

  • Manually perform subexpression elimination in tight loops as often as you practically can. It can make quite a bit of difference in a CPU-bound script. (Remember -- 25% is the difference between an hour and 45 minutes.)
  • *Always* use lexicals if you possibly can. It's not that difficult, and although the savings are small, they *are* measurable. For a more extreme example, see $_ vs. argument passing.

Update: Realized how long this node is, added readmore.
--Stevie-O
$"=$,,$_=q>|\p4<6 8p<M/_|<('=> .q>.<4-KI<l|2$<6%s!<qn#F<>;$, .=pack'N*',"@{[unpack'C*',$_] }"for split/</;$_=$,,y[A-Z a-z] {}cd;print lc

Comment on Perl and common subexpressions
Select or Download Code
Re: Perl and common subexpressions
by Zaxo (Archbishop) on Dec 23, 2004 at 06:56 UTC

    Nice to see that quantified, thanks!

    A similar optimization can be set up when map or a for loop is applied to the values of a hash or elements of an array,

    my $total; $total += $_->{'cost'} for @{$struct[3]{'baz'}[42]};

    After Compline,
    Zaxo

      Interestingly, doing that for the simple case seems to actually impede rather than help performance:

      #!/usr/bin/perl use strict; use warnings; use Benchmark qw( cmpthese ); my @bogus; $bogus[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ baz } = 5; $bogus[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ quux } = 6; our @bogus2; $bogus2[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ baz } = 5; $bogus2[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ quux } = 6; cmpthese( -3 => { without_common => sub { my $prod = $bogus[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ baz } * $bogus[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ quux }; }, with_common => sub { my $common = $bogus[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]; my $prod = $common->{ baz } * $common->{ quux }; }, with_for => sub { my $prod; $prod = $_->{ baz } * $_->{ quux } for $bogus[ 1 ]{ foo }[ 2 ] +{ bar }[ 3 ]; }, with_for_g => sub { my $prod; $prod = $_->{ baz } * $_->{ quux } for $bogus2[ 1 ]{ foo }[ 2 +]{ bar }[ 3 ]; }, without_common_g => sub { my $prod = $bogus2[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ baz } * $bogus2[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]{ quux }; }, with_common_g => sub { my $common = $bogus2[ 1 ]{ foo }[ 2 ]{ bar }[ 3 ]; my $prod = $common->{ baz } * $common->{ quux }; }, } ); __END__ Rate with_for with_for_g without_common without_c +ommon_g with_common with_common_g with_for 346092/s -- -1% -17% + -19% -36% -37% with_for_g 350487/s 1% -- -16% + -18% -35% -37% without_common 416843/s 20% 19% -- + -3% -23% -25% without_common_g 429491/s 24% 23% 3% + -- -20% -22% with_common 537863/s 55% 53% 29% + 25% -- -3% with_common_g 553408/s 60% 58% 33% + 29% 3% --

      I have to say this result surprised me.

      Makeshifts last the longest.

Re: Perl and common subexpressions
by dws (Chancellor) on Dec 23, 2004 at 07:16 UTC

    Unfortunately, unlike C, Perl has to contend with something a little crazier: Tied hashes and arrays.

    And function calls. In

    t = x->y->z->a->b[5];
    any of y, z, or a can be methods, with or without side-effects, and with no guarantee that they'll return the same thing on subsequent calls. In the face of such flexibility, static analysis optimizations are non-starters.

      It's trivial to tell the difference between a method call and a hash lookup for the perl compile -- you're just having issues with C vs perl syntax. (Getting e, an element of the struct pointed to by p in C is p->e, which looks a lot like calling a method, m, on an object $o in Perl -- $o->m)

      On the other hand, when it /is/ a method call, perl can't tell /what/ method is being called, because it doesn't know the type of the object you're calling the method on until runtime. The m method on Foo::Bar might be side-effect free, while the m method on Baz has side-effects.


      Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).

Re: Perl and common subexpressions
by revdiablo (Prior) on Dec 23, 2004 at 07:23 UTC

    Nice post, Stevie-O. Of course, you already knew I would say that, since we talked about it before you posted... but you know.

    I was curious to see when the common subexpression elimination would pay off. So I tested both hashes and arrays against eachother at various depths, to see when the CSE would overcome the assignment overhead. Here's my benchmark (sorry for the cryptic names, I didn't feel like typing a whole lot):

    It looks like hashes get a benefit at just 2 levels of references, but with arrays it doesn't pay off until 3 levels. Maybe not very surprising, but possibly useful information.

Re: Perl and common subexpressions
by Anonymous Monk on Dec 23, 2004 at 12:53 UTC
    Manually perform subexpression elimination in tight loops as often as you practically can. It can make quite a bit of difference in a CPU-bound script. (Remember -- 25% is the difference between an hour and 45 minutes.)
    Please be very, very carefully with drawing conclusions. You have performed a benchmark, with one specific set of data, using a specific versions of Perl, for a specific version of a certain OS, running on a specific set of hardware. All you have proven so far is that with this particular combination of data, OS, perl version and hardware, you have a 25% gain. For someone else, using a different OS, a different CPU, or a different version of Perl, the numbers might be different.

    Note also that a 25% improvement in an very, very simple loop seldomly translates to 25% improvement in the overall program. If only for the fact you'll typically do more in the loop.

      This is very true.

      That is, by the way, why I qualified my statement with 'CPU-bound'. When the bulk of your program involves I/O, the overhead from array, hash, and stash lookups becomes negligible -- even for pipes, because they involve context switches to the process on the other end of the pipe.

      --Stevie-O
      $"=$,,$_=q>|\p4<6 8p<M/_|<('=> .q>.<4-KI<l|2$<6%s!<qn#F<>;$, .=pack'N*',"@{[unpack'C*',$_] }"for split/</;$_=$,,y[A-Z a-z] {}cd;print lc
Re: Perl and common subexpressions
by TimToady (Parson) on Dec 23, 2004 at 18:46 UTC
    One minor quibble: the decision not to do common subexpression elimination actually predated tie and references. The main motivation for not doing it was that it was potentially an expensive optimization, and as a compile-and-go language, Perl could not afford any expensive optimizations that don't usually buy you much and can easily be emulated by hand coding anyway. Of course, as Perl moves more in the direction of precompiled modules, this policy will be subject to revision. (And this is also one of the reasons Perl 6 tightens up the rules on tying so that you can't tie a variable unless it has been declared as tieable, or even tied directly at declaration time.)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://417006]
Front-paged by mojotoad
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (3)
As of 2014-08-21 04:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (127 votes), past polls