在Perl中,为什么绑定数组这么慢？

Question

在我的测试中,我注意到迭代绑定数组的速度最好是使用内部存取方法(FETCH和FETCHSIZE)的一半.以下基准显示了该问题:

{package Array;
    sub new {
        my $class = shift;
        tie my @array, $class, [@_];
        \@array
    }
    sub TIEARRAY {
        my ($class, $self) = @_;
        bless $self => $class;
    }
    sub FETCH     {$_[0][$_[1]]}
    sub FETCHSIZE {scalar @{$_[0]}}
}

use List::Util 'sum';
use Benchmark 'cmpthese';

for my $mag (map 10**$_ => 1 .. 5) {

    my $array = Array->new(1 .. $mag);
    my $tied  = tied(@$array);
    my $sum   = sum @$array;

    print "$mag: \n";
    cmpthese -2 => {
        tied => sub {
            my $x = 0;
            $x += $_ for @$array;
            $x == $sum or die $x
        },
        method => sub {
            my $x = 0;
            $x += $tied->FETCH($_) for 0 .. $tied->FETCHSIZE - 1;
            $x == $sum or die $x
        },
        method_while => sub {
            my $x = 0;
            my $i = 0; $x += $tied->FETCH($i++) while $i < $tied->FETCHSIZE;
            $x == $sum or die $x
        },
        method_while2 => sub {
            my $x = 0;
            my $i = 0;
            $x += tied(@$array)->FETCH($i++) 
                while $i < tied(@$array)->FETCHSIZE;
            $x == $sum or die $x
        },
        method_while3 => sub {
            my $x = 0;
            my $i = 0;
            while ($i < tied(@$array)->FETCHSIZE) {
                local *_ = \(tied(@$array)->FETCH($i++));
                $x += $_
            }
            $x == $sum or die $x
        },
    };
    print "\n";
}

数组大小为1000,基准返回:

1000: 
                Rate   tied method_while3 method_while2 method_while   method
tied           439/s     --          -40%          -51%         -61%     -79%
method_while3  728/s    66%            --          -19%         -35%     -65%
method_while2  900/s   105%           24%            --         -19%     -57%
method_while  1114/s   154%           53%           24%           --     -47%
method        2088/s   375%          187%          132%          87%       --

我省略了其他运行,因为数组的大小不会对相对速度产生有意义的改变.

method当然是最快的,因为它不会在每次迭代时检查数组的大小,但是method_while它method_while2似乎以与for循环相同的方式在绑定数组上运行,但即使速度method_while2也比绑定数组快两倍.

甚至在结果中添加了$_别名和别名赋值,比绑定数组的执行速度快66%.method_while2method_while3

在for没有发生的循环中发生了什么额外的工作method_while3？有没有办法提高绑定阵列的速度？

Answer 1

每次使用绑定数组时,都必须查找绑定对象,然后查找方法,然后调用它们.对于其他版本,您在编译时或在循环之前执行部分或全部查找,而不是在每次访问时执行.

(顺序method和其他method_*版本之间的速度比较就是一个很好的例子,顺便说一下:你看到了这样做的费用FETCHSIZE,即使已经查找了绑定的对象.现在将这个成本应用于触及的每一​​个操作数组.)

Answer 2

在基准测试中，你做

... for @$array;

如果你做了怎么办

++$_ for @$array;

它会起作用的。当在左值上下文中返回值时，Tie magic 会将 FETCH 返回的值包装到左值中。您可以使用 Devel::Peek 来查看这一点。

use Devel::Peek;
Dump( $array->[2] );

SV = PVLV(0x14b2234) at 0x187b374
  REFCNT = 1
  FLAGS = (TEMP,GMG,SMG,RMG)
  IV = 0
  NV = 0
  PV = 0
  MAGIC = 0x14d6274
    MG_VIRTUAL = &PL_vtbl_packelem
    MG_TYPE = PERL_MAGIC_tiedelem(p)
    MG_FLAGS = 0x02
      REFCOUNTED
    MG_OBJ = 0x14a7e5c
    SV = IV(0x14a7e58) at 0x14a7e5c
      REFCNT = 2
      FLAGS = (ROK)
      RV = 0x187b324
      SV = PVAV(0x187c37c) at 0x187b324
        REFCNT = 1
        FLAGS = (OBJECT)
        STASH = 0x14a842c       "Array"
        ARRAY = 0x0
        FILL = -1
        MAX = -1
        ARYLEN = 0x0
        FLAGS = (REAL)
    MG_LEN = 2
  TYPE = t
  TARGOFF = 0
  TARGLEN = 0
  TARG = 0x187b374

将 FETCH 返回的值包装到神奇的 SV 中并处理该神奇的值至少可以解释部分差异。

tied_rvalue => sub {
    my $x = 0;
    $x += $_ for @$array;
    $x == $sum or die $x
},
tied_lvalue => sub {
    my $x = 0;
    $x += $array->[$_] for 0 .. $tied->FETCHSIZE - 1;
    $x == $sum or die $x
},

100:
                 Rate tied_rvalue method_while3 tied_lvalue method_while2 method_while method
tied_rvalue    3333/s          --          -33%        -36%          -50%         -58%   -77%
method_while3  4998/s         50%            --         -4%          -25%         -36%   -66%
tied_lvalue    5184/s         56%            4%          --          -23%         -34%   -65%
method_while2  6699/s        101%           34%         29%            --         -15%   -55%
method_while   7856/s        136%           57%         52%           17%           --   -47%
method        14747/s        342%          195%        184%          120%          88%     --