diff options
author | David Mitchell <davem@iabyn.com> | 2014-10-24 16:26:38 +0100 |
---|---|---|
committer | David Mitchell <davem@iabyn.com> | 2014-12-07 09:24:55 +0000 |
commit | fedf30e1c349130b23648c022f5f3cb4ad7928f3 (patch) | |
tree | 59634b92647baec7686f67156a199f0f33ef19bb /t/perf/opcount.t | |
parent | 2f7c6295c991839e20b09fbf3107b861d511de31 (diff) | |
download | perl-fedf30e1c349130b23648c022f5f3cb4ad7928f3.tar.gz |
Add OP_MULTIDEREF
This op is an optimisation for any series of one or more array or hash
lookups and dereferences, where the key/index is a simple constant or
package/lexical variable. If the first-level lookup is of a simple
array/hash variable or scalar ref, then that is included in the op too.
So all of the following are replaced with a single op:
$h{foo}
$a[$i]
$a[5][$k][$i]
$r->{$k}
local $a[0][$i]
exists $a[$i]{$k}
delete $h{foo}
while these aren't:
$a[0] already handled by OP_AELEMFAST
$a[$x+1] not a simple index
and these are partially replaced:
(expr)->[0]{$k} the bit following (expr) is replaced
$h{foo}[$x+1][0] the first and third lookups are each done with
a multideref op, while the $x+1 expression and
middle lookup are done by existing add, aelem etc
ops.
Up until now, aggregate dereferencing has been very heavyweight in ops; for
example, $r->[0]{$x} is compiled as:
gv[*r] s
rv2sv sKM/DREFAV,1
rv2av[t2] sKR/1
const[IV 0] s
aelem sKM/DREFHV,2
rv2hv sKR/1
gvsv[*x] s
helem vK/2
When executing this, in addition to the actual calls to av_fetch() and
hv_fetch(), there is a lot of overhead of pushing SVs on and off the
stack, and calling lots of little pp() functions from the runops loop
(each with its potential indirect branch miss).
The multideref op avoids that by running all the code in a loop in a
switch statement. It makes use of the new UNOP_AUX type to hold an array
of
typedef union {
PADOFFSET pad_offset;
SV *sv;
IV iv;
UV uv;
} UNOP_AUX_item;
In something like $a[7][$i]{foo}, the GVs or pad offsets for @a and $i are
stored as items in the array, along with a pointer to a const SV holding
'foo', and the UV 7 is stored directly. Along with this, some UVs are used
to store a sequence of actions (several actions are squeezed into a single
UV).
Then the main body of pp_multideref is a big while loop round a switch,
which reads actions and values from the AUX array. The two big branches in
the switch are ones that are affectively unrolled (/DREFAV, rv2av, aelem)
and (/DREFHV, rv2hv, helem) triplets. The other branches are various entry
points that handle retrieving the different types of initial value; for
example 'my %h; $h{foo}' needs to get %h from the pad, while '(expr)->{foo}'
needs to pop expr off the stack.
Note that there is a slight complication with /DEREF; in the example above
of $r->[0]{$x}, the aelem op is actually
aelem sKM/DREFHV,2
which means that the aelem, after having retrieved a (possibly undef)
value from the array, is responsible for autovivifying it into a hash,
ready for the next op. Similarly, the rv2sv that retrieves $r from the
typeglob is responsible for autovivifying it into an AV. This action
of doing the next op's work for it complicates matters somewhat. Within
pp_multideref, the autovivification action is instead included as the
first step of the current action.
In terms of benchmarking with Porting/bench.pl, a simple lexical
$a[$i][$j] shows a reduction of approx 40% in numbers of instructions
executed, while $r->[0][0][0] uses 54% fewer. The speed-up for hash
accesses is relatively more modest, since the actual hash lookup (i.e.
hv_fetch()) is more expensive than an array lookup. A lexical $h{foo}
uses 10% fewer, while $r->{foo}{bar}{baz} uses 34% fewer instructions.
Overall,
bench.pl --tests='/expr::(array|hash)/' ...
gives:
PRE POST
------ ------
Ir 100.00 145.00
Dr 100.00 165.30
Dw 100.00 175.74
COND 100.00 132.02
IND 100.00 171.11
COND_m 100.00 127.65
IND_m 100.00 203.90
with cache misses unchanged at 100%.
In general, the more lookups done, the bigger the proportionate saving.
Diffstat (limited to 't/perf/opcount.t')
-rw-r--r-- | t/perf/opcount.t | 151 |
1 files changed, 148 insertions, 3 deletions
diff --git a/t/perf/opcount.t b/t/perf/opcount.t index 659a80ee12..f3c0badcb6 100644 --- a/t/perf/opcount.t +++ b/t/perf/opcount.t @@ -17,7 +17,10 @@ BEGIN { @INC = '../lib'; } -plan 28; +use warnings; +use strict; + +plan 2249; use B (); @@ -56,8 +59,16 @@ use B (); note(sprintf "%3d %s", $counts{$_}, $_) for sort keys %counts; } + my @exp; for (sort keys %$expected_counts) { - is ($counts{$_}//0, $expected_counts->{$_}, "$desc: $_"); + my ($c, $e) = ($counts{$_}//0, $expected_counts->{$_}); + if ($c != $e) { + push @exp, "expected $e, got $c: $_"; + } + } + ok(!@exp, $desc); + if (@exp) { + diag($_) for @exp; } } } @@ -65,7 +76,7 @@ use B (); # aelem => aelemfast: a basic test that this test file works test_opcount(0, "basic aelemfast", - sub { $a[0] = 1 }, + sub { our @a; $a[0] = 1 }, { aelem => 0, aelemfast => 1, @@ -96,6 +107,7 @@ test_opcount(0, "basic aelemfast", } ); + no warnings 'void'; test_opcount(0, "bench.pl active loop", sub { for my $x (1..$ARGV[0]) { $x; } }, { @@ -115,3 +127,136 @@ test_opcount(0, "basic aelemfast", } ); } + +# +# multideref +# +# try many permutations of aggregate lookup expressions + +{ + package Foo; + + my (@agg_lex, %agg_lex, $i_lex, $r_lex); + our (@agg_pkg, %agg_pkg, $i_pkg, $r_pkg); + + my $f; + my @bodies = ('[0]', '[128]', '[$i_lex]', '[$i_pkg]', + '{foo}', '{$i_lex}', '{$i_pkg}', + ); + + for my $prefix ('$f->()->', '$agg_lex', '$agg_pkg', '$r_lex->', '$r_pkg->') + { + for my $mod ('', 'local', 'exists', 'delete') { + for my $body0 (@bodies) { + for my $body1 ('', @bodies) { + for my $body2 ('', '[2*$i_lex]') { + my $code = "$mod $prefix$body0$body1$body2"; + my $sub = "sub { $code }"; + my $coderef = eval $sub + or die "eval '$sub': $@"; + + my %c = (aelem => 0, + aelemfast => 0, + aelemfast_lex => 0, + exists => 0, + delete => 0, + helem => 0, + multideref => 0, + ); + + my $top = 'aelem'; + if ($code =~ /^\s*\$agg_...\[0\]$/) { + # we should expect aelemfast rather than multideref + $top = $code =~ /lex/ ? 'aelemfast_lex' + : 'aelemfast'; + $c{$top} = 1; + } + else { + $c{multideref} = 1; + } + + if ($body2 ne '') { + # trailing index; top aelem/exists/whatever + # node is kept + $top = $mod unless $mod eq '' or $mod eq 'local'; + $c{$top} = 1 + } + + ::test_opcount(0, $sub, $coderef, \%c); + } + } + } + } + } +} + + +# multideref: ensure that the prefix expression and trailing index +# expression are optimised (include aelemfast in those expressions) + + +test_opcount(0, 'multideref expressions', + sub { ($_[0] // $_)->[0]{2*$_[0]} }, + { + aelemfast => 2, + helem => 1, + multideref => 1, + }, + ); + +# multideref with interesting constant indices + + +test_opcount(0, 'multideref const index', + sub { $_->{1}{1.1} }, + { + helem => 0, + multideref => 1, + }, + ); + +use constant my_undef => undef; +test_opcount(0, 'multideref undef const index', + sub { $_->{+my_undef} }, + { + helem => 1, + multideref => 0, + }, + ); + +# multideref when its the first op in a subchain + +test_opcount(0, 'multideref op_other etc', + sub { $_{foo} = $_ ? $_{bar} : $_{baz} }, + { + helem => 0, + multideref => 3, + }, + ); + +# multideref without hints + +{ + no strict; + no warnings; + + test_opcount(0, 'multideref no hints', + sub { $_{foo}[0] }, + { + aelem => 0, + helem => 0, + multideref => 1, + }, + ); +} + +# exists shouldn't clash with aelemfast + +test_opcount(0, 'multideref exists', + sub { exists $_[0] }, + { + aelem => 0, + aelemfast => 0, + multideref => 1, + }, + ); |