63

据说通过指针访问内存比通过数组访问内存更有效。我正在学习 C，以上内容在 K&R 中有所说明。他们特别说

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

我使用 Visual C++ 反汇编了以下代码。（我的是 686 处理器。我已禁用所有优化。）

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

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

令我惊讶的是，我看到通过指针访问内存需要 3 条指令，而通过数组访问内存需要 3 条指令。下面是对应的代码。

; 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
4

14 回答 14

77

据说通过指针访问内存比通过数组访问内存更有效。

在过去编译器是相对愚蠢的野兽时，这可能是正确的。您只需要查看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%eaxpa&(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;
{
    ...
}

从那时起，编译器已经走了很长一段路。

于 2010-02-21T12:01:38.363 回答
11

如果您正在编写嵌入式平台，您很快就会了解到指针方法比使用索引要快得多。

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(struct bar))，而第二个循环每次都必须将 sizeof(struct bar) 添加到 p。在许多处理器上，乘法运算比加法运算使用更多的时钟周期。

如果您在循环内多次引用 a[i]，您真的会开始看到改进。一些编译器不缓存该地址，因此可能会在循环内多次重新计算。

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

于 2010-02-21T15:49:24.373 回答
8

指针自然地表达简单的归纳变量，而下标在某种程度上需要更复杂的编译器优化

在许多情况下，仅使用下标表达式需要在问题中添加额外的层。增加下标i的循环可以看作是一个状态机，并且表达式a[i]在技术上要求，每次使用它时，将i乘以每个元素的大小并添加到基地址。

为了将该访问模式转换为使用指针，编译器必须分析整个循环并确定，例如，每个元素都被访问。然后编译器可以用前一个循环值的简单增量来替换将下标乘以元素大小的多个实例。这个过程结合了称为公共子表达式消除和归纳变量强度减少的优化。

使用指针编写时，不需要整个优化过程，因为程序员通常会单步执行数组以开始。

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

因为数组通常必须是连续的，所以指针的另一个优点是创建增量分配的复合结构。

于 2010-02-22T00:09:03.770 回答
8

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

于 2010-02-21T12:00:28.350 回答
8

The speed is gained in loops, most of all. When you use an array, you would use a counter which you increment. To calculate the position, the system multiplies this counter with the size of the array element, then adds the address of the first element to get the address. With pointers, all you need to do to go to the next element is to increase the current pointer with the size of the element to get the next one, assuming all elements are next to each other in-memory.

Pointer arithmetic thus takes a bit less calculations when doing loops. Also, having pointers to the right element is faster than using an index within an array.

Modern development is slowly getting rid of many pointer operations, though. Processors are getting faster and faster and arrays are easier to manage than pointers. Also, arrays tend to reduce the amount of bugs in code. Array will allow index checks, making sure you're not accessing data outside the array.

于 2010-02-21T12:19:51.833 回答
7

As paxdiablo said, Any new compiler will make them very similar.

Even more, I saw situations where array was faster then pointers. This was on a DSP processor which uses vector operations.

In this case, using arrays was similar to using restrict pointers. Because by using two arrays the compiler -implicitly- knows that they don't point to the same location. But if you deal with 2 pointer, the compiler may think that they point to same location and will skip pipe lining.

for example:

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++;
}

In case 1, the compiler will easily do pipe-lining of adding a and b, and storing value to c.

In case 2, the compiler will not pipe-line, because he might be overwriting a or b while saving to C.

于 2010-02-21T12:21:08.823 回答
3

这是一个很老的问题，已经回答了，所以我不需要回答！但是，我没有注意到一个简单的答案，所以我提供了一个。

回答：间接访问（指针/数组）“可能”添加一条额外的指令来加载（基）地址，但之后的所有访问（数组中的元素/指向结构的指针中的成员）应该只是一条指令因为它只是在已经加载的（基）地址上增加了一个偏移量。因此，在某种程度上，它将与直接访问一样好。因此，在大多数情况下，通过数组/指针访问是等效的，元素访问也与直接访问变量一样好。

前任。如果我有一个包含 10 个元素的数组（或指针）或一个包含 10 个成员的结构（通过指向该结构的指针访问），并且我正在访问一个元素/成员，则在开始时只需要一个可能的附加指令。之后所有的元素/成员访问应该只是一条指令。

于 2013-08-02T21:46:45.820 回答
2

您在这里的问题得到了很好的答案，但是由于您正在学习，因此值得指出的是，该级别的效率很少引起注意。

当您调整程序以获得最佳性能时，您至少应该尽可能多地注意发现和修复程序结构中的更大问题。在这些被修复之后，低级优化可以产生进一步的影响。

这是一个如何做到这一点的示例。

于 2010-02-21T21:27:58.983 回答
2

指针过去比数组快。当然，当 C 语言被设计时，指针要快得多。但是现在，优化器通常可以比使用指针更好地优化数组，因为数组受到更多限制。

现代处理器的指令集也旨在帮助优化阵列访问。

所以底线是现在数组通常更快，尤其是在带有索引变量的循环中使用时。

当然，您仍然希望将指针用于链接列表之类的东西，但是过去将指针遍历数组而不是使用索引变量的优化现在可能是一种反优化。

于 2010-02-21T21:37:35.877 回答
1

“指针版本通常会更快”意味着在大多数情况下，编译器更容易生成具有指针（只需要取消引用）的更高效的代码，而不是具有数组和下标（这意味着编译器需要从数组的开头移动地址）。然而，对于现代处理器和优化编译器，典型情况下的数组访问并不比指针访问慢。

特别是在您的情况下，您需要打开优化，以获得相同的结果。

于 2010-02-21T12:04:48.500 回答
1

由于 0 被定义为常量，所以 a[0] 也是常量，编译器在编译时就知道它在哪里。在“正常”情况下，编译器必须从基数+偏移量计算元素地址（偏移量根据元素大小进行缩放）。

OTOH，p是一个变量，间接需要额外的移动。

一般来说，无论如何，数组索引在内部都是作为指针算术处理的，所以我不确定 K&R 试图提出的观点。

于 2010-02-21T12:05:03.480 回答
1

由于大多数人已经给出了详细的答案，所以我只是举一个直观的例子。如果更大规模地使用数组和指针，使用指针的效率会更显着。例如，如果您想通过将一个大的 long int 数据集排序为几个子集，然后将它们合并来排序。

long int * testData = calloc(N, sizeof(long int));

对于 2017 年每天 8G 内存的机器，我们可以设置N为 400000000，这意味着你将使用大约 1.5G 的内存来存储这个原始数据集。如果你正在使用MPI，你可以通过使用快速分离你的数据

MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);

您可以简单地将paritionLength其视为存储N/number_of_thread每个相同部分的长度的指针，并将partitionIndex其视为存储 N/number_of_threads 递增地盯着索引的指针。假设你有一个 4 核 CPU，并且你只将你的工作分成 4 个线程。MPI肯定会通过参考快速完成这项工作。但是如果你使用数组，这个例程必须在数组上运行一个指针算法来首先找到分区点。这不像指针那么直接。此外，当您合并分区数据集时，您可能希望使用K-way merge加速。您需要一个临时空间来存储四个排序的数据集。在这里，如果使用指针，则只需要存储4个地址。但是，如果使用数组，它将存储 4 个完整的子数组，效率不高。有时，如果您没有使用MPI_Barrier来确保您的程序是线程安全的，MPI甚至可能会抱怨您的内存实现很糟糕。我得到了一台 32G 机器，通过数组方法和指针方法在 8 个线程上对 400000000 个 long 值进行排序，我得到了 11.054980s 和 13.182739s 相应的。如果我将大小增加到 1000000000，如果我使用数组，我的排序程序将无法成功执行。这就是为什么很多人对除 C 中的标量之外的每个数据结构都使用指针的原因。

于 2017-05-03T22:55:01.373 回答
0

我对 ptr 比数组讨论更快感到有些惊讶，其中证据表明情况并非如此，最初由 Abhijith 的 asm 代码给出。

mov eax，dord ptr _a；// 直接从地址 _a 加载值

对比

mov eax, dword ptr _p; // 将 p 的地址/值加载到 eax

和

mov ecx, dword ptr [eax]; // 使用加载的地址访问值并放入 ecx

数组代表一个固定地址，因此 cpu 可以直接访问它，而不是 ptr 需要取消引用才能让 cpu 访问该值！

第二批代码不可比较，因为必须计算数组偏移量，为了对 ptr 执行此操作，您还需要至少多 1/2 的指令！

编译器在编译期间可以推断出的任何东西（固定地址、偏移量等）都是高性能代码的关键。比较迭代代码并分配给变量：

大批：

; 第2791章

mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx

对比

PTR

; 第2796章

mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx

加

; 2801：++p；

mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax

与 Array 使用地址并同时获取值相比，它只是用于 ptr 加载地址而不是使用它！

此致

于 2018-06-06T11:12:44.493 回答
0

数组与指针的效率：向量化的情况

如果您使用的是gcc之类的编译器，那么在点上使用数组以从自动矢量化的收益中获利可能会很有意义：

基本块矢量化，又名 SLP，由标志 -ftree-slp-vectorize 启用，并且需要与循环矢量化相同的平台相关标志。默认情况下，基本块 SLP 在 -O3 和 -ftree-vectorize 启用时启用。

不可向量化的循环

当前无法矢量化的循环示例：

示例 1：不可数循环：


while (*p != NULL) {
  *q++ = *p++;
}

矢量化循环

“feature”表示示例演示的矢量化功能。

示例 1：

int a[256], b[256], c[256];
foo () {
  int i;

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

底线

因此，尽管许多人会告诉您指针或数组更好，但最好的是，一如既往：

  • 用最好的标志编译你的代码
  • 使用编译器资源管理器检查生成的字节码
  • 最后对实际运行速度进行基准测试。
于 2021-03-02T21:21:50.150 回答