又一面试题,又一伪命题
最近土豆同学经常去参加各种面试和笔试,而我也获益不少,得以见识到这些"题目"的诡异.这次听到的,是一个关于C语言中字符串逆序的问题.问题的核心是: 用什么办法,可以最高效的把一个char[]内容的顺序逆转? 最好是不用额外的存储空间.我陷入了沉思.土豆同学问我的时候,一再强调既不需要用"额外的存储空间,也不需要加减或者异或运算";跟算法没关系,而是与类似语言特性的特性相关.想想也是,要逆序,无论如何也要遍历整个字符数组,不可能达到比O(n)还好的下限.但是不使用"额外"的空间...
并且,假设函数原型是类似: void reverse( char* str );
于是我只想到了两种可能,要么利用了数组之前(也就是例如"array[-1]"之类)的"安全空间",要么利用数组最后的"\0".当然,前者不是语言规定要有,而是编译器特定的行为,不靠谱;后者则是C语言里字符串的标准表示方式所规定的: 字符串以'\0'表示结束,可以放心利用.想到这里,土豆点头了,说面试官提出的就是这么一种使用结束位置上的0来完成交换的,"既没有使用额外的存储空间,又比加减或者异或运算快的方法".
...
我随即表示了反对.我从一开始就觉得这个方法很糟糕,所以没纳入考虑范围.不过面试官的思路我们也琢磨不透就是了.下面将说明我反对这种方法的理由.
把问题稍微简单化,将上面涉及的三种方案都写成代码如下.foo1()是面试官的建议版,foo2()是使用额外临时变量版,foo3()是运算版.
#include <stdio.h>#include <string.h>/* * reverse string via the terminating zero */void foo1(char* a) { int len = strlen(a); int i; for (i = 0; i < len / 2; i++) { a = a; a = a; a = a; } a = 0;}/* * reverse string via a temp variable */void foo2(char* a) { char temp; int len = strlen(a); int i; for (i = 0; i < len / 2; i++) { temp = a; a = a; a = temp; }}/* * reverse string via XORs */void foo3(char* a) { int len = strlen(a); int i; for (i = 0; i < len / 2; i++) { a ^= a; a ^= a; a ^= a; }}void main(void) { /* declare few strings to be put into test */ char* a = "abcd"; char* b = "abcde"; char* c = "abcdef"; /* reverse the strings above */ foo1(a); foo2(b); foo3(c); /* print results */ printf("%s\n%s\n%s\n", a, b, c);}
光从C语言的表象上看上面的代码,一时还真会觉得: foo1()与foo3()几乎一样,只是没有了"运算";而这两者又比foo2()要节省空间,因为没有多用一个"临时变量".
那么让我们来看看特定于一个编译器上,上面的代码实际表达了怎样的意思:
将上面的代码(str.c)以VC8的编译器编译,命令用的是: cl /Og /Ot /Ox str.c
foo1():
00401000/$8B4C24 04 mov ecx,dword ptr ss:00401004|.55 push ebp00401005|.56 push esi00401006|.57 push edi00401007|.8BF9 mov edi,ecx00401009|.8D57 01 lea edx,dword ptr ds:0040100C|.8D6424 00 lea esp,dword ptr ss:00401010|>8A07 /mov al,byte ptr ds:00401012|.83C7 01 |add edi,100401015|.84C0 |test al,al00401017|.^ 75 F7 \jnz short str.0040101000401019|.2BFA sub edi,edx0040101B|.8BC7 mov eax,edi0040101D|.99 cdq0040101E|.2BC2 sub eax,edx00401020|.8BE8 mov ebp,eax00401022|.D1FD sar ebp,100401024|.33F6 xor esi,esi00401026|.85ED test ebp,ebp00401028|.7E 23 jle short str.0040104D0040102A|.8D540F FF lea edx,dword ptr ds:0040102E|.8BFF mov edi,edi00401030|>0FB6040E /movzx eax,byte ptr ds:00401034|.88040F |mov byte ptr ds:,al00401037|.0FB602 |movzx eax,byte ptr ds:0040103A|.88040E |mov byte ptr ds:,al0040103D|.0FB6040F |movzx eax,byte ptr ds:00401041|.8802 |mov byte ptr ds:,al00401043|.83C6 01 |add esi,100401046|.83EA 01 |sub edx,100401049|.3BF5 |cmp esi,ebp0040104B|.^ 7C E3 \jl short str.004010300040104D|>C6040F 00 mov byte ptr ds:,000401051|.5F pop edi00401052|.5E pop esi00401053|.5D pop ebp00401054\.C3 retn
foo2():
00401060/$53 push ebx00401061|.56 push esi00401062|.57 push edi00401063|.8B7C24 10 mov edi,dword ptr ss:00401067|.8BC7 mov eax,edi00401069|.8D50 01 lea edx,dword ptr ds:0040106C|.8D6424 00 lea esp,dword ptr ss:00401070|>8A08 /mov cl,byte ptr ds:00401072|.83C0 01 |add eax,100401075|.84C9 |test cl,cl00401077|.^ 75 F7 \jnz short str.0040107000401079|.2BC2 sub eax,edx0040107B|.8BD8 mov ebx,eax0040107D|.99 cdq0040107E|.2BC2 sub eax,edx00401080|.8BF0 mov esi,eax00401082|.D1FE sar esi,100401084|.33C9 xor ecx,ecx00401086|.85F6 test esi,esi00401088|.7E 1A jle short str.004010A40040108A|.8D543B FF lea edx,dword ptr ds:0040108E|.8BFF mov edi,edi00401090|>8A1A /mov bl,byte ptr ds:00401092|.8A0439 |mov al,byte ptr ds:00401095|.881C39 |mov byte ptr ds:,bl00401098|.8802 |mov byte ptr ds:,al0040109A|.83C1 01 |add ecx,10040109D|.83EA 01 |sub edx,1004010A0|.3BCE |cmp ecx,esi004010A2|.^ 7C EC \jl short str.00401090004010A4|>5F pop edi004010A5|.5E pop esi004010A6|.5B pop ebx004010A7\.C3 retn
foo3():
004010B0/$53 push ebx004010B1|.56 push esi004010B2|.8B7424 0C mov esi,dword ptr ss:004010B6|.8BC6 mov eax,esi004010B8|.57 push edi004010B9|.8D50 01 lea edx,dword ptr ds:004010BC|.8D6424 00 lea esp,dword ptr ss:004010C0|>8A08 /mov cl,byte ptr ds:004010C2|.83C0 01 |add eax,1004010C5|.84C9 |test cl,cl004010C7|.^ 75 F7 \jnz short str.004010C0004010C9|.2BC2 sub eax,edx004010CB|.8BD8 mov ebx,eax004010CD|.99 cdq004010CE|.2BC2 sub eax,edx004010D0|.8BF8 mov edi,eax004010D2|.D1FF sar edi,1004010D4|.33C9 xor ecx,ecx004010D6|.85FF test edi,edi004010D8|.7E 20 jle short str.004010FA004010DA|.8D5433 FF lea edx,dword ptr ds:004010DE|.8BFF mov edi,edi004010E0|>0FB60431 /movzx eax,byte ptr ds:004010E4|.3002 |xor byte ptr ds:,al004010E6|.8A02 |mov al,byte ptr ds:004010E8|.300431 |xor byte ptr ds:,al004010EB|.8A0431 |mov al,byte ptr ds:004010EE|.3002 |xor byte ptr ds:,al004010F0|.83C1 01 |add ecx,1004010F3|.83EA 01 |sub edx,1004010F6|.3BCF |cmp ecx,edi004010F8|.^ 7C E6 \jl short str.004010E0004010FA|>5F pop edi004010FB|.5E pop esi004010FC|.5B pop ebx004010FD\.C3 retn
总体看看这三份代码,可以看到strlen函数都被inline进来了,所以三份代码的开头部分都有一个小循环,用于计算数组的长度(题外话: 我见的最多的strlen实现是用rep实现的啊...这里为什么是显式循环,怪哉).
接下来,先对比foo1()与foo3().主要关注靠近代码尾部的循环,发现内容几乎是一样的,除了foo3()里出现了3个xor,而foo1()里的对应位置上指令是mov.查阅x86的手册可以知道,在i486,i586等机器上mov mem, reg需要1个时钟周期,而xor mem, reg需要3个.确实,在这里运算与否有那么点细微的性能差距,但是根据80/20法则,这点差距是否真的能体现在程序的实际运行里值得疑问.
然后,再看上面那对与foo2()的比较.在C源代码中,可以看到我们声明了一个临时变量char temp,按照土豆同学所说的"一般常识",这个变量应该被分配在栈上了.可是事实上呢? 从编译出来的结果,可以看到这个temp从来没有被保存在栈上,而是直接分配在了寄存器上.有人要问"具体分配到哪个寄存器了呢?",答案更有趣:其实是分配到2个寄存器,al与bl上了;换句话说,"temp"这个变量就像存在有两份一样,分别储存了被交换的数据的两边.要说"占用了额外的存储空间",那也只能说是多用了个寄存器(仔细观察会发现其实也没多用),而这其实是个好事.在如此简单的函数中,寄存器不会不够用,而是有多的没用到;能有效分配寄存器,实际上让程序更高效了.
硬要比较这3个编译结果,应该能看出,foo2()才是最快而且不浪费(栈)空间的版本,另外两个都差不多.当然这是吹毛求疵了,实际运行的话很可能看不出什么性能差别.
需要重申的是,上面给出的结果是基于特定的编译器(VC8)与特定平台(Win32/i586)的组合下的结果,并不代表所有编译器的特性或所有平台的特性.
本来,只需要交换两个变量的值的话,用异或的方法是个相当不错的选择(本来xor reg, reg只需要1个时钟周期),但这里不巧遇上了数组而需要间接寻址,就(细微得)慢了.把结束标记的0(一个必须要分配,平时却没显著作用的空间)作为临时变量也是个不错的方案,但同样是遭遇到数组访问的问题而受到了拖累.反而在源代码里用了"额外的临时变量"的foo2()得到了不错的优化.这里的启示是: 没必要的时候,不要乱做优化.首先,凭"一般常识"而不是profile做出的优化决定很可能并不会给程序带来显著的性能提升.其次,耍小聪明的优化反而可能干扰编译器的判断,从而阻挠了一些优化,反而使代码变得更慢.那就得不偿失了.
面试官们的水平也还需要加强啊...那是哪间公司来着? 反正我没记住名字,算了.
说到这里倒是想起我以前用过的BlowfishJ,一个Java的Blowfish算法实现.它做了些极端的优化来试图克服Java本身性能上的缺陷.其中,在编码与解码的方法里,它都是先把一个长度为18的int[] (也就是那个P box)全部赋值给局部变量,然后再进入循环运算.在寄存器比较多的机器上,这确实有助于JITter的优化,尽可能利用寄存器而减少间接寻址.
所以说我实在挺不理解,在一些trivial的地方用尽心思去减少局部变量的使用,到底能有什么好处... = =
=================================================================
另外,既然提到这个话题,希望能引起注意的是异或交换方法的简写形式.相信有一定C++经验的人都会见过这个:
inline void swap(int& a, int& b) { a ^= b ^= a ^= b;}
好吧,用异或运算本来就很难支持泛型(因为不是什么都能拿来算--除非cast成指针,那没话说了),所以这里只是简单的用了int型而没用template.这么写在C++里是(很可能)没问题,但并不意味着能广泛应用到其它C-like语言中.就不提C++的pass-by-reference语法不能在C或者Java里用,关键是中间的那句:
a ^= b ^= a ^= b;
要是在Java或者C#执行这句,就会发现b虽然正确的得到了a原本的值,但a在结束时却总是0.所以同一个简写,换到Java与C#中得这样写:
a = (b ^= a ^= b) ^ a;
原因也是与运算顺序的规定相关.C/C++中虽然没规定表达式的运算顺序,不过规定了赋值顺序一定是右结合的,所以那个简单版的简写(多半能)行得通(行不通的例子请参考这里).但Java/C#严格定义了表达式的运算顺序一定是从左向右,赋值顺序是从右向左,所以在遇到^=运算符时,需要首先将左操作数装载,再装载右操作数.这么做的后果是最左边的^=的左操作数的值是"旧"的,因而在简单版简写中等同于与自身做了异或,结果自然是0.
以JVM bytecode来说明,简单版简写编译出来是这样:
iload_1 // 关键差异iload_2iload_1iload_2ixordupistore_1ixordupistore_2ixoristore_1
而带括号的版本是这样:
iload_2iload_1iload_2ixordupistore_1ixordupistore_2iload_1 // 关键差异ixoristore_1
可以观察到注释为"关键差异"的行出现的位置的不同,导致了最终运算结果的不同.
下面具体举几个例子:
·可以用简单版简写的:
C/C++: (Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86测试)
#include <stdio.h>void main(void) { int i = 1, j = 2, k = 3, l = 4; i ^= j ^= i ^= j; k = (l ^= k ^= l) ^ k; printf("i = %d, j = %d\nk = %d, l = %d", i, j, k, l); // i = 2, j = 1, k = 4, l = 3}
D: (DMD 2.004测试)
void main(char[][] args) { int i = 1, j = 2, k = 3, l = 4; i ^= j ^= i ^= j; k = (l ^= k ^= l) ^ k; printf("i = %d, j = %d\nk = %d, l = %d", i, j, k, l); // i = 2, j = 1, k = 4, l = 3}
TJS2: (KiriKiri 2.29测试)
tf.i = 1, tf.j = 2, tf.k = 3, tf.l = 4;tf.i ^= tf.j ^= tf.i ^= tf.j;tf.k = (tf.l ^= tf.k ^= tf.l) ^ tf.k;tf.i = , tf.j = tf.k = , tf.l = ; tf.i = 2, tf.j = 1, tf.k = 4, tf.l = 3
·需要用括号版简写的:
Java: (JRE 1.5.0/1.6.0测试)
public class Swap { public static void main(String[] args) { int i = 1, j = 2, k = 3, l = 4; i ^= j ^= i ^= j; k = (l ^= k ^= l) ^ k; System.out.printf("i = %d, j = %d\nk = %d, l = %d", i, j, k, l); // i = 0, j = 1, k = 4, j = 3 }}
C#: (.NET Framework 2.0测试)
using System;public class Swap { public static void Main(string[] args) { int i = 1, j = 2, k = 3, l = 4; i ^= j ^= i ^= j; k = (l ^= k ^= l) ^ k; Console.WriteLine("i = {0}, j = {1}{2}k = {3}, l = {4}", i.ToString(), j.ToString(), Environment.NewLine, k.ToString(), l.ToString()); // i = 0, j = 1, k = 4, j = 3 }}
JavaScript: (IE6/IE7/FF2测试)
<html><body><script type="text/javascript">var i = 1, j = 2, k = 3, l = 4;i ^= j ^= i ^= j;k = (l ^= k ^= l) ^ k;document.write("i = " + i + ", j = " + j + "<br />k = " + k + ", l = " + l);// i = 0, j = 1, k = 4, j = 3</script></body></html>
页:
[1]