В 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 loop, но даже медленнее method_while2 в два раза быстрее связанного массива.

Даже добавление локализации $_ и присвоения с псевдонимом к method_while2 в method_while3 приводит к быстрому выполнению на 66% по сравнению с связанным массивом.

Какая дополнительная работа происходит в цикле for, чего не происходит в method_while3? Есть ли способ улучшить скорость связанного массива?

Answer 1

Каждый раз, когда вы используете связанный массив, он должен искать связанный объект, затем искать методы и затем вызывать их. В других ваших версиях вы выполняете часть или весь этот поиск либо во время компиляции, либо один раз перед циклом, а не при каждом доступе.

(Кстати, сравнение скоростей между method и другими method_* версиями является хорошим примером этого: вы видите затраты на выполнение этого FETCHSIZE, даже если связанный объект уже выглядел вверх. Теперь примените эту стоимость к каждой отдельной операции, которая касается массива.)

Answer 2

Стоит отметить, что local очень медленный, что объясняет некоторые потери производительности в method_ while3 по сравнению с другими тестами методов. Он также выполняет вход и выход из блока, что связано с затратами.

Несмотря на то, что method_while3 программно эквивалентен statement for x..y, perl может оптимизировать цикл for лучше, чем вы. Как правило, чем больше кода вы делаете внутри perl, тем быстрее будет ваш код.

Answer 3

В тесте вы делаете

... for @$array;

Что, если вы сделали

++$_ for @$array;

Это будет работать. Tie magic оборачивает значение, возвращаемое FETCH, в lvalue, когда значение возвращается в контексте lvalue. Вы можете увидеть это, используя 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 и обрабатываем , что magic объясняет, по крайней мере, некоторую разницу.

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