关于冒泡排序逆序时间少于逆序时间的疑点和探究
关于冒泡排序逆序时间少于逆序时间的疑问和探究
问题描述
现有两个整形数组，元素个数均为100000。组a为完全逆序，组b的顺序随机(非完全顺序)。对两数组使用冒泡排序，使之均变为完全顺序，组a耗时小
于组b(见截图)。
组a耗时
组b耗时
环境：Linux
编译：g++
经过分析，完全逆序与顺序随机的差别在于两层<for>循环中的<if>语句块是否执行，以及执行次数的多少。其中两层<for>循环的C++代码为：
汇编代码为(蓝色部分为方便理解做的注释)：
显然， 如果 a[i] > a[i+1]，那么将执行<jle .L4>条件转移指令；反之，则将顺序执行。
查阅相关资料后得出了一些结论:
现代CPU采用流水线技术来提升指令执行速度。这种技术会带来一个问题，即上一条指令执行时之后几条指令的地址必须确定。然而对于条件转移指令来说，需要当前指令执行完后才能判断是否跳转，此时后继指令的地址并不确定，需要等待判断完毕。这样的等待过程会降低执行速度。而分支预测技术则依据之前对True与False的判断(分支预测算法)来预测接下来几条命令的地址，并读入指令队列缓冲器。预测正确，则流水线执行无暂停；预测错误，则需要再次取址，重新执行另一分支的指令(将导致几十个时钟周期被浪费)。
注：
借鉴文章：1.http://blog.hesey.net/2013/03/branch-prediction-in-pipeline.html?utm_source=rss&utm_medium=rss&utm_campaign=branch-prediction-in-pipeline
2.http://www.cnblogs.com/yangecnu/p/4196026.html
后来老师提示说可以使用不同语言进行相同实验，如果结果相同就是CPU问题，如果结果不同则可能是g++编译器优化的结果。于是python 写了个代码，结果跑出来是乱序时间比逆序少，跟c++相反。因此怀疑可能是编译器的优化。然而我对于编译器优化不太了解，希望高手大神前辈们知其所以然的，不吝赐教！
------解决思路----------------------
无profiler不要谈效率！！尤其在这个云计算、虚拟机、模拟器、CUDA、多核 、多级cache、指令流水线、多种存储介质、……满天飞的时代！
------解决思路----------------------
g++ 的优化你是能看到的，就在汇编里。
python 和 C++ 的结果也许正好说明问题，因为 python 是解释执行的，应该不会受到流水线的影响。
问题描述
现有两个整形数组，元素个数均为100000。组a为完全逆序，组b的顺序随机(非完全顺序)。对两数组使用冒泡排序，使之均变为完全顺序，组a耗时小
于组b(见截图)。
组a耗时
组b耗时
环境：Linux
编译：g++
经过分析，完全逆序与顺序随机的差别在于两层<for>循环中的<if>语句块是否执行，以及执行次数的多少。其中两层<for>循环的C++代码为：
汇编代码为(蓝色部分为方便理解做的注释)：
显然， 如果 a[i] > a[i+1]，那么将执行<jle .L4>条件转移指令；反之，则将顺序执行。
查阅相关资料后得出了一些结论:
现代CPU采用流水线技术来提升指令执行速度。这种技术会带来一个问题，即上一条指令执行时之后几条指令的地址必须确定。然而对于条件转移指令来说，需要当前指令执行完后才能判断是否跳转，此时后继指令的地址并不确定，需要等待判断完毕。这样的等待过程会降低执行速度。而分支预测技术则依据之前对True与False的判断(分支预测算法)来预测接下来几条命令的地址，并读入指令队列缓冲器。预测正确，则流水线执行无暂停；预测错误，则需要再次取址，重新执行另一分支的指令(将导致几十个时钟周期被浪费)。
注：
借鉴文章：1.http://blog.hesey.net/2013/03/branch-prediction-in-pipeline.html?utm_source=rss&utm_medium=rss&utm_campaign=branch-prediction-in-pipeline
2.http://www.cnblogs.com/yangecnu/p/4196026.html
后来老师提示说可以使用不同语言进行相同实验，如果结果相同就是CPU问题，如果结果不同则可能是g++编译器优化的结果。于是python 写了个代码，结果跑出来是乱序时间比逆序少，跟c++相反。因此怀疑可能是编译器的优化。然而我对于编译器优化不太了解，希望高手大神前辈们知其所以然的，不吝赐教！
------解决思路----------------------
无profiler不要谈效率！！尤其在这个云计算、虚拟机、模拟器、CUDA、多核 、多级cache、指令流水线、多种存储介质、……满天飞的时代！
------解决思路----------------------
g++ 的优化你是能看到的，就在汇编里。
python 和 C++ 的结果也许正好说明问题，因为 python 是解释执行的，应该不会受到流水线的影响。