通过偏移索引Perl数组的速度

Question

根据这个问题和这个答案,列表实现为数组:

Perl使用数组和第一个/最后一个元素偏移实现列表.数组的分配大于所需的偏移量,最初指向数组中间的偏移量,因此在重新分配底层数组之前,在两个方向(未移位和推送/插入)都有增长的空间.这种实现的结果是所有perl的原始列表操作符(插入,获取,确定数组大小,推送,弹出,移位,非移位等)在O(1)时间内执行.

因此,您希望通过数字偏移量访问元素的速度同样快,因为它们是实现中的数组,可提供非常快速的常量时间索引.然而,作者在学习Perl的脚注中说

索引到数组不是使用Perl的优势.如果使用避免使用索引的pop,push和类似运算符,则代码通常比使用多个索引时更快,并且避免"逐个"错误,通常称为"fencepost"错误.有时,一个刚开始的Perl程序员(想要了解Perl的速度与C的比较)将采用针对C优化的排序算法(具有许多数组索引操作),在Perl中直接重写它(再次,使用许多索引操作)和想知道为什么它这么慢.答案是使用Stradivarius小提琴敲钉子不应该被认为是一种合理的构造技术.

当一个列表真的是一个阵列时,怎么会这样呢？我知道尝试将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必须执行更少的步骤,因此可以预期更快.

使用任何解释语言的诀窍是让它完成所有工作.