为什么会这样子

a ^= b;
b ^= a;
a ^= b;

以前看到iceboy喜欢用xor来交换两个数。今晚就写了段程序来比较xor法与第三方变量法的效率,惊奇的发现,xor法竟然输了。
是不是我的程序有问题呢?

以下是测试比较:

1) 当两者进行1亿次交换时,xor法输48ms。
1. a=1 b=2
2. a=1 b=2     ms:688
3. a=1 b=2     ms:640

2)当两者进行10亿次交换时,xor法输249ms。
1. a=100 b=200
2. a=100 b=200 ms:6765
3. a=100 b=200 ms:6516

3)当两者进行1次交换时,rdtsc读取来的时钟周期数显示两者速度相差不大,无比较意义。

对交换部分代码进行反汇编,得到
xor法:
40142d: 81 7d e8 ff e0 f5 05 cmpl $0x5f5e0ff,0xffffffe8(%ebp)
401434: 7f 1f                 jg     401455 <_main+0xc5>
401436: 8b 55 ec             mov    0xffffffec(%ebp),%edx
401439: 8d 45 f0             lea    0xfffffff0(%ebp),%eax
40143c: 31 10                 xor    %edx,(%eax)
40143e: 8b 55 f0             mov    0xfffffff0(%ebp),%edx
401441: 8d 45 ec             lea    0xffffffec(%ebp),%eax
401444: 31 10                 xor    %edx,(%eax)
401446: 8b 55 ec             mov    0xffffffec(%ebp),%edx
401449: 8d 45 f0             lea    0xfffffff0(%ebp),%eax
40144c: 31 10                 xor    %edx,(%eax)
40144e: 8d 45 e8             lea    0xffffffe8(%ebp),%eax
401451: ff 00                 incl (%eax)
401453: eb d8                 jmp    40142d <_main+0x9d>

第三方变量法:
4014e8: 81 7d e8 ff e0 f5 05 cmpl $0x5f5e0ff,0xffffffe8(%ebp)
4014ef: 7f 19                 jg     40150a <_main+0x17a>
4014f1: 8b 45 f0             mov    0xfffffff0(%ebp),%eax
4014f4: 89 45 e4             mov    %eax,0xffffffe4(%ebp)
4014f7: 8b 45 ec             mov    0xffffffec(%ebp),%eax
4014fa: 89 45 f0             mov    %eax,0xfffffff0(%ebp)
4014fd: 8b 45 e4             mov    0xffffffe4(%ebp),%eax
401500: 89 45 ec             mov    %eax,0xffffffec(%ebp)
401503: 8d 45 e8             lea    0xffffffe8(%ebp),%eax
401506: ff 00                 incl (%eax)
401508: eb de                 jmp    4014e8 <_main+0x158>

很明显,xor法生成的汇编代码行数较多,xor可能比mov的时钟周期数要少。但是因为涉及了内存操作,这两段代码在不同的编译器就可能有不同做法,很难比较了。

注意,上面的分析是在gcc没有开启优化选项的情况下进行的。
如果加入了-O参数,xor交换代码会被聪明地替换成只有3行代码:
4013b8: 87 f3                 xchg %esi,%ebx
4013ba: 42                 inc    %edx
4013bb: 81 fa ff e0 f5 05     cmp    $0x5f5e0ff,%edx
而第三方变量法被优化成:
401443: 89 d8                 mov    %ebx,%eax
401445: 89 f3                 mov    %esi,%ebx
401447: 89 c6                 mov    %eax,%esi
401449: 42                 inc    %edx
40144a: 81 fa ff e0 f5 05     cmp    $0x5f5e0ff,%edx
401450: 7e f1                 jle    401443 <_main+0x111>

两者都省去了内存相关的操作了。xor法虽然用xchg直接交换了变量,但结果却出乎意料。xchg比mov耗多了一倍时间。测试如下:
1. a=1 b=2
2. a=1 b=2     ms:468
3. a=1 b=2     ms:219

小结,在c、c++里交换变量还是少使用xor法,除非自己一定要装逼,那也无所谓。

附测试程序源代码:

#include "windows.h"
#include "iostream"
using namespace std;

#define record(t) t = GetTickCount()

int main()
{
	int tl1, tl2, tl3;
	int a = 1, b = 2, i, t;
	cout--"1. a="--a--" b="--b--endl;
	record( tl1 );

	//exchange  1:
	for( i=0; i<100000000; i++ ){
		a ^= b;
		b ^= a;
		a ^= b;
	}

	record( tl2 );
	cout--"2. a="--a--" b="--b--"\tms:"--tl2-tl1--endl;
	record( tl2 );

	//exchange 2:
	for( i=0; i<100000000; i++ ){
		t = a;
		a = b;
		b = t;
	}

	record( tl3 );
	cout--"3. a="--a--" b="--b--"\tms:"--tl3-tl2--endl;
	return 0;
}

为什么会这样子》上有13条评论

  1. Xiaoxia

    xchg不是一个很简单的操作么? 为什么时钟周期会这么长?
    i486上xchg是3个时钟周期。mov是1个时钟周期。也就是说,3个mov指令的时钟周期应该与1个xchg时钟周期的时间相等。
    然而,测试结果表明xchg的时间还是长了一倍。为什么呢?
    是不是说明intel Pentium后的cpu(我的是atom n270)的mov比xchg快很多?

    回复
  2. ear

    xchg其实就是3次xor操作

    xchg %esi,%ebx这条指令对内存读取了3次,当然会慢

    位运算只有在汇编里才会有效率,高级语言必然涉及到读取内存,想快也快不起来

    回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>