arrays - 按偏移量索引 Perl 数组的速度

Question

根据 this question和 this answer , 列表被实现为数组:

Perl implements lists with an array and first/last element offsets. The array is allocated larger than needed with the offsets originally pointing in the middle of the array so there is room to grow in both directions (unshifts and pushes/inserts) before a re-allocation of the underlying array is necessary. The consequence of this implementation is that all of perl's primitive list operators (insertion, fetching, determining array size, push, pop, shift, unshift, etc.) perform in O(1) time.

因此，您会期望通过数字偏移量访问元素会同样快，因为它们是实现中的数组，可提供非常快的常量时间索引。但是，在 Learning Perl 的脚注中，作者说

Indexing into arrays is not using Perl’s strengths. If you use the pop, push, and similar operators that avoid using indexing, your code will generally be faster than if you use many indices, as well as avoiding “off-by-one” errors, often called “fencepost” errors. Occasionally, a beginning Perl programmer (wanting to see how Perl’s speed compares to C’s) will take, say, a sorting algorithm optimized for C (with many array index operations), rewrite it straightforwardly in Perl (again, with many index operations) and wonder why it’s so slow. The answer is that using a Stradivarius violin to pound nails should not be considered a sound construction technique.

当列表实际上是引擎盖下的数组时，这怎么可能是真的？我知道尝试将 Perl 的速度与 C 的速度进行比较是无知的，但是通过偏移索引列表不会像 pop 或 push 一样快吗？这些似乎相互矛盾。

Answer 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 必须执行更少的步骤，因此可以预期更快。

任何解释型语言的诀窍是让它完成所有工作。