在64位平台上的效率:指针与32位数组索引

Andrei Alexandrescu在他的一个主题演讲中build议,在64位平台上,使用32位数组索引比使用原始指针快:

第16页: http : //www.slideshare.net/andreialexandrescu1/three-optimization-tips-for-c-15708507

在他的Facebook账户上,他更精确地说:“更喜欢数组索引来指针(这个似乎每十年都会颠倒)”。

我已经尝试了很多东西来find差异,但我还没有设法build立任何显示这种差异的程序。 知道安德烈,我不会感到惊讶的是,差距不会超过百分之几,但是如果有人find这样的例子,我会很高兴。

这是我做的一个testing。 我selectn = 5000,足够大,以获得一个体面的时间,足够小,使一切都适合一级caching。 我循环几次,使CPU频率上升。

#include <iostream> #include <chrono> int main(int argc, const char* argv[]) { const int n{5000}; int* p{new int[n]}; // Warm up the cache for (int i{0}; i < n; i++) { p[i] += 1; } for (int j{0}; j < 5; j++) { { auto start_pointer = std::chrono::high_resolution_clock::now(); for (int* q{p}; q != p + n; ++q) { ++(*q); } auto end_pointer = std::chrono::high_resolution_clock::now(); auto time_pointer = std::chrono::duration_cast<std::chrono::nanoseconds>( end_pointer - start_pointer) .count(); std::cout << " Pointer: " << time_pointer << std::endl; } { auto start_pointer = std::chrono::high_resolution_clock::now(); for (int* q{p}; q != p + n; ++q) { ++(*q); } auto end_pointer = std::chrono::high_resolution_clock::now(); auto time_pointer = std::chrono::duration_cast<std::chrono::nanoseconds>( end_pointer - start_pointer) .count(); std::cout << " Pointer: " << time_pointer << std::endl; } { auto start_index_32 = std::chrono::high_resolution_clock::now(); for (int i{0}; i < n; i++) { p[i] += 1; } auto end_index_32 = std::chrono::high_resolution_clock::now(); auto time_index_32 = std::chrono::duration_cast<std::chrono::nanoseconds>( end_index_32 - start_index_32) .count(); std::cout << "Index 32: " << time_index_32 << std::endl; } { auto start_index_32 = std::chrono::high_resolution_clock::now(); for (int i{0}; i < n; i++) { p[i] += 1; } auto end_index_32 = std::chrono::high_resolution_clock::now(); auto time_index_32 = std::chrono::duration_cast<std::chrono::nanoseconds>( end_index_32 - start_index_32) .count(); std::cout << "Index 32: " << time_index_32 << std::endl; } { const std::size_t n_64{n}; auto start_index_64 = std::chrono::high_resolution_clock::now(); for (std::size_t i{0}; i < n_64; i++) { p[i] += 1; } auto end_index_64 = std::chrono::high_resolution_clock::now(); auto time_index_64 = std::chrono::duration_cast<std::chrono::nanoseconds>( end_index_64 - start_index_64) .count(); std::cout << "Index 64: " << time_index_64 << std::endl; } { const std::size_t n_64{n}; auto start_index_64 = std::chrono::high_resolution_clock::now(); for (std::size_t i{0}; i < n_64; i++) { p[i] += 1; } auto end_index_64 = std::chrono::high_resolution_clock::now(); auto time_index_64 = std::chrono::duration_cast<std::chrono::nanoseconds>( end_index_64 - start_index_64) .count(); std::cout << "Index 64: " << time_index_64 << std::endl; } std::cout << std::endl; } delete[] p; return 0; } 

这是我的机器上得到的那种结果(core i7)。 我得到的只是“噪音”。

  Pointer: 883 Pointer: 485 Index 32: 436 Index 32: 380 Index 64: 372 Index 64: 429 Pointer: 330 Pointer: 316 Index 32: 336 Index 32: 321 Index 64: 337 Index 64: 318 Pointer: 311 Pointer: 314 Index 32: 318 Index 32: 319 Index 64: 316 Index 64: 301 Pointer: 306 Pointer: 325 Index 32: 323 Index 32: 313 Index 64: 318 Index 64: 305 Pointer: 311 Pointer: 319 Index 32: 313 Index 32: 324 Index 64: 315 Index 64: 303 

像这样的低层次的build议(甚至来自Andrei Alexandrescu)的问题是它忽略了编译器优化的事实。

现代编译器如此积极地进行优化(并且一般来说是成功的),以至于试图对它们进行第二次猜测,它确实成为了杯子的游戏。 总的来说,编写清晰可读的代码将帮助您,您的同事和编译器分析代码。 我真的相信这是最好的一般build议,可以给。

现代编译器使用的众所周知的优化之一是索引和基于指针的循环之间的转换。 在基准testing的特定情况下,对于大多数优化设置,gcc会将基于指针和基于32位索引的循环编译为相同的汇编程序输出。

在下面,我用++sentryreplace了++sentrysentryvolatile ,以减less代码的大小。 程序集输出对应于:

 for (int* q{p}; q != p + n; ++q) ++(*q); ++sentry; for (int i{0}; i < n; i++) p[i] += 1; 

-O2编译,这产生了以下结果:( %rdi%ebp仍然是从p填充的循环中初始化的)

  movq %rdi, %rdx cmpq %rcx, %rdi je .L10 .L16: addl $1, (%rdx) addq $4, %rdx cmpq %rcx, %rdx jne .L16 .L10: movl sentry(%rip), %eax movq %rdi, %rdx addl $1, %eax movl %eax, sentry(%rip) testl %ebp, %ebp jle .L8 .L14: addl $1, (%rdx) addq $4, %rdx cmpq %rdx, %rsi jne .L14 .L8: 

你可以看到在.L16.L14的循环之间没有任何区别。

当然,不同的优化设置会产生不同的结果。 使用-O3 ,循环使用SIMD指令和Duff的设备进行vector化,但是几乎完全相同。 铿锵在-O2做这个优化

没有一个人否认这一点,那就是编译器可能需要更努力地certificate正在写入的指针不能修改任意内存。

但在这种情况下,和许多情况一样,循环索引是一个局部variables,循环非常简单,编译器可以对其进行全面分析,从而可以减less强度,展开和向量化; 控制variables是指针还是索引是不相关的。


一个更有趣的例子(可能)是在两个数组的基础元素是不同大小的循环。 鉴于以下两个function:

 void d2f_ptr(float* out, const double* in, int n) { for (auto lim = out + n; out < lim;) *out++ = *in++; } void d2f_idx(float out[], const double in[], int n) { for (int i = 0; i < n; ++i) out[i] = in[i]; } 

gcc(v5.3.0,-O2)确实产生了不同的循环,基于索引的循环缩短了一个指令:

 d2f_ptr(float*, double const*, int): d2f_idx(float*, double const*, int): movslq %edx, %rdx xorl %eax, %eax leaq (%rdi,%rdx,4), %rax testl %edx, %edx cmpq %rax, %rdi jle .L16 jnb .L11 .L15: .L20: addq $4, %rdi pxor %xmm0, %xmm0 addq $8, %rsi cvtsd2ss (%rsi,%rax,8), %xmm0 pxor %xmm0, %xmm0 movss %xmm0, (%rdi,%rax,4) cvtsd2ss -8(%rsi), %xmm0 addq $1, %rax movss %xmm0, -4(%rdi) cmpq %rdi, %rax cmpl %eax, %edx ja .L15 jg .L20 .L11: .L16: ret ret 

但是将doublefloat更改为大小不再允许使用Intel芯片索引寻址模式的对象,编译器再次将基于索引的代码转换为基于指针的变体。

这里的代码基本上和以前一样,但是double被填充到48个字节:

 struct Big { double val; char padding[40]; }; struct Small { float val; Small& operator=(const Big& other) { val = other.val; return *this; } }; d2f_ptr(Small*, Big const*, int): d2f_idx(Small*, Big const*, int): movslq %edx, %rdx testl %edx, %edx leaq (%rdi,%rdx,4), %rax jle .L26 cmpq %rax, %rdi leal -1(%rdx), %eax jnb .L21 leaq 4(%rdi,%rax,4), %rax .L25: .L29: addq $48, %rsi pxor %xmm0, %xmm0 addq $4, %rdi addq $4, %rdi pxor %xmm0, %xmm0 cvtsd2ss (%rsi), %xmm0 cvtsd2ss -48(%rsi), %xmm0 addq $48, %rsi movss %xmm0, -4(%rdi) movss %xmm0, -4(%rdi) cmpq %rdi, %rax cmpq %rax, %rdi ja .L25 jne .L29 .L21: .L26: ret ret 

可能值得补充的是,对于编译器来说,分析哪个对象的特定指针将被修改并不一定更难。 [ 编辑 :亚历山大雷斯库在这里引用了一段话,但是并没有我想象的那么重要,所以我把它移除了,这个部分主要是一个稻草人。]

实际上,如果一个指针只被直接赋值一次,而所有其他的修改都是通过递增和递减操作(包括+=-= ),那么编译器完全有权假定指针总是指向相同的目的。 如果指针的一些附加修改超过了其他对象,这将是未定义的行为,编译器可以放弃这种可能性。 在stream程图中跟踪分配和增加/减less操作是很容易的,因此在指针可能被索引expression式replace的情况下,编译器很有可能知道这一点,从而知道其他对象不是通过指针写入随机变异。

他(Andrei Alexandrescu)的推理似乎是基于这样一个事实,即使用指针variables的寄存器通常比较难以编译,因为指针可能指向全局数据。 但我没有看到32位数组索引的具体内容(就我的阅读而言,如果他实际上是指32位数组或索引32位系统)

从马的嘴里 (是的,这是他的Facebook帐户的链接:)

最小化arrays写入

为了更快,代码应该减lessarrays写入的次数,更一般地说,通过指针写入。

在具有大寄存器文件和充足的寄存器重命名硬件的现代机器上,可以假定大多数命名的单个variables(数字,指针)最终位于寄存器中。 使用寄存器操作速度很快,并发挥硬件设置的优势。 即使在数据依赖性(指令级并行性的主要敌人)发挥作用时,CPU也有专门的硬件来pipe理各种依赖模式。 与寄存器(即命名variables)操作赌注在房子上。 这样做。

相比之下,数组操作(和一般间接访问)在整个编译器 – 处理器 – caching层次结构中不那么自然。 除了一些明显的模式,数组访问没有注册。 另外,每当涉及指针时,编译器必须假定指针可指向全局数据,这意味着任何函数调用都可能随意更改指向的数据。 在arrays操作中,arrays写入是最差的。 考虑到所有带有内存的stream量都是以高速caching线粒度完成的,写入一个字到内存本质上是一个高速caching行读取,然后写入高速caching行。 所以在很大程度上,数组读取是不可避免的,这个build议归结为“尽可能避免数组写入”。

他似乎也build议,这是一般性build议,而不是总是更快地使用数组索引(来自同一篇文章):

一些好的,但不太为人所知的事情要做的快速代码:

首选静态链接和位置相关的代码(而不是PIC,位置无关的代码)。
首选64位代码和32位数据。
更喜欢数组索引到指针(这个似乎每10年反转一次)。
优先考虑正规的内存访问模式。 最大限度地减less控制stream量。
避免数据依赖。

我给Andrei Alexandrescu写了一封电子邮件,他很友善地回复。 这是他的解释:

“为了加速可视化,您需要利用ALU在一个周期内运行两个32位操作或一个64位操作的能力,而不是每个基准都会显示加速。

我理解为“SIMD指令每个周期用32位数据比64位数据处理更多的数据”。 我还没有find一个基准(不包含任何整数数组),在哪里有所作为。 但我认为这将是困难的。 安德烈曾经为Facebook工作,每一个百分比值得。

不完全是一个答案,但太复杂的评论:

你的testing是一个非常有限的指针运算与数组索引的testing; 在简单的情况下, 每次编译器都会对其优化产生相同的程序集。 当索引variables没有被使用时,编译器可以完全自由地切换到程序集中的指针运算,如果它select的话,同样可以将指针运算切换回数组访问。

我能想出的最好的例子是几年前(也许从编译器到编译器,架构到架构等都不一致)。 我正在玩(为了学习的目的)两个版本的基本上相当于数组复制操作的代码:

 for (unsigned i = 0; i < copycnt; ++i) { x[i] = y[i]; } 

 while (copycnt--) { *x++ = *y++; } 

我猜测有一些复杂的因素(或编译器优化已经改变,因为上次我testing了这样的高优化编译到相同的程序集),但即使编译器可以平凡地将第一种情况转换为第二种理论上保存一个寄存器,避免偏移加载和存储指令,转而支持直接加载和存储指令,使用cmpl为0而不是两个cmpl值,因为添加一个递减指令的成本很小),编译器select编译代码大致可以近似为:

 const ptrdiff_t diff = y - x; decltype(*x) *const end = x + copycnt; while (x < end) { *x = *(x + diff); ++x; } 

如果你计算循环中需要的寄存器的数量,循环中的指令的数量(假设在固定寄存器偏移处的装载是一个组合的指令,因为它是在x86机器上),那么这可能优于代码的“正常”版本而不是直接加载)等等,编译器肯定是这么想的,因为它select了这个版本而不是直接的指针算术(任何编译器都可以在这里完成)。

但是当我编译简单的指针算术代码时,编译器找不到这种关系(可能是由于这个简化版本中没有出现一些复杂的因素;我不知道xycopycnt是否被再次使用,所以它不是一个保留原始值的问题),并且或多或less地按照我给出的内容来编译,两个指针独立地递增。

我的理论是,索引的使用为编译器提供了我在做的事情。 它不是两个不相关的指针,它是通过一个通用索引访问的两个“数组”,它知道如何改进该模式的编译代码。 指针算术是“做我说的”,没有给出“我正在做什么”的上下文,而编译器也找不到它,所以它没有优化它。

无论如何,显然只是轶事,但我认为这个例子是更复杂的可能性的代表; 数组索引为编译器提供了更多关于你正在做什么的“更高的逻辑”的信息,在这里指针算术说明了要做什么,而不是为什么要做,所以编译器有更难的时间优化,这可能解释了build议。 希望能帮助到你。

这种types的优化只是在金属级别,你应该忽略它们。 我会更专注于其他的事情,实际上会给你的testing带来噪音

[问题]

  1. 指针赋值是用++(*q) ,而对于整型来说,它的执行速度更快(*q)++ ,但无论如何你应该和int32 / int64testing一致并且做*q+=1
  2. 指针testing每次在你的循环中计算结束指针,你应该这样做一次int * ep{p+n}并检查它。
  3. 在整数testing中,您不应该使用< but !=进行终止评估。
  4. 只运行五次将不会提供足够的原理图。
  5. 您必须设置cpu亲和力
  6. 你应该做更多的循环,并只占最后一个
  7. 你应该有一个编译器已经编译到金属的系统
  8. 你不应该像你那样“预热caching”
  9. 你应该随机化你的input。

我已经改变了你的代码,你可以从这里检索它。

你应该编译:

g++ -O3 -march=native --std=c++11 -o intvsptr

并与启动

taskset 0x00000001 ./intvsptr

然后你应该得到一致的结果。

指针:4396指针:4397索引32:4395索引32:4394索引64:4394索引64:4395

指针:4395指针:4397索引32:4397索引32:4395索引64:4393索引64:4396

指针:4395指针:4397索引32:4396索引32:4394索引64:4394索引64:4396

指针:4396指针:4397索引32:4397索引32:4395索引64:4394索引64:4395

指针:4395指针:7698索引32:4471索引32:4422索引64:4425索引64:4407

指针:4399指针:4416索引32:4394索引32:4393索引64:4399索引64:4412

这个testing的精度应该是最后一位数字,但通常应该做一个广泛的统计分析。

我已经粘贴了一次执行的最后几次,但是做了多次,我认为可以肯定的是,只要这个微基准允许指针运算速度更快,或者在最坏的情况下运行速度稍微慢一些

无论如何,您可以忽略这种types的提示 ,这些提示可能在很久以前就已经变得重要了,但是与当前的编译器无关