效率:数组与指针

Question

通过指针进行内存访问比通过数组进行内存访问更有效.我正在学习C,上面的内容在K&R中有说明.他们特别说

通过数组下标可以实现的任何操作也可以使用指针来完成.指针版本通常会更快

我使用visual C++解组了以下代码.(我是一个686处理器.我已禁用所有优化.)

int a[10], *p = a, temp;

void foo()
{
    temp = a[0];
    temp = *p;
}

令我惊讶的是,我看到通过指针的内存访问需要通过数组对内存访问所采用的两条指令.以下是相应的代码.

; 5    : temp = a[0];

    mov eax, DWORD PTR _a
    mov DWORD PTR _temp, eax

; 6    : temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

请帮我理解.我在这里失踪了什么？

---

正如许多答案和评论所指出的那样,我使用了编译时常量作为数组索引,从而使得通过数组访问变得更容易.下面是汇编代码,其中变量作为索引.我现在有相同数量的指令通过指针和数组进行访问.我更广泛的问题仍然很好.通过指针进行内存访问并不会使其本身更有效.

; 7    :        temp = a[i];

    mov eax, DWORD PTR _i
    mov ecx, DWORD PTR _a[eax*4]
    mov DWORD PTR _temp, ecx

; 8    : 
; 9    :    
; 10   :        temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

Answer 1

通过指针进行内存访问比通过数组进行内存访问更有效.

在编译器是相对愚蠢的野兽的过去,这可能是真的.您只需要gcc在高优化模式下查看一些代码输出,就可以知道它不再是真的.有些代码很难理解,但是一旦你做到了,它的亮度就很明显了.

一个不错的编译器将为指针访问和数组访问生成相同的代码,您可能不应该担心该级别的性能.编写编译器的人比我们凡人更了解他们的目标架构.在优化代码(算法选择等)时更专注于宏观层面,并相信您的工具制造者能够完成他们的工作.

事实上,我很惊讶编译器没有优化整个

temp = a[0];

由于temp在下一行中以不同的值重写了行,a因此不会被标记volatile.

我记得很久以前的城市神话中有关最新VAX Fortran编译器(显示我的年龄)的基准测试,其表现优于其竞争对手几个数量级.

原来,编译器发现基准计算的结果没有在任何地方使用,因此它将整个计算循环优化为遗忘.因此,运行速度大幅提高.

更新:优化代码在您的特定情况下更有效的原因是您找到位置的方式.a将在链接/加载时间确定的固定位置,并且将同时修复对它的引用.所以a[0]或者确实a[any constant]会在固定的位置.

p出于同样的原因,它本身也将处于固定的位置.但是 *p(内容p)是可变的,因此需要额外的查找才能找到正确的内存位置.

你可能会发现将另一个变量x设置为0(不是const)并且使用a[x]也会引入额外的计算.

在您的一条评论中,您说:

按照您的建议执行操作会产生3条通过数组进行内存访问的指令(获取索引,获取数组元素的值,存储在temp中).但我仍然无法看到效率.:-(

我的回应是,你很可能不会看到一个效率使用指针.现代编译器不仅可以确定数组操作和指针操作可以转换为相同的底层机器代码.

实际上,如果没有打开优化,指针代码的效率就会降低.请考虑以下翻译:

int *pa, i, a[10];

for (i = 0; i < 10; i++)
    a[i] = 100;
/*
    movl    $0, -16(%ebp)              ; this is i, init to 0
L2:
    cmpl    $9, -16(%ebp)              ; from 0 to 9
    jg      L3
    movl    -16(%ebp), %eax            ; load i into register
    movl    $100, -72(%ebp,%eax,4)     ; store 100 based on array/i
    leal    -16(%ebp), %eax            ; get address of i
    incl    (%eax)                     ; increment
    jmp     L2                         ; and loop
L3:
*/

for (pa = a; pa < a + 10; pa++)
    *pa = 100;
/*
    leal    -72(%ebp), %eax
    movl    %eax, -12(%ebp)            ; this is pa, init to &a[0]
L5:
    leal    -72(%ebp), %eax
    addl    $40, %eax
    cmpl    -12(%ebp), %eax            ; is pa at &(a[10])
    jbe     L6                         ; yes, stop
    movl    -12(%ebp), %eax            ; get pa
    movl    $100, (%eax)               ; store 100
    leal    -12(%ebp), %eax            ; get pa
    addl    $4, (%eax)                 ; add 4 (sizeof int)
    jmp     L5                         ; loop around
L6:
*/

从该示例中,您实际上可以看到指针示例更长,并且不必要地如此.它加载pa到%eax多次而不改变,实际上%eax在pa和之间交替&(a[10]).这里的默认优化基本上没有.

当您切换到优化级别2时,您获得的代码是:

    xorl    %eax, %eax
L5:
    movl    $100, %edx
    movl    %edx, -56(%ebp,%eax,4)
    incl    %eax
    cmpl    $9, %eax
    jle     L5

对于阵列版本,和:

    leal    -56(%ebp), %eax
    leal    -16(%ebp), %edx
    jmp     L14
L16:
    movl    $100, (%eax)
    addl    $4, %eax
L14:
    cmpl    %eax, %edx
    ja      L16

对于指针版本.

我不打算在这里对时钟周期进行分析(因为它太多了,我基本上都很懒)但我会指出一件事.在汇编程序指令方面,两个版本的代码没有太大差别,并且考虑到现代CPU实际运行的速度,除非您正在进行数十亿次这些操作,否则您不会注意到差异.我总是倾向于编写代码以便于阅读,而只是担心性能会成为一个问题.

顺便说一下,你引用的那句话:

5.3指针和数组:指针版本通常会更快,但至少对于没有经验的人来说,更难以立即掌握.

可以追溯到最早版本的K&R,包括我1978年的古老版本,其中的功能仍然是:

getint(pn)
int *pn;
{
    ...
}

从那时起,编译器已经走了很长的路.

Answer 2

如果您正在编写嵌入式平台,则可以快速了解指针方法比使用索引快得多.

struct bar a[10], *p;

void foo()
{
    int i;

    // slow loop
    for (i = 0; i < 10; ++i)
        printf( a[i].value);

    // faster loop
    for (p = a; p < &a[10]; ++p)
        printf( p->value);
}

慢循环必须每次计算一个+(i*sizeof(结构条)),而第二个只需要每次都将sizeof(结构条)添加到p.乘法运算比许多处理器上的加法使用更多的时钟周期.

如果你在循环中多次引用[i],你真的开始看到改进了.有些编译器不会缓存该地址,因此可能会在循环内多次重新计算.

尝试更新您的示例以使用结构并引用多个元素.

Answer 3

在第一种情况下,编译器直接知道数组的地址(也是第一个元素的地址)并访问它.在第二种情况下,他知道指针的地址并读取指针的值,该值指向该存储器位置.这实际上是一个额外的间接,所以它在这里可能更慢.

Answer 4

最重要的是在循环中获得速度.使用数组时,您将使用递增的计数器.要计算位置,系统将此计数器与数组元素的大小相乘,然后添加第一个元素的地址以获取地址.使用指针,您需要做的就是转到下一个元素是使用元素的大小增加当前指针以获得下一个元素,假设所有元素在内存中彼此相邻.

因此,指针算法在执行循环时需要少一些计算.此外,指向右元素的指针比使用数组中的索引更快.

然而,现代发展正逐渐摆脱许多指针操作.处理器越来越快,数组比指针更容易管理.此外,数组往往会减少代码中的错误数量.Array将允许索引检查,确保您不访问数组外的数据.

Answer 5

正如paxdiablo所说,任何新的编译器都会使它们非常相似.

更重要的是,我看到数组比指针更快的情况.这是在使用向量运算的DSP处理器上.

在这种情况下,使用数组类似于使用限制指针.因为通过使用两个数组,编译器 - 明确地 - 知道它们不指向相同的位置.但是如果你处理2指针,编译器可能会认为它们指向相同的位置并且将跳过管道衬里.

例如:

int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;

// fill a and b.
fill_arrays(a,b);

// set c[i] = a[i]+b[i];
for (i = 0; i<10; i++)
{
   c[i] = a[i] + b[i];
}

// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
   *pc++ = *pa++ + *pb++;
}

在案例1中,编译器将轻松地进行添加a和b的管道连接,并将值存储到c.

在情况2中,编译器不会管道,因为他可能在保存到C时覆盖a或b.

Answer 6

指针自然地表达简单的归纳变量,而下标本质上需要更复杂的编译器优化

在许多情况下,只使用下标表达式需要在问题中添加额外的图层.递增下标i的循环可以作为状态机,并且表达式a [i]在技术上需要,每次使用时,我乘以每个元素的大小并添加到基址.

为了将该访问模式转换为使用指针,编译器必须分析整个循环并确定,例如,正在访问每个元素.然后,编译器可以将下标乘以元素大小的多个实例替换为前一个循环值的简单增量.该过程结合了称为公共子表达式消除和感应变量强度降低的优化.

使用指针编写时,整个优化过程不是必需的,因为程序员通常只是逐步完成数组.

有时编译器可以进行优化,有时则不能.近年来,手头有一个复杂的编译器比较常见,因此基于指针的代码并不总是更快.

因为arrrays通常必须是连续的,所以指针的另一个优点是创建递增分配的复合结构.