Скорость индексирования массивов Perl с помощью смещения

В соответствии с этим вопросом и этот ответ списки реализуются как массивы:

Perl реализует списки с массивом и смещения первого/последнего элемента. массив выделяется больше, чем необходимо с смещениями, первоначально указывающими в середине массива, так что есть место для роста в обоих направлениях (unshifts и push/inserts) перед перераспределение базового массива необходимо. Следствием этого реализация заключается в том, что все примитивные операторы списка (вставка, выборка, определение размера массива, push, pop, shift, unshift и т.д.) выполнить в O (1) время.

Таким образом, вы ожидаете, что доступ к элементу с помощью числового смещения будет таким же быстрым, потому что они представляют собой массивы в реализации, которые обеспечивают очень быструю индексацию в постоянном времени. Однако в сноске в Learning Perl автор говорит

Индексирование в массивы не используется Сильные стороны Perls. Если вы используете поп, push и аналогичных операторов, которые избегают используя индексирование, ваш код будет как правило, быстрее, чем если вы используете многие индексы, а также избегая ошибки "по очереди", часто называемые ошибки "fencepost". Иногда, начиная программист Perl (желая посмотрите, как скорость Perls сравнивается с Cs) возьмет, скажем, алгоритм сортировки оптимизированный для C (с большим индексом массива операции), переписать его прямо в Perl (опять же, с многие операции с индексами) и удивляться, почему его так медленно. Ответ заключается в том, что использование скрипка Страдивари для ног не следует рассматривать как звук строительной техники.

Как это может быть правдой, когда список действительно представляет собой массив под капотом? Я знаю, что просто неосведомленно пытаться сравнить скорость Perl с C, но не индексировать список по смещению так же быстро, как pop или push или что-то еще? Они, кажется, противоречат друг другу.

Ответы

Ответ 1

Это связано с реализацией Perl как серии кодов операций. push, pop, shift и unshift - это все коды операций, поэтому они могут индексироваться в массив, с которым они манипулируют с C, где обращения выполняются очень быстро. Если вы сделаете это с Perl с индексами, вы заставите Perl выполнить дополнительные коды операций, чтобы получить индекс от скаляра, получить слот из массива, а затем поместить в него что-то.

Вы можете увидеть это, используя ключ -MO = Terse, чтобы увидеть, что Perl действительно (в некотором смысле):

$foo[$i] = 1

    BINOP (0x18beae0) sassign
        SVOP (0x18bd850) const  IV (0x18b60b0) 1
        BINOP (0x18beb60) aelem
            UNOP (0x18bedb0) rv2av
                SVOP (0x18bef30) gv  GV (0x18b60c8) *foo
            UNOP (0x18beba0) null [15]
                SVOP (0x18bec70) gvsv  GV (0x18b60f8) *i

push @foo, 1

    LISTOP (0x18bd7b0) push [2]
        OP (0x18aff70) pushmark
        UNOP (0x18beb20) rv2av [1]
            SVOP (0x18bd8f0) gv  GV (0x18b60c8) *foo
        SVOP (0x18bed10) const  IV (0x18b61b8) 1

Вы видите, что Perl должен выполнять меньше шагов, поэтому можно ожидать, что они будут быстрее.

Трюк с любым интерпретируемым языком должен позволить ему выполнять всю работу.