`
RednaxelaFX
  • 浏览: 3049307 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

一个简单循环的优化问题 (2007-09-20)

阅读更多
Alright,终于开始用JavaEye的空间,顺便把之前写的别的东西转过来吧~~

==============转载开始==============
(2007-09-20)

昨晚回到宿舍之后,有同学问了我一个简单循环的优化问题.问题是,为何编译器要进行下述优化:

将优化前的代码:
for (int i = 0; i < 100; i++)
    for (int j = 0; j < 20; j++)
        a[j] = a[j] + 1;


优化为:
for (int j = 0; j < 20; j++)
    for (int i = 0; i < 100; i++)
        a[j] = a[j] + 1;


这让我一下疑惑了.我平时留意的循环相关优化主要是运算强度减弱(如乘法转换为加减法),不变量外提,短循环展开等.但这次的问题却跟前面三种情况都没什么关系.想了好一会才突然醒悟过来,原来是内存访问的问题.
可以观察到,优化前的代码里,外层循环里的所有语句都在内层循环里,而且外层循环控制变量i没有参与最内层循环体的运算,这为优化提供了可能性,意味着可以调换内外循环的顺序而不影响执行结果.

让我们来看看优化前的代码大概是被如何执行的(伪代码):
  lea reg0, a ; reg0 ← a
  and reg1, 0 ; reg1 ← i

outer_loop:
  cmp reg1, 100.
  jge end_outer_loop
  and reg2, 0 ; reg2 ← j
inner_loop:
  cmp reg2, 20.
  jge end_inner_loop
  mov reg3, reg0[reg2] ; //关键语句1_1
  incr reg3
  mov reg0[reg2], reg3 ; //关键语句1_2
  incr reg2
  jmp inner_loop
end_inner_loop:
  incr reg1
  jmp outer_loop

end_outer_loop:
  ...


而优化后的代码大概是这样(伪代码,实际上可以优化得更彻底):
  lea reg0, a ; reg0 ← a
  and reg2, 0 ; reg2 ← j

outer_loop:
  cmp reg2, 20.
  jge end_outer_loop
  and reg1, 0 ; reg1 ← i
  mov reg3, reg0[reg2] ; //关键语句2_1
inner_loop:
  cmp reg1, 100.
  jge end_inner_loop
  incr reg3
  incr reg1
  jmp inner_loop
end_inner_loop:
  mov reg0[reg2], reg3 ; //关键语句2_2
  incr reg2
  jmp outer_loop

end_outer_loop:
  ...


可以看到优化前后的代码长度几乎是一样的.也就是说这个优化跟减小目标代码的大小没有关系.最大的区别在于内存访问的语句的位置与内/外层循环体的位置关系.优化前,内层循环体每次执行都要进行两次内存访问,循环中需要进行的内存访问次数约为100 * 20 * 2 = 4000次.而优化后,内存访问被外提到了外层循环中,内层循环里不再需要访问内存,所以循环中需要进行的内存访问次数约为20 * 2 = 40次.
由于内存访问远远慢于寄存器访问,即使根据局部性(locality)原则a数组的内容都预先读到了高速cache中还是要比直接只使用寄存器要慢.所以综合各种条件后尽量减少内存的访问次数是优化的一个方向.而这个题目就展示了这一点.

为什么没一眼就看出来呢...我真是的.明明在debug的时候见得那么多的东西了...

=============续篇=============
(2007-09-24)

让我们来看看what's in the real world.下面两幅图分别是一个C++代码片段和对应的编译后结果的对照图.可以看到,前文中"优化后"代码对应的汇编在功能和顺序上跟我预期的没多少差别,只是具体指令用得不一样...嘛,寄存器清零确实xor用得最多.另外,两个版本在实际循环前都有一大段mov指令,这些就是a[20]的初始化语句所展开得到的.真正需要关心的地方从地址0x00401068开始.这循环次数实在太少,即使高精度记时器也未必能满足比较这两份代码消耗时间的需求,所以我们还是用观察法来分析两段代码的区别.





前一版本的代码("未优化版")的反汇编结果中我们可以看到,内层循环体里第一句是一个add指令.这对应于a[j] += 1;,这句指令实际上做了从内存取值,运算,将结果保存回内存这几步,也就是说内存访问次数大致可以认为有两次.综合来说,这个双层循环中内存的访问次数大约是100 * 20 * 2 = 4000次,与前面分析的一样.
后一版本的代码("优化版")的反汇编结果与前文的分析基本吻合,就不重复了.双层循环中内存的访问次树大致是20 * 2 = 40次.

很好,既然两次的编译结果都跟前面分析得差不多,那还有什么问题呢? 问题就是这优化是"我"而不是"编译器"做的.也就是说出这道问题的人光顾着理论研究而没管现实世界中的状况;也可能是没把想表达的意思说清楚;也有可能是转述的人记错了题目.Anyway,清华研究生入学考试考这种题也有够无聊的.这题实际想考的或许是与内存相关,不过也很可能只是下面提到的优化建议.

---------------------------------------------------------------------

Code Complete, 2nd Edition里,Chapter 26, 26.2 Loops一节提到了手工优化循环代码的一些建议,其中与本题相关的是:
Putting the Busiest Loop on the Inside

When you have nested loops, think about which loop you want on the outside and which you want on the inside. Following is an example of a nested loop that can be improved:

Java Example of a Nested Loop That Can Be Improved

for ( column = 0; column < 100; column++ ) {
    for ( row = 0; row < 5; row++ ) {
        sum = sum + table[ row ][ column ];
    }
}


The key to improving the loop is that the outer loop executes much more often than the inner loop. Each time the loop executes, it has to initialize the loop index, increment it on each pass through the loop, and check it after each pass. The total number of loop executions is 100 for the outer loop and 100 * 5 = 500 for the inner loop, for a total of 600 iterations. By merely switching the inner and outer loops, you can change the total number of iterations to 5 for the outer loop and 5 * 100 = 500 for the inner loop, for a total of 505 iterations. Analytically, you'd expect to save about (600 - 505) / 600 = 16 percent by switching the loops. Here's the measured difference in performance:

Language / Straight Time / Code-Tuned Time / Time Savings
C++ 4.75 / 3.19 / 33%
Java 5.39 / 3.56 / 34%
PHP 4.16 / 3.65 / 12%
Python 3.48 / 3.33 / 4%

The results vary significantly, which shows once again that you have to measure the effect in your particular environment before you can be sure your optimization will help.


---------------------------------------------------------------------

所以问题的关键是什么? 我觉得是"See it for yourself."
分享到:
评论

相关推荐

    228号资源-源程序:循环系统优化算法-本人博客有解读

    该算法的设计理念是将优化问题视为一个循环过程,个体代表系统中的元素,而优化目标则是提升系统效率和减少资源浪费。在CSOA中,算法通过模拟元素之间的相互作用和反馈机制,动态调整其状态,从而实现自我优化。这种...

    利用cvx 解决凸优化问题实例代码.rar_matlab 凸优化_凸优化_凸优化程序_凸优化问题_利用cvx 解决凸优化问题实例

    - **运行优化**:执行`cvx_solve`命令,CVX会自动选择合适的求解器来解决这个问题。 3. **示例代码解析** 提供的"利用cvx 解决凸优化问题实例代码.docx"文档中,很可能包含了一个具体的凸优化问题的MATLAB代码。...

    求解有约束优化问题sa-pso代码

    在计算机科学和工程领域,有约束优化问题是指寻找一个函数的最优解,同时满足一组特定的条件或约束。这些约束可能是不等式或等式,限制了搜索空间。优化的目标可以是最大化或最小化目标函数。 **模拟退火算法...

    比较好的循环方法---------

    在编程领域,循环是必不可少的控制流结构,用于重复执行一段代码直到满足特定条件为止。在不同的编程语言中,有多种类型的循环供我们选择,每种都有其独特的用途和效率。"比较好的循环方法"这一主题关注的是如何高效...

    优化方法Hooke-Jeeves C++程序

    程序的主要逻辑位于一个循环内,这个循环代表了算法的迭代过程。 在每次迭代中,程序会对每个维度进行检查。对于每个维度,计算函数值f,然后尝试沿着正方向和负方向移动,即yjia和yjian。如果这两个方向上的新函...

    程序分析与优化 - 6 循环优化.doc

    循环优化的逻辑相对简单,但对性能提升的效果却非常明显。本章主要介绍了循环的分析方法和优化技术。 6.1 循环的重要性 循环优化对获得更高的性能非常重要。根据 90/10 定律,90% 的算力消耗在 10% 的代码上,这些...

    性能测试_性能测试_c#循环优化_

    例如,一个简单的for循环优化前后的对比可能是这样的: ```csharp // 未优化的for循环 for (int i = 0; i ; i++) { // 执行某个操作 } // 优化后的并行for循环 Parallel.For(0, 1000000, i =&gt; { // 执行相同的...

    element 中 el-menu 组件的无限极循环思路代码详解

    下面是一个递归组件的简单实现代码: ```*** ***ponent('recursive-menu', { // 接收外部传入的菜单数据 props: ['menu'], template: ` &lt;el-menu-item index="menu.path"&gt; {{ menu.name }} &lt;recursive-menu v...

    JavaREPL是一个Java语言读入-求值-打印-循环(Read-Eval-Print-Loop)功能实现

    通过研究这些源代码,开发者可以了解如何实现一个简单的JavaREPL,或者对其进行定制以满足特定需求。 在实际使用JavaREPL时,开发者可以利用它来: - **快速测试代码片段**:比如尝试一个新的API调用,或者验证一...

    一个简单的sql循环语句脚本

    本话题将详细讲解一个简单的SQL循环语句脚本及其相关知识。 一、SQL循环语句概述 SQL循环语句主要包括WHILE循环和FOR循环,它们允许我们在满足特定条件时重复执行一段代码块。在PL/SQL和T-SQL中,还有BEGIN-END...

    算法-理论基础- 队列- 循环队列(包含源程序).rar

    循环队列是计算机科学中数据结构的一个重要概念,特别是在算法设计和实现中占有核心地位。队列是一种先进先出(First In First Out, FIFO)的数据结构,它在处理任务调度、缓冲区管理等方面有着广泛的应用。循环队列...

    DSP CCS 高级 优化编译

    - 循环优化:通过循环展开、合并等技术提高循环效率。 - 排除全局共用子表达式:类似于局部级别优化,但作用于整个函数。 - 排除全局未使用的赋值:与局部级别类似,但在全局范围内进行。 - 打开循环:将循环体...

    代码优化-之-优化条件分支[定义].pdf

    "代码优化-之-优化条件分支" 代码优化是软件开发中非常重要的一环,而条件分支是编程语言中的常见结构。然而,在某些时候,条件分支可能带来严重的性能问题。当前的CPU都能对条件分支做预测(动用了庞大的晶体管...

    简单反汇编之for循环、if判断--详细注释.doc

    我们以一个简单的示例程序为例,该程序包含一个for循环和一个if判断,用于计算一个累加和。 首先,我们看源代码: ```cpp void test(int a, int b) { int c = 1; for(int i = 0; i ; i++) { c = c + a + b + i; ...

    TIA博途-循环队列-全局FB库文件-GF-cyclic-Queue-FIFO.zip

    本压缩包文件“TIA博途-循环队列-全局FB库文件-GF-cyclic-Queue-FIFO.zip”显然是为了解决一个特定的编程任务,即使用循环队列(Cyclic Queue)的FIFO(先进先出)原则来优化数据处理。下面我们将深入探讨这个主题。...

    自制音频播放器-2020-09-20.zip

    本项目“自制音频播放器-2020-09-20.zip”就是利用C#语言编写的一款简易音频播放器,它能够加载同一文件夹内的音频文件,并且支持歌词同步显示。尽管存在一些小的bug,但通过适当的调整和优化,可以将其转化为一个...

    一个编译器优化引起的问题

    本文通过一个具体的案例来探讨编译器优化所带来的潜在问题及其解决方案。 #### 案例背景 案例中的开发者使用了KE的驱动库以及Keil作为开发环境。为了实现一个简单的延时功能,编写了一段代码,期望通过中断服务程序...

    爬台阶问题求解(优化求解)-少儿编程scratch项目源代码文件案例素材.zip

    "爬台阶问题求解"是一个很好的少儿编程教学案例,它通过简单的数学问题引入编程思维,利用Scratch的图形化编程界面,使编程变得生动有趣。通过分析和理解源代码,孩子们能够深入理解递归和循环的运用,同时提高编程...

    SCBC循环_布雷顿循环_简单布雷顿循环布置

    简单布雷顿循环则进一步简化了这一过程,通常不包括回热或再热等复杂环节,以降低系统的复杂性和成本。在SCBC中,SCO2被用作工质,由于其在超临界状态下具有的独特性质,使得该循环在高温和高压下运行时,能实现更高...

    约瑟夫环代码,建立一个具有n个链结点的循环链表。

    单向循环链表是一种特殊的数据结构,每个节点包含一个指向下一个节点的指针,最后一个节点的指针指向头节点,形成闭环。 #### 三、代码解析 1. **数据结构定义**: ```c typedef struct node { int num; // ...

Global site tag (gtag.js) - Google Analytics