代码效率的判断标准
老师给我们了两端代码让我们思考它们谁的效率高，并说出理由。他还提示用不同的角度去看这两段代码，可以得出不同的结果，还有要从程序的运行机理来看这个问题。各位帅哥美女帮小弟想一想，谢谢。
code 1:
int main()
{
int a[6]={1,1,1,1,1,1};
int b[6]={2,2,2,2,2,2};
int c[6]={0};
for(int i=0;i <6;i++)
{
c[i]=a[i]+b[i];
}
return 0;
}
code 2:
int main()
{
int a[6]={1,1,1,1,1,1};
int b[6]={2,2,2,2,2,2};
int c[6]={0};
for(int i=0;i <6;i+=2)
{
c[i]=a[i]+b[i];
c[i+1]=a[i+1]+b[i+1];
}
return 0;
}
[解决办法]
第一眼觉得code 2循环次数少了一半，似乎效率高了。
如果单从循环次数角度看，确实如此。
但是复杂度本质上是看完成了多少次操作。两个代码对a,b,c三个数组读写次数是相等的。当时对循环变量的操作次数有差异。
code1: "i <6 " 6次， "i++ " 6次, "取数组下标时读取i " 18次
code2： "i <6 " 3次， "i+=2 " 3次, "i+1 " 9次， "取下标时读取i/i+1 " 18次
可以看到code2在比较操作上少了3次，但是加法操作3+9-6=6次，换句话说，如果假设比较时间和加法时间相等的话，code2要比code1慢一些，大致相差n/2次（n为数组长度）加法的时间（即 （n/2 + 3n/2 - n）+ （2/n - n））
当然这个差别很小，因为i是在寄存器中，与在内存堆栈中读写数组大不相同（注意不能假设n小到足以在寄存器或L1/L2中完成，虽然本例n=6是如此）。
但是，再进一步，编译器是可以对代码做优化的，在每个循环中，i+1可以只被计算一次。所以，真实环境中这个差别有多大还很难说。不过，不考虑代码优化的话，code1比code2要快一些，是可以放心采用的结论。
[解决办法]
呵呵，在DSP中，使用并行指令发布的话，明显是第二种快。
下面我公平地对待这两种算法，并且以同等地水平来处理指令流水线。
/******* test.c ********/
// 第一种求和计算
extern "C " void sum1(int dest[6], const int src1[6], const int src2[6]);
// 第二种求和计算
extern "C " void sum2(int dest[6], const int src1[6], const int src2[6]);
int a[6] = { 1, 2, 3, 4, 5, 6 };
int b[6] = { 10, 20, 30, 40, 50, 60 };
int c1[6] = { };
int c2[6] = { };
int main()
{
sum1(c1, a, b);
sum2(c2, a, b);
return 0 ;
}
/****** sum.asm *******/
.section program;
.global _sum1;
_sum1:
// Set breakpoint at the following instruction
p0 = r0;// p0 points to destination
i0 = r1;// i1 points to src1
i1 = r2;// i2 points to src2
p1 = 6;
// hardware loop
loop CAL_SUM lc0 = p1;
loop_begin CAL_SUM;
r0 = [i0++] || r1 = [i1++];// parallel instruction issue
r2 = r0 + r1(ns);// non-saturate
[p0++] = r2;
loop_end CAL_SUM;
// Set breakpoint at the following instruction
rts;
_sum1.end:
.global _sum2;
_sum2:
// Set breakpoint at the following instruction
p0 = r0;
i0 = r1;
i1 = r2;
p1 = 3;
loop CAL_SUM2 lc0 = p1;
loop_begin CAL_SUM2;
r0 = [i0++] || r1 = [i1++];
r2 = r0 + r1(ns) || r0 = [i0++] || r1 = [i1++];
r2 = r0 + r1(ns) || [p0++] = r2;
[p0++] = r2;
loop_end CAL_SUM2;
// Set breakpoint at the following instruction
rts;
_sum2.end:
Result:
_sum1第一个断点处的Cycles：00000D5B
_sum1第二个断点处的Cycles：00000D7A
两者相减为31
_sum2第一个断点处的Cycles：00000D89
_sum2第二个断点处的Cycles：00000DA2
两者相减为25
因此，采用第二种算法所花费的指令周期比第一种少6个。
[解决办法]
以上代码可以在VisualDSP++环境下调试：http://www.analog.com/processors/blackfin/evaluationDevelopment/blackfinProcessorTestDrive.html
点击：Software Download - June 2006
可以试用三个月。该IDDE的C/C++编译器支持CPP2003以及C99标准，并且自带STL，在嵌入式领域非常强大。
如果想用UltraEdit查看我的汇编指令，可以用一下地址的wordfile，下载后替换旧的即可：
http://download.csdn.net/source/174562
[解决办法]
第一个注释写错了，应该是test.cpp，而不是test.c
上面两个代码很明显：_sum1中的loop块发布了三条指令，共循环6次，一共18条指令；
_sum2循环块中发布了4条指令，共循环3次，因此一共为12条指令。由于采用同等水平的流水线填补操作，实际上，两者循环中的pipeline的阻塞是一样的。
所以，它们正好相差6条指令周期。
[解决办法]
代码 2 效率高一点. 简之, 可读性换效率.
这个大致是这样:
代码 1 的可读性好. 符合人的自然逻辑.
代码 2 的效率高一点. 这也是常用的优化手段. 但是, 代码的可读性变差. 通常, 步长加大效率更高. 如 i += 6 效率更高.
可读性变差的原因是, 加大步长, 有可能需要如此是要处理 余数 个element.
[解决办法]
再描述完整点, 可读性变差的原因是:
1. 手动展开, 产生了多条 赋值语句. 代码变长了. 哦, 对了, 从这个意义上说, 手动展开不利啊. 如果, 导致代码分页分到不同页上去了, 那效率又要两说了.
2. 加大步长, 通常需要处理 余数 个element. 比如, 步长为 4 的话, 要处理 余数 2 个元素.
这个问题, 要把数组想象成足够大, 才能看出 代码 2的效率.
[解决办法]
实际上第二段代码稍微把三次i+1引起别人臭美的问题稍微修改一下就可以了.既然要从 "程序的运行机理 "看,那就来一段:cpu计算时,首先需要通过总线取数据,然后将数据送到累加器进行运算.现在流行的cpu使得总线取数据和累加器运算可以并行进行,因此,现在的cpu都有一个指令预取队列,在cpu进行累计运算的同时,总线将下一条指令取到指令预取队列中,这样就节省了累加器运算下一条指令时需要等待总线取数据的时间,而代码2中的下一条指令就可以顺序存取,能够加快计算;而for循环属于跳转指令,使得预取指令队列的数据无效,也就是,此时预取功能无效,累加器必须等待总线取到数据进行计算.因此代码2比代码1快.实际上,代码2步长小了些,最好步长> =4.还有一个知识点,你看你的bios信息,其中cpu信息中(现在一般都是)有L1 Cache 和L2 Cache ,这个就是cpu的一级和2级缓存,缓存的速度比内存速度快(总线取数据从内存取数据),这个缓存就是指令预取队列.建议大家看看计算机原理的书籍
[解决办法]
CPU缓存
缓存大小也是CPU的重要指标之一，而且缓存的结构和大小对CPU速度的影响非常大，CPU内缓存的运行频率极高，一般是和处理器同频运作，工作效率远远大于系统内存和硬盘。实际工作时，CPU往往需要重复读取同样的数据块，而缓存容量的增大，可以大幅度提升CPU内部读取数据的命中率，而不用再到内存或者硬盘上寻找，以此提高系统性能。但是由于CPU芯片面积和成本的因素来考虑，缓存都很小。
L1 Cache(一级缓存)是CPU第一层高速缓存，分为数据缓存和指令缓存。内置的L1高速缓存的容量和结构对CPU的性能影响较大，不过高速缓冲存储器均由静态RAM组成，结构较复杂，在CPU管芯面积不能太大的情况下，L1级高速缓存的容量不可能做得太大。一般服务器CPU的L1缓存的容量通常在32—256KB。
L2 Cache(二级缓存)是CPU的第二层高速缓存，分内部和外部两种芯片。内部的芯片二级缓存运行速度与主频相同，而外部的二级缓存则只有主频的一半。L2高速缓存容量也会影响CPU的性能，原则是越大越好，现在家庭用CPU容量最大的是512KB，而服务器和工作站上用CPU的L2高速缓存更高达256-1MB，有的高达2MB或者3MB。
L3 Cache(三级缓存)，分为两种，早期的是外置，现在的都是内置的。而它的实际作用即是，L3缓存的应用可以进一步降低内存延迟，同时提升大数据量计算时处理器的性能。降低内存延迟和提升大数据量计算能力对游戏都很有帮助。而在服务器领域增加L3缓存在性能方面仍然有显著的提升。比方具有较大L3缓存的配置利用物理内存会更有效，故它比较慢的磁盘I/O子系统可以处理更多的数据请求。具有较大L3缓存的处理器提供更有效的文件系统缓存行为及较短消息和处理器队列长度。
其实最早的L3缓存被应用在AMD发布的K6-III处理器上，当时的L3缓存受限于制造工艺，并没有被集成进芯片内部，而是集成在主板上。在只能够和系统总线频率同步的L3缓存同主内存其实差不了多少。后来使用L3缓存的是英特尔为服务器市场所推出的Itanium处理器。接着就是P4EE和至强MP。Intel还打算推出一款9MB L3缓存的Itanium2处理器，和以后24MB L3缓存的双核心Itanium2处理器。
但基本上L3缓存对处理器的性能提高显得不是很重要，比方配备1MB L3缓存的Xeon MP处理器却仍然不是Opteron的对手，由此可见前端总线的增加，要比缓存增加带来更有效的性能提升。
[解决办法]
高级别优化 (HLO)
数据预取是规避内存访问延迟的有效技术，可以在许多计算密集型应用中显著提高性能。数据预取在程序中的特定点上为所选数据引用插入预取指令，使引用的数据项在实际使用之前就已尽可能地移近处理器（放入高速缓存）。
循环展开将两个或更多个循环迭代合并到一起，以减少循环计数。循环展开虽然常常会导致代码长度增加，但它可以减少必须执行的指令数。下面是一个非常简单的循环展开示例，它从循环中删除了一个分支：
之前 之后
for (i=0, i <1000,i++)
{
a[i] = b[i] * c[i];
} for (i=0,i <1000, i+=4)
{
a[i] = b[i] * c[i];
a[i+1] = b[i+1] * c[i+1];
a[i+2] = b[i+2] * c[i+2];
a[i+3] = b[i+3] * c[i+3];
}
(这些例子自己可以到intel.com.cn去找).对于循环,intel后来的cpu(晚期的奔腾处理器)有BTB(分支目标缓冲器(Branch Target Buffer，BTB))技术(具体自己查找)能够有效的提高循环效率.
至于L1Cache ,L1Cache位于cpu内,是指令与数据的预取指令(数据)的队列.资料自己找.
关于cache ,cache line(就是一次读写指令/数据的基准长度)
Conroe的高速缓存、预拾取、外部总线、主内存系统
Conore的两个内核各拥有32KB两路相连L1指令高速缓存、32KB两路相连L1数据高速缓存，其中两个内核的L1数据缓存具备一致性总线来实现cache一致性，而两个内核都共享一个16路相连CPU全速运作的4MB L2 cache。
L1数据cache-L2 cache的连接带宽提升为256位（之前的Yonah、Dothan为128位），而Coppermine PIII时代所说的256bit L2 cache总线其实只是指DIB界面和L2 cache的连接带宽为256位。在Pentium 4上，L1 D-cache和L2 cache的位宽为256位。
Conroe的L1/L2 cache都是write back方式，L1-D和L2 cache的cache line长度为64个字节，即每次拾取（fetch）动作都会抓64个字节。相比之下，Pentium 4的L1 cache是write back、64字节；L2 cache是write through 128字节。
cache line越长意味着每次拾取能抓更多的数据，但是这是双刃剑，因为cache line越长也可能意味着被覆盖替换的资料越多造成拾取的动作可能更多。
英特尔宣称Conroe L1D和L1D之间有直通的连接，但是其作用并没有透露。
Conroe的每个内核都有三个独立的预取器（Pre-fetcher），它们分别位于指令拾取、load单元、store单元，此外在共享的L2 cache上也有两个预取器。预取器的作用是在处理器发出请求之前，提前把数据装进更高一级的内存里，你可以在我们的L2 cache延迟测试中看到一些效果。
Conroe的系统总线为AGTL+，和Pentium 4一样，但是频率就提升到1066MHz和1333MHz（Conroe的eXtreme版），作为64位处理器，Conroe可能拥有和Pentium D一样的40位物理内存定制能力，但是未来应该会作进一步的扩充（AMD已经有着方面的计划）。
[解决办法]
所谓的 "队列 "那是要按指令执行的先后顺序 "排队 "等待执行的
而这个队是排在哪里的,是放在CPU的指令流水线上的,还是放在Cache里的?
队列是严格的先进先出,即FIFO.
Cache只是存放指令和数据的一个临时地点,其数据交换的算法很复杂.
你可以说Cache有指令预取的功能,但不能说它们就是 "队列 ", 真正的排队是在比Cache更快的专门寄存器中.
