月度归档:2013年08月

数值交换与优化

大学的时候,看到一道面试题:不用临时变量交换两个数的值。
    话说 真把我难住了, 还好 有答案。 惊讶 异或 还可以这么神奇. 一直记在心中.
    后来 学Java的时候, 老师 提了下 这样 也会分配 临时空间的. 自己噢了一下,就过去了,对寄存器并没什么概念
    再后来,知道在不溢出的情况下,用加减法也是可以的。
    再后来,我知道一般人写的 是有隐患的
    我就想,又没有本质优化,怎么这么多人这样写了,于是汇编看看 到底是怎样的
    C 源码:
   汇编代码

swap


swap2


    可以 看到,即使 不懂 汇编 也知道 swap2 用的指令种类比swap多了个 xorl , 条数 还比 swap 多。仔细分析,会看到 swap比swap2多了一个 -4(%rbp)

   这个了 就是 函数栈中的空间,保存在 内存中. 也就是说 swap 因为 临时变量t 多了一个对内存的写操作(读操作swap2比swap多),由于内存操作比寄存器操作慢,所以我们在这里先不比较效率,我们看下编译器优化后的情况.
   优化后,汇编代码

swap


swap2


     可以 看到,编译器 优化后,汇编代码 清爽多了。只要会比多少,就会知道 使用 异或  在效率上在降低了,在空间上 少用一个寄存器 edx。

      相对优化前的swap汇编代码,优化后的汇编对多了 rdi,rsi 两个寄存器的访问,减少了对其他寄存器的读写。
  这两个寄存器有什么特点了?
  首先,这两个寄存器是用来调用swap函数时传递参数的,其值 由调用者设置。
  其次,这两个寄存器是非易失性的【Register Usage】
     也就是说,被调用者不修改或者修改后要在调用结束前改回修改前的值
  根据以上资料, 异或 操作,并没有 太大的 优化作用,为什么 还有这么多人 这样写了?
  直观上,没有使用临时变量。优化前,多使用了一个int大小的栈空间,一般4字节;优化后 多使用了一个寄存器。
  基于 这样的原因, 正如 那个面试题 所说的那样,不使用临时变量。大家都采用swap2,尤其在讨论算法,特别是排序时 。
 
 
 
References:
   深入理解计算机体系结构