develooper Front page | perl.perl5.porters | Postings from September 2013

OP_OR early branch exit optimisation

Thread Next
From:
wolfsage
Date:
September 19, 2013 14:49
Subject:
OP_OR early branch exit optimisation
Message ID:
CAJ0K8bgEyVD0CoaMnGprLkO2Sj1-NNQ386C8Thg_cUS7HMU5uQ@mail.gmail.com
Howdy,

I noticed that OP_OR is slightly slower than OP_AND when exiting early
from its branches:

  $ cat run.pl
  #!/usr/bin/perl

  use strict; use warnings;

  use Benchmark qw(timethese);

  my $and = 0;
  my $or  = 1;

  my $other;
  my $junk;

  # Force early exit of branches in both cases
  timethese(10_000_000, {
          'and' => sub { if ($and && $other) { $junk = 0; } },
          'or'  => sub { if ($or  || $other) { $junk = 0; } },
  });

And the test:

  $ ./perl -Ilib run.pl
  Benchmark: timing 10000000 iterations of and, or...
         and:  1 wallclock secs ( 0.46 usr + -0.01 sys =  0.45 CPU) @
22222222.22/s (n=10000000)
          or:  2 wallclock secs ( 2.15 usr +  0.01 sys =  2.16 CPU) @
  4629629.63/s (n=10000000)

I believe it's because of the optimisation that happens for OP_ANDs:

  $ ./perl -Ilib -MO=Concise -e 'if ($aa && $bb) {}'
  8  <@> leave[1 ref] vKP/REFC ->(end)
  1     <0> enter ->2
  2     <;> nextstate(main 3 -e:1) v:{ ->3
  -     <1> null vK/1 ->8
  6        <|> and(other->7) vK/1 ->8
  -           <1> null sK/1 ->6
  4              <|> and(other->5) sK/1 ->8             <-- Optimised
  -                 <1> ex-rv2sv sK/1 ->4
  3                    <$> gvsv(*aa) s ->4
  -                 <1> ex-rv2sv sK/1 ->-
  5                    <$> gvsv(*bb) s ->6
  -           <@> scope vK ->-
  7              <0> stub v ->8
  -e syntax OK

That doesn't happen for OP_ORS:

  $ ./perl -Ilib -MO=Concise -e 'if ($aa || $bb) {}'
  8  <@> leave[1 ref] vKP/REFC ->(end)
  1     <0> enter ->2
  2     <;> nextstate(main 3 -e:1) v:{ ->3
  -     <1> null vK/1 ->8
  6        <|> and(other->7) vK/1 ->8
  -           <1> null sK/1 ->6
  4              <|> or(other->5) sK/1 ->6              <-- Not optimised
  -                 <1> ex-rv2sv sK/1 ->4
  3                    <$> gvsv(*aa) s ->4
  -                 <1> ex-rv2sv sK/1 ->-
  5                    <$> gvsv(*bb) s ->6
  -           <@> scope vK ->-
  7              <0> stub v ->8
  -e syntax OK

Relevant code from rpeep in op.c:

            while (o->op_next && (   o->op_type == o->op_next->op_type
                                  || o->op_next->op_type == OP_NULL))
                o->op_next = o->op_next->op_next;

I've watched in gdb and verified that Perl_pp_or() is following back
into the outer
Perl_pp_and() after exiting whereas Perl_pp_and() doesn't.

Now what I'm wondering is:

 1. How much we care. Certainly someone thought the optimisation was a win,
    so, I think we do, but:

 2. Would it be possible to sanely optimise this use case? I haven't found
    a way yet to detect this type of OP tree without breaking other parts
    of the code. Perhaps someone with more knowledge of the workings here
    could figure something out (otherwise I'll keep poking at it.)

Cheers and thanks,

-- Matthew Horsfall (alh)

Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About