深入理解计算机系统小班讨论课:寄存器溢出问题的原理、对性能的影响(register spilng)
《深入理解计算机系统》第5章的5.11.1介绍了寄存器溢出(register spilng)问题,请结合教材给出的简单实例,阐释为什么会出现寄存器溢出问题?寄存器溢出问题为什么会影响性能?但实际上我们在进行高级语言编程的时候根本无需考虑这个问题,为什么?试简单阐释系统内部谁、如何解决寄存器溢出问题。
一、 寄存器溢出的原理
首先我们回顾一下什么是寄存器。寄存器是CPU内部的元件,包括通用寄存器、专用寄存器和控制寄存器。寄存器拥有非常高的读写速度,所以在寄存器之间的数据传送非常快。
我们已经知道,通过引入临时的累积变量,消除不必要的存储器引用,可以提高程序性能。“消除不必要的存储器引用”可以提高程序性能,其原因即在于寄存器的读写速度远优于存储器。
在上者的基础上,通过将一组合并运算分割成多个部分,最后合并结果,即引入多个累计变量提高程序并行性,可以进一步提高程序性能。比如:
通常我们这么写代码:
void sumAnswer(long int *sum) {
int i=0;
for(i=0; i<100000; i++)
*sum+=num[i];
}
但我们可以这样改进:
void sumAnswer(long int *sum) {
int i;
long int acc0=0;
long int acc1=0;
long int acc2=0;
for(i=0 ;i<10000; i+=3) {
acc0=acc0+num[i];
acc1=acc0+num[i];
acc2=acc0+num[i];
}
*sum=(acc0+acc1+acc2);
}
我们可以看到,区别于通常的for(i=0; i<10000; i++),这里每次i加三,在循环内部通过三个临时的累积变量存储结果。这三个累计变量直接存储到三个寄存器中,而不是每次循环都要读写存储器,因此执行效率大大提升。这一点我们之后会进行验证。
在前面分析的基础上,我们又知道,IA32指令集只有少量寄存器可用于存放累积的值。会不会出现累计变量过多、寄存器“不够用”的情况呢?因此,我们通过如下程序验证:
#include <stdio.h>
int num[10006];//注意这里为了防止越界,我多定义了一些空间
void sumAnswer(long int *sum) {
int i;
long int acc0=0;
long int acc1=0;
long int acc2=0;
long int acc3=0;
long int acc4=0;
long int acc5=0;
for(i=0 ;i<10000; i+=6) {//循环展开六次,使用六个累积变量
acc0=acc0+num[i];
acc1=acc0+num[i];
acc2=acc0+num[i];
acc3=acc0+num[i];
acc4=acc0+num[i];
acc5=acc0+num[i];
}
*sum=(acc0+acc1+acc2+acc3+acc4+acc5);
}
int main() {
int i;
srand((unsigned int)time(NULL));
for(i=0; i<10010; i++)
num[i]=rand()%1000;//这里我随机生成一个数组
long int sum;
sumAnswer(&sum);//通过指针,直接改变值
return 0;
}
在命令行输入如下指令:
gcc -g spilling.c -o spilling
gdb ./spilling
list
disass sumAnswer
查看sumAnswer函数的反汇编代码,观察到结果为:
我们可以看到,每次相加后的结果分别保存到-0x8(%ebp)、-0xc(%ebp)、-0x10(%ebp)、-0x14(%ebp)、-0x1c(%ebp),这是栈帧中的连续存储空间,而不是寄存器,表明编译器并没有允许寄存器存储临时变量!
在64位系统下查看反汇编代码(上图)、将加法更改为乘法、将临时变量的定义不放在一起依旧如此。
那么,在什么时候编译器允许寄存器存储临时变量呢?
答案是:需要开启O2优化选项!
gcc -g -O2 spilling.c -o spilling
编译上面的代码,得到反汇编代码为:
可以清楚看到,每次相加的结果存储到了寄存器edx中!
我们得到这样一个结论:默认的编译选项不提供“消除不必要的存储器引用”的机制,所有局部变量按定义顺序存储在栈中,每次读写时需要从存储器中访问并写回存储器。
接下来,我们来分析寄存器溢出与溢出的情况。我用三个累积变量:
得到反汇编代码:
分析得到:
此时没有出现寄存器溢出问题。我们改为使用6个累积变量:
得到反汇编代码:
分析得到:
因此,我们得到结论:IA32指令集提供4个寄存器存放累积的值,它们分别是:%ecx %edx %edi %esi。当我们的并行度超过了可用的寄存器数量时,就会发生寄存器溢出。
二、 寄存器溢出对性能的影响
原理上:发生寄存器溢出时,编译器会将结果溢出到栈中。程序需要在内存中读写这些变量,会抵消使用多个值并行累积所获得的好处,并行积累的优势就可能消失。
编程验证:测试并行度为自0到8的程序运行时间。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long int num[100020];
void sum0(long int *r) {
int i=0;
for(i=0; i<100000; i++)
*r+=num[i];
}
void sum1(long int *r) {
int i=0;
long int acc;
for(i=0; i<100000; i++)
acc+=num[i];
*r=acc;
}
void sum2(long int *r) {
int i=0;
long int acc0,acc1;
for(i=0; i<100000; i+=2) {
acc0+=num[i];
acc1+=num[i+1];
}
*r=acc0+acc1;
}
void sum3(long int *r) {
int i=0;
long int acc0,acc1,acc2;
for(i=0; i<100000; i+=3) {
acc0+=num[i];
acc1+=num[i+1];
acc2+=num[i+2];
}
*r=acc0+acc1+acc2;
}
void sum4(long int *r) {
int i=0;
long int acc0,acc1,acc2,acc3;
for(i=0; i<100000; i+=4) {
acc0+=num[i];
acc1+=num[i+1];
acc2+=num[i+2];
acc3+=num[i+3];
}
*r=acc0+acc1+acc2+acc3;
}
void sum5(long int *r) {
int i=0;
long int acc0,acc1,acc2,acc3,acc4;
for(i=0; i<100000; i+=5) {
acc0+=num[i];
acc1+=num[i+1];
acc2+=num[i+2];
acc3+=num[i+3];
acc4+=num[i+4];
}
*r=acc0+acc1+acc2+acc3+acc4;
}
void sum6(long int *r) {
int i=0;
long int acc0,acc1,acc2,acc3,acc4,acc5;
for(i=0; i<100000; i+=6) {
acc0+=num[i];
acc1+=num[i+1];
acc2+=num[i+2];
acc3+=num[i+3];
acc4+=num[i+4];
acc5+=num[i+5];
}
*r=acc0+acc1+acc2+acc3+acc4+acc5;
}
void sum7(long int *r) {
int i=0;
long int acc0,acc1,acc2,acc3,acc4,acc5,acc6;
for(i=0; i<100000; i+=6) {
acc0+=num[i];
acc1+=num[i+1];
acc2+=num[i+2];
acc3+=num[i+3];
acc4+=num[i+4];
acc5+=num[i+5];
acc6+=num[i+6];
}
*r=acc0+acc1+acc2+acc3+acc4+acc5+acc6;
}
void sum8(long int *r) {
int i=0;
long int acc0,acc1,acc2,acc3,acc4,acc5,acc6,acc7;
for(i=0; i<100000; i+=6) {
acc0+=num[i];
acc1+=num[i+1];
acc2+=num[i+2];
acc3+=num[i+3];
acc4+=num[i+4];
acc5+=num[i+5];
acc6+=num[i+6];
acc7+=num[i+7];
}
*r=acc0+acc1+acc2+acc3+acc4+acc5+acc6,acc7;
}
int main() {
clock_t start,finish,during;
srand((unsigned int)time(NULL));
long int result;
for(int i=0; i<100020; i++)
num[i]=(long int)rand()%10000;
start=clock();
sum0(&result);
finish=clock();
during=finish-start;
start=clock();
sum1(&result);
finish=clock();
printf("k=0:1\n");
printf("k=1:%f\n",(float)(during/(finish-start)));
start=clock();
sum2(&result);
finish=clock();
printf("k=2:%f\n",(float)(during/(finish-start)));
start=clock();
sum3(&result);
finish=clock();
printf("k=3:%f\n",(float)(during/(finish-start)));
start=clock();
sum4(&result);
finish=clock();
printf("k=4:%f\n",(float)(during/(finish-start)));
start=clock();
sum5(&result);
finish=clock();
printf("k=5:%f\n",(float)(during/(finish-start)));
start=clock();
sum6(&result);
finish=clock();
printf("k=6:%f\n",(float)(during/(finish-start)));
start=clock();
sum7(&result);
finish=clock();
printf("k=7:%f\n",(float)(during/(finish-start)));
start=clock();
sum8(&result);
finish=clock();
printf("k=8:%f\n",(float)(during/(finish-start)));
}
运行结果为:
在一定的误差范围内,程序给出了优化效率随并行度的变化趋势,与理论分析是吻合的。下图为教材中给出的结果:
三、 寄存器溢出问题的处理
1. 开启不同的优化选项,结果不同,如gcc与dev C++的默认优化选项不支持该优化方案,因此不存在寄存器溢出问题。
2. 开发者本身无需考虑寄存器的分配问题。在开启了相应优化选项的前提下,编译器会自动为相应临时变量分配寄存器,若寄存器溢出,相应数据存储到栈中,并通过register location技术确保其地址不会丢失,以保证该数据在需要时可被再次读写。
比如说,我在写如上代码时,并没有考虑寄存器有无溢出,这是编译器考虑的问题。寄存器溢出只会影响性能,但不会导致错误结果。
3. 开发者应适当利用此原理,编写高效代码。