HardBirch

两个变量交换的扩展思考

时间:09-09-13 栏目:系统技术篇 作者:鲁智森也有文化 评论:0 点击: 1,359 次

首先声明,在面向对象盛行的时代里,我改用对象这两个词来指代最广泛的变量。 现在的变量就不一定只是一个整型或浮点型,甚至不是一个基本数据类型。我们 将在更广泛的意义上讨论对象交换的问题。

在前一篇文章 “ 关于两个对象交换的问题”(注意,名称已改)中,我们讨论了交换两个变量 的几种方法,并给出了形式化的公式。而在这一篇文章中,我们将讨论的是效率 与可行性的问题。(注:这个主题的想法,主要是受farproc朋友对上一篇文章的留言引发 的。)

中间变量方式

首先,我们来看采用最简单直接的交换方式的代码:

{        int tmp;        tmp = a;        a = b;        b = tmp;}

按语言本身的特性来想,这些代码做以下这些工作:

  1. 在栈上分配为整型变量tmp分配空间;
  2. 将a的值放入tmp中;
  3. 将b的值放入a中;
  4. 将tmp的值放入b中;
  5. 释放为tmp分配的栈空间。

而实际上呢?我们来看看生成的汇编代码:

      movl        b, %eax    ;将b从内存载入到寄存器eax        movl        a, %edx    ;将a从内存载入到寄存器edx        movl        %eax, a    ;将eax的内容存入到内存a中      xorl        %eax, %eax ;将eax清零      movl        %edx, b    ;将edx的内容存入到内存b中

看起来,汇编指令并不象我们想象的那样复杂。因为变量要参与运算首先要从内 存载入到寄存器中,所以要将两个变量交换只需按相反的顺序再存入到内存中就 可以了。只是四个内存与寄存器之间交换数据的指令,看起来好像没有交换操作 似的。而此处为什么要将eax清零呢?因为eax寄存器是专门用来放函数返回值 的,而我们的测试函数很简单,除了执行上面的操作外,剩下的就是return 0;了,因此它与变量交换根本没有关系。从上面可以看到,编译器为我们做的工 作远比我们想像的要多。

异或方式

接下来,我们来看基于异或方式交换的代码:

{        a ^= b;        b ^= a;        a ^= b;}

这一代码看起来很纯粹,没有一句是浪费的(是指全部操作都与交换有关,没有 像上例中的分配临时变量空间的操作),而且代码直接对应操作:三次异或。凭 着直觉,我们觉得它应该是效率最高的。但是它带来的副作用是代码的可读性大 大降低(注意,可读性很重要),而一些人认为这是值得的,因为它带来的效率。 我们接下来看看究竟是不是值得的。

下面是上面代码对应的汇编代码:

movl        b, %eax       ;将b从内存载入寄存器eaxmovl        a, %ecx       ;将a从内存载入寄存器ecxmovl        %eax, %edx    ;将eax的值保存到edx中xorl        %ecx, %edx    ;ecx与edx异或xorl        %edx, %eax    ;edx与eax异或xorl        %eax, %edx    ;eax与edx异或movl        %eax, b       ;将eax的值存入到内存b中xorl        %eax, %eax    ;将eax置0:设置返回值,与上例中一样movl        %edx, a       ;将edx的值存入到内存a中

哦,好像有点晕了。
它总共用了四次内存与寄存器之间的数据移动操作,一次寄存器之间的赋值,以 及三次异或运算。
我很诧异编译器会产生这样的汇编代码,我怀疑是编译选项出了问题(这是在-O2下 的结果),于是试了-O3的结果,居然也是完全一样,更令人意想不到的 是,在-O1下产生的结果居然是最简洁的。不过我们先来看上面这些代码都做了些 什么操作,是否都是必要的操作。

“意外”现象分析

首先我们将上面的C代码改写一下(现在想来才觉得C代码其实也是一样的迷惑 人,我并不清楚它到底经过了哪些步骤,而只知道它能交换两个整型变量的值而 已):

{        int tmp;

        tmp = a ^ b;      //得到异或的中间结果,即任何a、b中与它                          //异或,都会得到另外一个的值(对比参考                          //第一篇文章中关于加和乘情况的讨论)      b = tmp ^ b;      //b的最终结果:b=(a^b)^b=a^(b^b)=a        a = tmp ^ a;      //a的最终结果:a=(a^b)^a=b^(a^a)=b}

现在,我们来将汇编代码逐行翻译为C代码来看看(忽略内存与寄存器之间的数据 交换):

      int tmp;        //寄存器edx对应变量tmp

        tmp = b;        tmp = a ^ tmp;  //对应于tmp = a ^ b;

        b = tmp ^ b;

        tmp = b ^ tmp;        a = tmp;        //对应于a = tmp ^ b;

与我们转换后的代码相比,对这段代码编译器好像有点犯迷糊了。我们明明没有 用中间变量的代码,它居然不仅用了中间变量,而且还多用了两个赋值操作。
接下来我们再看在-O1下产生的结果:

      movl        b, %eax       ;将b载入到寄存器eax        movl        %eax, %edx    ;将eax的值保存到edx        xorl        a, %edx       ;内存a与edx异或,结果保存到edx,得到中间结果      xorl        %edx, %eax    ;edx与eax异或,结果到eax,得到b的最终值,即a        movl        %eax, b       ;保存到内存b        xorl        %eax, %edx    ;edx与eax异或,结果到edx,得到a的最终值,即b        movl        %edx, a       ;保存到内存a        movl        $0, %eax      ;设置返回值

这一结果与我们手工转换的代码是类似的。但它不仅进行了四次内存与寄存器之 间的数据移动操作(对应于中间变量交换的情况),而且还进行了一次寄存器之 间的赋值,两次寄存器之间的异或运算,以及一次寄存器与内存之间的异或运算 (应该包含一次内存与隐含寄存器之间的数据移动,以及一次异或运算)。由此 看来,-O1产生的代码确实不如-O2产生的代码效率高,编译器并没有犯迷糊。

结论

很明显可以看出,异或方式的效率比预期的要坏得多,而且要比采用中间变量的 方式更坏。现在看来,如果我们一开始就从汇编及CPU的执行流程上来考虑的话, 就可以很容易的得出这一结论。在机器的角度来考虑交换两个整型变量(即相对 应的内存)的值,只需要将两个变量的值载入到寄存器中,然后按相反的对应关 系使用,或是按相反的对应关系保存到内存中即可,完全不需要经过中间计算。 而用异或方式,除了上述内存与寄存器之间的数据移动操作外,还需要进行三次 的异或操作(以及可能由此带来的移动操作)。这个结论是显而易见的。
采用异或的方式,我们不仅牺牲了可读性,而且还牺牲了效率,所以并不可取。
其它的方式,如加、乘等,用脚趾头想想也知道结果了,所以就不再讨论了。

说明

以上的结果,只是根据由C代码生成的汇编代码的行数,及其内存与寄存器之间数 据移动的次数等方面比较它们的效率;C代码也是很简单而纯粹的整型变量交换, 与实际情况差别较大;而且最重要的是没有来实际测量它们的运行时间,因此得出 的结论并不一定正确。

本次只讨论的是对整型变量交换的情况,而实际中要交换的对象是多种多样的。 比如在C++中,最常见的应该就是类对象的交换,甚至是两个不知道何种类型的对 象的交换(考虑模板类的情形)。

并不是所有对象都支持异或、加、乘的运算,所以这些方法就基本舍弃了,但仍要 重视它们所带来的思想上的东西(这种情况下仍然有可以用它们,但是很危险, 参见注1)。而基于中间变量的方式也要加以小心,一些对 象必须提供合适的拷贝构造函数和赋值运算符函数,才能保证交换操作在语义上 也是正确的,比如那些内部含有指针成员的类对象。

更广泛的结论

总的来说,采用中间变量方式交换两个对象的值,是最通用、可读性最高、效 率比较高的一种方式。在此我建议大家在一般情况下,都采用这种方式。 (注2

[1] 我们可以将对象看成若干个字符类型变量的数组,从而可以使用异或等方式。 但是,这并不能保证它的语义是正确的,尤其是在C++中。可以这样说,在实际情 况中,这样的操作几乎总是会带来错误。

[2] 说到最后,还不如原来就不要知道这种方法呢 :)

[n] 我的系统平台是Debian 4.1.1、GCC 4.1.2,所有编译选项默认均为-O2,编译为 汇编代码的选项为-S。

[n+1] farproc的汇编结果是另一种情况。在进行交换之前数据已经载入到寄存器中,从而考虑的只有寄存器中的运算。下面是他的留言:

经过我的测试(vc2005 release),使用一个临时变量的交换方式还是效率最高的。位异或的次之,相加或相乘的最慢。
其实看一下生成的汇编码就很清楚了。
使用临时变量版本:

    mov eax,edi     mov edi,esi     mov esi,eax

位异或版本:

    xor edi,esi     xor esi,edi     xor edi,esi

加减版本:

    add edi,esi     mov ecx,edi     sub ecx,esi     mov esi,ecx     sub edi,esi

void swap2(int*a,int*b )

{

    *a^=*b;

    *b^=*a;

    *a^=*b;

}

利用中间变量:最常用,也是最基本的,可读性好,适用于任何类型,只要对象具备合适的

构造函数。

利用异或交换:在内置数据类型比较常用,也就局限于 整形数据的交换。

声明: 本文由( 鲁智森也有文化 )原创编译,转载请保留链接: 两个变量交换的扩展思考

两个变量交换的扩展思考:等您坐沙发呢!

发表评论


QQ群互动

Linux系统与内核学习群:194051772

WP建站技术学习交流群:194062106

魔豆之路QR

魔豆的Linux内核之路

魔豆的Linux内核之路

优秀工程师当看优秀书籍

优秀程序员,要看优秀书!

赞助商广告

友荐云推荐