通过指针算法访问数组值与C中的订阅

你需要了解这个索赔背后的原因。你有没有问过自己为什么速度更快?让我们比较一些代码:

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 乘以单个项目的大小 一 到那个地址(int通常是四个字节)。

3. 从那个地址取值。

所以每次你从 一 ,的基址 一 添加到 我 到四点。如果只是取消对指针的引用,请执行步骤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增加4!)

好吧,但是为什么会更快呢?因为在指针上加四比乘快 我 四个,再加上一个指针。在这两种情况下都有一个加法,但在第二种情况下,没有乘法(避免了一次乘法所需的CPU时间)。考虑到现代CPU的速度,即使阵列是1 mio元素,我想知道您是否真的可以对差异进行基准测试。

现代编译器可以同样快速地优化其中一个,这是您可以通过查看它生成的程序集输出来检查的。您可以通过将“-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可以在单个汇编命令中做越来越多的工作(很久以前,编译器确实必须手动获取地址,乘以 我 四个一组,加起来再求出价值),过去是绝对真理的说法现在越来越令人怀疑。还有谁知道CPU如何在内部工作?上面我比较了一个组装说明和另外两个组装说明。

我可以看到指令的数量是不同的,这样的指令需要的时间也可以不同。另外,这些指令在其机器表示中需要多少内存(毕竟它们需要从内存传输到CPU缓存)是不同的。然而,现代的CPU不会像您输入指令那样执行指令。将大指令(通常称为cisc)拆分为小的子指令(通常称为risc),这也使它们能够更好地优化内部的程序流以提高速度。实际上,下面的第一个、单个指令和其他两个指令可能会导致 相同的子指令集 在这种情况下,没有任何可测量的速度差。

关于objective-c,它只是带有扩展名的c。所以,对于C来说,所有正确的东西对于Objective-C,以及指针和数组来说都是正确的。如果在另一方面使用对象(例如, NSArray 或 NSMutableArray )这是完全不同的野兽。但是,在这种情况下,您无论如何都必须使用方法访问这些数组,没有可供选择的指针/数组访问。

“使用指针算术通常是 比订阅数组快 “访问”

不。这两种方法都是一样的。订阅是将(元素大小*索引)添加到数组的起始地址的语法糖。

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

这可能有点离题(抱歉),因为它没有回答您关于执行速度的问题,但您应该考虑一下 过早的优化是万恶之源。 (Knuth)在我看来,特别是当你还在学习这门语言的时候,一定要先用最容易阅读的方式来写。 然后,如果你的程序运行 对的 ,考虑优化速度。 不管怎样,大多数时候你的代码都足够快。

麦基有一个很好的解释。根据我的经验,索引与指针经常关系到的事情之一就是其他代码在循环中所处的位置。例子:

#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";
  }
}

在基于2核的快速核心系统(G++4.1.2,X64)上,以下是时间安排:

    Simple loop (indexed): 0.400842
    Simple loop (pointer): 0.380633
    Loop that uses more ALUs (indexed): 0.768398
    Loop that uses more ALUs (pointer): 0.777886

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

如果您处理的是数组类型的数据,我会说使用下标使代码更可读。在今天的机器上(特别是对于这样简单的东西),可读代码更重要。

现在,如果您显式地处理一块malloc()d的数据,并且希望在该数据中获得一个指针,比如说音频文件头中的20个字节,那么我认为地址算法更清楚地表达了您要做的事情。

在这方面,我不确定编译器的优化,但即使订阅速度较慢,最多也只会慢几个时钟周期。当你能从思路的清晰中获得更多的东西时,这几乎不是什么。

编辑:根据一些其他的回答,订阅只是一个语法元素,对性能没有影响,就像我想象的那样。在这种情况下,无论您试图通过指针指向的块内的访问数据来表示什么上下文,都必须使用它。

请记住,即使在使用超标量CPU之类的设备代码时,执行速度也很难预测。

• 不正常的执行
• 流水线技术
• 分支预测
• 超线程
• …

这不仅仅是计算机器指令,甚至不仅仅是计算时钟周期。 在实际需要的情况下,似乎更容易测量。即使不可能计算出一个给定程序的正确循环计数(我们在大学里必须这样做),但是很难找到正确的循环计数。 旁注:在多线程/多线程处理器环境中,正确测量也很困难。

char p1[ ] = "12345";
char* p2 = "12345";

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

C标准没有说明哪个更快。在可观察的行为上是相同的,编译器可以根据自己的需要以任何方式实现它。通常,它甚至根本看不到内存。

一般来说,除非指定编译器、版本、体系结构和编译选项,否则无法确定哪个更快。即便如此,优化仍将取决于周围的环境。

因此,一般的建议是使用能够提供更清晰和更简单代码的任何代码。使用数组[i]提供了一些工具,可以尝试查找超出限制条件的索引,因此,如果使用数组,最好将其视为这样。

如果它是关键的-请查看编译器生成的汇编程序。但请记住,当您更改围绕它的代码时,它可能会更改。

不,使用指针算法不是更快,也可能更慢,因为优化编译器可能会在英特尔处理器上使用LEA(加载有效地址)指令,或在其他处理器上使用类似的指令,以实现比加法或加法/乘法更快的指针算法。它的优点是一次做几件事情而不影响标记,而且计算也需要一个周期。顺便说一句,以下内容摘自GCC手册。所以 -Os 不会主要针对速度进行优化。

我也完全同意市场。首先尝试编写干净、可读和可重用的代码,然后考虑优化,并使用一些分析工具来找到瓶颈。大多数时候,性能问题都与I/O相关,或者是一些糟糕的算法,或者是一些你必须找到的bug。 Knuth 就是那个人;

我刚刚想到,您将如何处理结构数组。如果您想做指针算术,那么您肯定应该为结构的每个成员做它。听起来像是杀戮过度?是的,当然它是杀伤力过大的,而且它为隐藏的虫子打开了一扇大门。

-操作系统 优化尺寸。 Os 启用通常不会增加代码大小的所有O2优化。它还执行进一步的优化,以减少代码大小。

速度不太可能有差别。

使用数组运算符[]可能是优选的,如C++中,可以使用与其他容器(例如向量)相同的语法。

这不是真的。它和下标操作符一样快。在Objective-C中,您可以使用类似于C中的数组,也可以使用面向对象的样式,因为它在每次调用中都会由于调用的动态特性而进行一些操作。

我已经为10年的AAA标题做了C++ /汇编优化,我可以说 特定平台/编译器 我已经研究过了,指针算术有相当大的差别。

作为一个透视事物的例子,我能够在粒子发生器中以40%的速度做一个非常紧密的循环,用指针算法替换所有数组访问,完全不相信我的同事。我从我的一位老师那里听说这是一个很好的诀窍,但我认为这不会对我们今天的编译器/CPU产生任何影响。我错了;

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