39

我一直在读到，在 C 中，使用指针算法通常比下标访问数组更快。即使使用现代（据说是优化的）编译器也是如此吗？

如果是这样，当我开始在 Mac 上从学习 C 转向 Objective-C 和Cocoa时，情况是否仍然如此？

在 C 和 Objective-C 中，哪种是数组访问的首选编码风格？哪个（由各自语言的专业人士）认为更清晰，更“正确”（因为没有更好的术语）？

4

11 回答 11

76

您需要了解此声明背后的原因。你有没有问过自己为什么它更快？让我们比较一些代码：

int i;
int a[20];

// Init all values to zero
memset(a, 0, sizeof(a));
for (i = 0; i < 20; i++) {
    printf("Value of %d is %d\n", i, a[i]);
}

它们都为零，真是令人惊讶：-P 问题是，a[i]在低级机器代码中实际上意味着什么？它的意思是

  1. 取a内存中的地址。

  2. 将i单个项目的大小乘a以该地址（int 通常是四个字节）。

  3. 从该地址获取值。

因此，每次从 中获取值时a，都会将 的基地址a添加到乘以i4 的结果中。如果你只是取消引用一个指针，步骤 1. 和 2. 不需要执行，只需要执行步骤 3。

考虑下面的代码。

int i;
int a[20];
int * b;

memset(a, 0, sizeof(a));
b = a;
for (i = 0; i < 20; i++) {
    printf("Value of %d is %d\n", i, *b);
    b++;
}

这段代码可能会更快......但即使是这样，差异也很小。为什么会更快？"*b" 与上面的第 3 步相同。但是，“b++”与第1步和第2步不一样。“b++”会将指针增加4。

（对新手很重要：++ 在指针上运行不会将指针在内存中增加一个字节！它会将指针在内存中增加与它指向的数据大小一样多的字节。它指向一个int并且 int是四个字节我的机器，所以 b++ 将 b 增加四！）

好的，但为什么会更快？因为将四加到指针上比乘以i四并将其加到指针上要快。无论哪种情况，您都有一个加法，但在第二种情况下，您没有乘法（您避免了一次乘法所需的 CPU 时间）。考虑到现代 CPU 的速度，即使阵列是 1 个 mio 元素，我想知道您是否真的可以对差异进行基准测试。

现代编译器可以将其中任何一个优化为同样快，您可以通过查看它产生的汇编输出来检查这一点。您可以通过将“-S”选项（大写 S）传递给 GCC 来实现。

这是第一个 C 代码的代码（-Os已使用优化级别，这意味着针对代码大小和速度进行优化，但不要进行会显着增加代码大小的速度优化，不同-O2和非常不同-O3）：

_main:
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    subl    $108, %esp
    call    ___i686.get_pc_thunk.bx
"L00000000001$pb":
    leal    -104(%ebp), %eax
    movl    $80, 8(%esp)
    movl    $0, 4(%esp)
    movl    %eax, (%esp)
    call    L_memset$stub
    xorl    %esi, %esi
    leal    LC0-"L00000000001$pb"(%ebx), %edi
L2:
    movl    -104(%ebp,%esi,4), %eax
    movl    %eax, 8(%esp)
    movl    %esi, 4(%esp)
    movl    %edi, (%esp)
    call    L_printf$stub
    addl    $1, %esi
    cmpl    $20, %esi
    jne L2
    addl    $108, %esp
    popl    %ebx
    popl    %esi
    popl    %edi
    popl    %ebp
    ret

与第二个代码相同：

_main:
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %edi
    pushl   %esi
    pushl   %ebx
    subl    $124, %esp
    call    ___i686.get_pc_thunk.bx
"L00000000001$pb":
    leal    -104(%ebp), %eax
    movl    %eax, -108(%ebp)
    movl    $80, 8(%esp)
    movl    $0, 4(%esp)
    movl    %eax, (%esp)
    call    L_memset$stub
    xorl    %esi, %esi
    leal    LC0-"L00000000001$pb"(%ebx), %edi
L2:
    movl    -108(%ebp), %edx
    movl    (%edx,%esi,4), %eax
    movl    %eax, 8(%esp)
    movl    %esi, 4(%esp)
    movl    %edi, (%esp)
    call    L_printf$stub
    addl    $1, %esi
    cmpl    $20, %esi
    jne L2
    addl    $124, %esp
    popl    %ebx
    popl    %esi
    popl    %edi
    popl    %ebp
    ret

嗯，这是不同的，这是肯定的。104 和 108 的数字差异来自变量b（在第一个代码中，堆栈上少了一个变量，现在我们多了一个，改变了堆栈地址）。for循环中真正的代码差异是

movl    -104(%ebp,%esi,4), %eax

相比

movl    -108(%ebp), %edx
movl    (%edx,%esi,4), %eax

实际上在我看来，第一种方法看起来更快（！），因为它发出一个 CPU 机器代码来执行所有工作（CPU 为我们完成所有工作），而不是有两个机器代码。另一方面，下面的两个汇编命令的运行时间可能比上面的要短。

作为结束语，我会说取决于您的编译器和 CPU 功能（CPU 提供什么命令以何种方式访问​​内存），结果可能是任何一种方式。任何一个都可能更快/更慢。除非您将自己完全限制在一个编译器（也意味着一个版本）和一个特定的 CPU 上，否则您无法确定。由于 CPU 在单个汇编命令中可以做越来越多的事情（很久以前，编译器确实必须手动获取地址，乘以i4，然后在获取值之前将两者相加），过去曾经是绝对真理的语句现在是现在越来越有问题了。还有谁知道 CPU 在内部是如何工作的？在上面，我将一个汇编指令与另外两个汇编指令进行了比较。

我可以看到指令的数量不同，并且此类指令所需的时间也可能不同。此外，这些指令在它们的机器表示中需要多少内存（毕竟它们需要从内存传输到 CPU 缓存）是不同的。但是，现代 CPU 不会按照您提供指令的方式执行指令。他们将大指令（通常称为 CISC）拆分为小的子指令（通常称为 RISC），这也使他们能够更好地优化程序流程以提高内部速度。事实上，第一条指令和下面的另外两条指令可能会导致相同的子指令集，在这种情况下，无论如何都没有可测量的速度差异。

关于Objective-C，它只是带有扩展的C。因此，所有适用于 C 的东西都适用于 Objective-C，就指针和数组而言也是如此。另一方面，如果您使用对象（例如，一个NSArray或NSMutableArray），这是一个完全不同的野兽。但是，在这种情况下，无论如何您都必须使用方法访问这些数组，没有指针/数组访问可供选择。

于 2008-10-24T11:31:32.263 回答
10

“使用指针算法通常比数组访问下标更快”

不。无论哪种方式都是相同的操作。下标是将（元素大小*索引）添加到数组的起始地址的语法糖。

也就是说，当迭代数组中的元素时，每次通过循环获取指向第一个元素的指针并增加它通常比每次从循环变量中计算当前元素的位置要快一些。（尽管这在现实生活中的应用程序中很重要。首先检查你的算法，过早的优化是万恶之源，等等）

于 2008-10-24T11:31:56.753 回答
5

这可能有点离题（抱歉），因为它没有回答您关于执行速度的问题，但您应该考虑过早优化是万恶之源（Knuth）。在我看来，特别是在（重新）学习语言时，一定要以最容易阅读的方式编写它。然后，如果您的程序运行正确，请考虑优化速度。无论如何，大多数情况下你的代码都会足够快。

于 2008-10-24T12:02:20.033 回答
4

Mecki 有一个很好的解释。根据我的经验，索引与指针之间通常很重要的一件事是循环中的其他代码。例子：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>

using namespace std;

typedef int64_t int64;
static int64 nsTime() {
  struct timespec tp;
  clock_gettime(CLOCK_REALTIME, &tp);
  return tp.tv_sec*(int64)1000000000 + tp.tv_nsec;
}

typedef int T;
size_t const N = 1024*1024*128;
T data[N];

int main(int, char**) {
  cout << "starting\n";

  {
    int64 const a = nsTime();
    int sum = 0;
    for (size_t i=0; i<N; i++) {
      sum += data[i];
    }
    int64 const b = nsTime();
    cout << "Simple loop (indexed): " << (b-a)/1e9 << "\n";
  }

  {
    int64 const a = nsTime();
    int sum = 0;
    T *d = data;
    for (size_t i=0; i<N; i++) {
      sum += *d++;
    }
    int64 const b = nsTime();
    cout << "Simple loop (pointer): " << (b-a)/1e9 << "\n";
  }

  {
    int64 const a = nsTime();
    int sum = 0;
    for (size_t i=0; i<N; i++) {
      int a = sum+3;
      int b = 4-sum;
      int c = sum+5;
      sum += data[i] + a - b + c;
    }
    int64 const b = nsTime();
    cout << "Loop that uses more ALUs (indexed): " << (b-a)/1e9 << "\n";
  }

  {
    int64 const a = nsTime();
    int sum = 0;
    T *d = data;
    for (size_t i=0; i<N; i++) {
      int a = sum+3;
      int b = 4-sum;
      int c = sum+5;
      sum += *d++ + a - b + c;
    }
    int64 const b = nsTime();
    cout << "Loop that uses more ALUs (pointer): " << (b-a)/1e9 << "\n";
  }
}

在基于 Core 2 的快速系统（g++ 4.1.2，x64）上，时间如下：

    简单循环（索引）：0.400842
    简单循环（指针）：0.380633
    使用更多 ALU（索引）的循环：0.768398
    使用更多 ALU（指针）的循环：0.777886

有时索引更快，有时指针算法更快。这取决于 CPU 和编译器如何能够流水线化循环执行。

于 2008-10-24T12:25:43.857 回答
3

如果您正在处理数组类型的数据，我会说使用下标使代码更具可读性。在今天的机器上（尤其是对于像这样简单的东西），可读的代码更为重要。

现在，如果您正在显式处理您 malloc() 的一大块数据，并且您想在该数据中获取一个指针，例如音频文件头中的 20 个字节，那么我认为地址算术更清楚地表达了您的意思试图做。

我不确定这方面的编译器优化，但即使下标速度较慢，它最多也只会慢几个时钟周期。当你可以从清晰的思路中获得更多收益时，这几乎不算什么。

编辑：根据其他一些回复，下标只是一个句法元素，对性能没有影响，就像我想的那样。在这种情况下，绝对要使用您试图通过访问指针指向的块内的数据来表达的任何上下文。

于 2008-10-24T11:31:54.803 回答
3

请记住，即使使用超标量 cpu 等查看机器代码，执行速度也很难预测

  • 乱序执行
  • 流水线
  • 分支预测
  • 超线程
  • ...

它不仅仅是计算机器指令，甚至不仅仅是计算时钟周期。在真正需要的情况下进行测量似乎更容易。即使计算给定程序的正确循环计数并非不可能（我们必须在大学里这样做），但这并不有趣而且很难做到正确。旁注：在多线程/多处理器环境中正确测量也很困难。

于 2008-10-24T12:18:38.660 回答
1

这不是真的。它与下标运算符一样快。在 Objective-C 中，您可以像在 C 和面向对象风格中那样使用数组，其中面向对象风格要慢得多，因为由于调用的动态特性，它在每次调用中都会进行一些操作。

于 2008-10-24T11:32:01.683 回答
1 
char p1[ ] = "12345";
char* p2 = "12345";

char *ch = p1[ 3 ]; /* 4 */
ch = *(p2 + 3); /* 4 */

C标准没有说哪个更快。在可观察的行为上是相同的，编译器可以按照它想要的任何方式来实现它。通常情况下，它甚至根本不会读取内存。

通常，除非您指定编译器、版本、体系结构和编译选项，否则您无法说出哪个“更快”。即使这样，优化也将取决于周围的环境。

所以一般的建议是使用任何能提供更清晰和更简单代码的东西。使用 array[ i ] 提供了一些工具来尝试查找索引超出范围的条件，因此如果您使用数组，最好将它们视为此类。

如果它很重要 - 查看编译器生成的汇编程序。但请记住，它可能会随着您更改围绕它的代码而改变。

于 2008-10-24T11:44:20.150 回答
1

不，使用指针算术并不是更快，而且很可能更慢，因为优化编译器可能会使用英特尔处理器上的 LEA（加载有效地址）等指令或其他处理器上的类似指令来进行指针算术，这比 add 或 add/mul 更快。它的优点是一次做几件事而不影响标志，而且它也需要一个周期来计算。顺便说一句，以下来自 GCC 手册。所以-Os主要不是针对速度进行优化。

我也完全同意themarko。首先尝试编写干净、可读和可重用的代码，然后考虑优化并使用一些 profiling 工具找到瓶颈。大多数时候，性能问题是与 I/O 相关的，或者是一些糟糕的算法或一些你必须寻找的错误。高德纳是男人 ;-)

我突然想到，你会用结构数组做什么。如果你想做指针运算，那么你肯定应该为结构的每个成员做。听起来是不是有点矫枉过正？是的，这当然是矫枉过正，也为掩盖错误打开了一扇大门。

-Os优化大小。Os启用通常不会增加代码大小的所有 O2 优化。它还执行旨在减少代码大小的进一步优化。

于 2008-10-24T12:32:34.683 回答
0

速度上不太可能有任何差异。

使用数组运算符 [] 可能是首选，因为在 C++ 中，您可以对其他容器（例如向量）使用相同的语法。

于 2008-10-24T11:33:12.883 回答
0

我已经为几个AAA游戏进行 C++/汇编优化 10 年了，我可以说，在我研究过的特定平台/编译器上，指针算法产生了相当大的差异。

作为一个透视的例子，我能够在我们的粒子生成器中创建一个非常紧密的循环，速度提高 40%，方法是用指针算法替换所有数组访问，这让我的同事完全不相信。以前我从我的一位老师那里听说它是一个很好的技巧，但我认为它不会对我们今天拥有的编译器/CPU 产生影响。我错了 ;）

必须指出的是，许多控制台ARM处理器没有现代CISC CPU 的所有可爱功能，而且编译器有时有点不稳定。

于 2016-03-01T22:12:18.580 回答