在他的一个主题演讲中,Andrei Alexandrescu建议,在64位平台上,使用32位数组索引比使用原始指针更快:
第16页:http://www.slideshare.net/andreialexandrescu1/three-optimization-tips-for-c-15708507
在他的Facebook帐户上,他更精确,并说:"更喜欢数组索引到指针(这个似乎每十年逆转一次)."
我已经尝试了许多方法来找到差异,但我还没有设法构建任何显示这种差异的程序.知道安德烈,我不会感到惊讶,差异不超过百分之几,但如果有人找到这样的例子,我会很高兴.
这是我做过的测试.我选择n = 5000,足够大以获得合适的时序并且足够小以使一切都适合L1缓存.我循环了几次,以便CPU频率上升.
#include
#include
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(
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(
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(
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(
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(
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(
end_index_64 - start_index_64)
.count();
std::cout << "Index 64: " << time_index_64 << std::endl;
}
std::cout << std::endl;
}
delete[] p;
return 0;
}
这是我在我的机器(核心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
rici..
40
像这样的低级别建议(甚至来自Andrei Alexandrescu)的问题在于它忽略了编译器优化的事实.
现代编译器如此积极地(并且,通常,成功地)进行优化,以便尝试对它们进行二次猜测真正成为一个杯子的游戏.总的来说,编写清晰易读的代码将帮助您,您的同事和编译器分析代码.我真的相信这是最好的一般建议.
现代编译器使用的一个众所周知的优化是基于索引和基于指针的循环之间的转换.在您的基准测试的特定情况下,对于大多数优化设置,gcc将基于指针和基于32位索引的循环编译为相同的汇编程序输出.
在下文中,我替换为计时的东西++sentry在那里sentry是volatile为了减少代码大小.程序集输出对应于:
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指令和达夫设备向量化,但同样几乎是相同的.clang做了这个优化-O2
这些都没有否定这一点,即编译器可能需要更加努力地证明正在写入的指针不能修改任意内存.
但在这种情况下,就像在很多情况下一样,循环索引是一个局部变量,循环很简单,编译器可以完全分析它,从而允许强度降低,展开和向量化; 然后,控制变量是指针还是索引是无关紧要的.
一个更有趣的例子(可能)是两个数组的循环,其中基本元素的大小不同.鉴于以下两个功能:
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
但是,改变double和float对象其尺寸不再允许使用英特尔芯片的索引寻址模式,编译器再次基于索引的代码转换为基于指针的变量.
这里的代码基本上和以前一样,但是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
可能有必要补充一点,对于编译器来说,分析特定指针写入将修改哪个对象并不一定更困难.[ 编辑:亚历山大雷斯库在这里有一个引用,但它没有我想象的那么重要,所以我把它删除了,留下这部分主要是一个稻草人.
实际上,如果指针只被直接赋值为一次,而所有其他修改都是通过递增和递减操作(包括+=和-=),则编译器完全有权假设指针始终指向同一对象.如果指针的某些附加修改超出了某些其他对象,那将是Undefined Behavior,编译器可以放弃这种可能性.在流程图中跟踪assign和inc/dec操作很容易,因此在指针可以用索引表达式替换的情况下,编译器很可能想出这个并因此知道其他对象不是通过指针写入随机变异.
1> rici..：
像这样的低级别建议(甚至来自Andrei Alexandrescu)的问题在于它忽略了编译器优化的事实.
现代编译器如此积极地(并且,通常,成功地)进行优化,以便尝试对它们进行二次猜测真正成为一个杯子的游戏.总的来说,编写清晰易读的代码将帮助您,您的同事和编译器分析代码.我真的相信这是最好的一般建议.
现代编译器使用的一个众所周知的优化是基于索引和基于指针的循环之间的转换.在您的基准测试的特定情况下,对于大多数优化设置,gcc将基于指针和基于32位索引的循环编译为相同的汇编程序输出.
在下文中,我替换为计时的东西++sentry在那里sentry是volatile为了减少代码大小.程序集输出对应于:
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指令和达夫设备向量化,但同样几乎是相同的.clang做了这个优化-O2
这些都没有否定这一点,即编译器可能需要更加努力地证明正在写入的指针不能修改任意内存.
但在这种情况下,就像在很多情况下一样,循环索引是一个局部变量,循环很简单,编译器可以完全分析它,从而允许强度降低,展开和向量化; 然后,控制变量是指针还是索引是无关紧要的.
一个更有趣的例子(可能)是两个数组的循环,其中基本元素的大小不同.鉴于以下两个功能:
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
但是,改变double和float对象其尺寸不再允许使用英特尔芯片的索引寻址模式,编译器再次基于索引的代码转换为基于指针的变量.
这里的代码基本上和以前一样,但是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
可能有必要补充一点,对于编译器来说,分析特定指针写入将修改哪个对象并不一定更困难.[ 编辑:亚历山大雷斯库在这里有一个引用,但它没有我想象的那么重要,所以我把它删除了,留下这部分主要是一个稻草人.
实际上,如果指针只被直接赋值为一次,而所有其他修改都是通过递增和递减操作(包括+=和-=),则编译器完全有权假设指针始终指向同一对象.如果指针的某些附加修改超出了某些其他对象,那将是Undefined Behavior,编译器可以放弃这种可能性.在流程图中跟踪assign和inc/dec操作很容易,因此在指针可以用索引表达式替换的情况下,编译器很可能想出这个并因此知道其他对象不是通过指针写入随机变异.
第2段值得尽可能多的赞成.
2> P.P...：
他的(Andrei Alexandrescu)推理似乎是基于这样一个事实:对于编译器使用寄存器通常更难以编译,因为指针可能指向全局数据.但是我没有看到任何特定于32位数组索引的内容(对于我的阅读,幻灯片不是很清楚,如果他实际上是指32位数组或数组索引32位系统)
从马的嘴里:(是的,它是他的Facebook帐户的链接:)
最小化数组写入
为了更快,代码应该减少数组写入的数量,更一般地说,通过指针写入.
在具有大寄存器文件和充足的寄存器重命名硬件的现代机器上,您可以假设大多数命名的单个变量(数字,指针)最终都位于寄存器中.使用寄存器进行操作非常快,并且具有硬件设置的优势.即使数据依赖性 - 指令级并行性的主要敌人 - 发挥作用,CPU也有专用于管理各种依赖模式的特殊硬件.使用寄存器(即命名变量)操作是押注房子.做吧.
相反,在整个编译器 - 处理器 - 高速缓存层次结构中,数组操作(和通用间接访问)不太自然.除了一些明显的模式,数组访问没有注册.此外,每当涉及指针时,编译器必须假设指针可以指向全局数据,这意味着任何函数调用都可以任意改变指向数据.在阵列操作中,阵列写入是最糟糕的.鉴于具有内存的所有流量都是以缓存行粒度完成的,将一个字写入内存本质上是一个缓存行读取,后跟一个缓存行写入.因此,鉴于在很大程度上数组读取是不可避免的,这条建议归结为"尽可能避免数组写入.
他似乎也暗示,这是一般的建议,而不是使用数组索引总是更快(来自同一篇文章):
一些好的,但鲜为人知的快速代码要做的事情:
首选静态链接和位置相关代码(与PIC相反,与位置无关的代码).
首选64位代码和32位数据.
首选数组索引到指针(这个似乎每十年逆转一次).
喜欢常规的内存访问模式.最大限度地减少控制流量.
避免数据依赖.
3> InsideLoop..：
我给Andrei Alexandrescu发了一封电子邮件,他很友善地回复.这是他的解释:
"为了使加速可见,您需要利用ALU在一个周期内运行两个32位操作或一个64位操作的能力.并非每个基准测试都会显示加速."
我理解为"SIMD指令每个周期处理的数据多于32位数据而不是64位数据".我还没有找到一个基准(它不包含任何整数数组),它会产生影响.但我认为这将很难.安德烈曾经在Facebook工作,每一个百分比都值得.
这不适用于标量操作,但没有微阵列以这种方式分割64位ALU.P4E有点做了它(P4用32位做了它)和它奇怪的交错加法器,但它没有那个结果 - 两种尺寸的吞吐量是相同的.64位标量操作没有其他任何分裂.64位整数上的一些SIMD操作有时被分开,例如Pentium M上的PADDQ,128位寄存器上的SIMD操作经常被拆分(P3,PM,K8,Bobcat),后来又被拆分的256位(AMD)
嗯,那指甲.安德烈的优化建议应该是用盐砾.
京公网安备 11010802040832号