转载注明出处:http://www.cppblog.com/ant/archive/2007/10/12/32886.html
学习高效编程的有效途径之一就是阅读高手写的源代码,CRT(C/C++ Runtime Library)作为底层的函数库,实现必然高效。恰好手中就有glibc和VC的CRT源代码,于是挑了一个相对简单的函数strlen研究了一下,并对各种实现作了简单的效率测试。
strlen的函数原形如下:
strlen返回str中字符的个数,其中str为一个以'\0'结尾的字符串(a null-terminated string)。
1. 简单实现
如果不管效率,最简单的实现只需要4行代码:
也许可以稍加改进如下:2.
高效实现
很显然,标准库的实现肯定不会如此简单,上面的strlen_a以及strlen_b都是一次判断一个字符直到发现'\0'为止,这是非常低效的。比较高效的实现如下(在这里WORD表示计算机中的一个字,不是WORD类型):
(1) 一次判断一个字符直到内存对齐,如果在内存对齐之前就遇到'\0'则直接return,否则到(2);
(2) 一次读入并判断一个WORD,如果此WORD中没有为0的字节,则继续下一个WORD,否则到(3);
(3) 到这里则说明WORD中至少有一个字节为0,剩下的就是找出第一个为0的字节的位置然后return。
NOTE:
数据对齐(data alignment),是指数据所在的内存地址必须是该数据长度的整数倍,这样CPU的存取速度最快。比如在32位的计算机中,一个WORD为4 byte,则WORD数据的起始地址能被4整除的时候CPU的存取效率比较高。CPU的优化规则大概如下:对于n字节(n = 2,4,8...)的元素,它的首地址能被n整除才能获得最好的性能。
为了便于下面的讨论,这里假设所用的计算机为32位,即一个WORD为4个字节。下面给出在32位计算机上的C语言实现(假设unsigned long为4个字节):
3. 源码剖析
上面给出的C语言实现虽然不算特别复杂,但也值得花点时间来弄清楚,先看9-13行:
上面的代码实现了数据对齐,如果在对齐之前就遇到'\0'则可以直接return char_ptr - str;
第15行将longword_ptr指向数据对齐后的首地址
第17行给magic_bits赋值(在后面会解释这个值的意义)
第20行读入一个WORD到longword并将longword_ptr指向下一个WORD
第22行的if语句是整个算法的核心,该语句判断22行读入的WORD中是否有为0的字节if语句中的计算可以分为如下3步:
(1) longword + magic_bits
其中magic_bits的二进制表示如下
magic_bits中的31,24,16,8这些bits都为0,我们把这几个bits称为holes,注意在每个byte的左边都有一个hole。
检测0字节:
如果longword 中有一个字节的所有bit都为0,则进行加法后,从这个字节的右边的字节传递来的进位都会落到这个字节的最低位所在的hole上,而从这个字节的最高位则永远不会产生向左边字节的hole的进位。则这个字节左边的hole在进行加法后不会改变,由此可以检测出0字节;相反,如果longword中所有字节都不为0,则每个字节中至少有1位为1,进行加法后所有的hole都会被改变。
为了便于理解,请看下面的例子:
上面longword中的b1为0,X可能为0也可能为1。因为b1的所有bit都为0,而从b0传递过来的进位只可能是0或1,很显然b1永远也不会产生进位,所以加法后longword的第16 bit这个hole不会变。
(2) ^ ~longword
这一步取出加法后longword中所有未改变的bit。
(3) & ~magic_bits
最后取出longword中未改变的hole,如果有任何hole未改变则说明longword中有为0的字节。
根据上面的描述,如果longword中有为0的字节,则if中的表达式结果为非0,否则为0。
NOTE:
如果b3为10000000,则进行加法后第31 bit这个hole不会变,这说明我们无法检测出b3为10000000的所有WORD。值得庆幸的是用于strlen的字符串都是ASCII标准字符,其值在0-127之间,这意味着每一个字节的第一个bit都为0。因此上面的算法是安全的。
一旦检测出longword中有为0的字节,后面的代码只需要找到第一个为0的字节并返回相应的长度就OK:4. 另一种实现
上面的代码与strlen_c基本一样,不同的是:
magic_bits换成了himagic和lomagic
以及if语句变得比较简单了
if语句中的计算可以分为如下2步:
(1) longword - lomagic
himagic和lomagic的二进制表示如下:
在这种方法中假设所有字符都是ASCII标准字符,其值在0-127之间,因此longword总是如下形式:
检测0字节:
如果longword 中有一个字节的所有bit都为0,则进行减法后,这个字节的最高位一定会从0变为1;相反,如果longword中所有字节都不为0,则每个字节中至少有1位为1,进行减法后这个字节的最高位依然为0。
(2) & himagic
这一步取出每个字节最高位的1,如果有任意字节最高位为1则说明longword中有为0的字节。
根据上面的描述,如果longword中有为0的字节,则if中的表达式结果为非0,否则为0。
5. 汇编实现
VC
CRT的汇编实现与前面strlen_c算法类似
1page,132
2titlestrlen-returnthelengthofanull-terminatedstring
3;***
4;strlen.asm-containsstrlen()routine
5;
6;Copyright(c)MicrosoftCorporation.Allrightsreserved.
7;
8;Purpose:
9;strlenreturnsthelengthofanull-terminatedstring,
10;notincludingthenullbyteitself.
11;
12;*******************************************************************************
13
14.xlist
15includecruntime.inc
16.list
17
18page
19;***
20;strlen-returnthelengthofanull-terminatedstring
21;
22;Purpose:
23;Findsthelengthinbytesofthegivenstring,notincluding
24;thefinalnullcharacter.
25;
26;Algorithm:
27;intstrlen(constchar*str)
28;{
29;intlength=0;
30;
31;while(*str++)
32;++length;
33;
34;return(length);
35;}
36;
37;Entry:
38;constchar*str-stringwhoselengthistobecomputed
39;
40;Exit:
41;EAX=lengthofthestring"str",exclusiveofthefinalnullbyte
42;
43;Uses:
44;EAX,ECX,EDX
45;
46;Exceptions:
47;
48;*******************************************************************************
49
50CODESEG
51
52publicstrlen
53
54strlenproc\
55buf:ptrbyte
56
57OPTIONPROLOGUE:NONE,EPILOGUE:NONE
58
59.FPO(0,1,0,0,0,0)
60
61stringequ[esp+4]
62
63movecx,string;ecx->string
64testecx,3;testifstringisalignedon32bits
65jeshortmain_loop
66
67str_misaligned:
68;simplebyteloopuntilstringisaligned
69moval,byteptr[ecx]
70addecx,1
71testal,al
72jeshortbyte_3
73testecx,3
74jneshortstr_misaligned
75
76addeax,dwordptr0;5bytenoptoalignlabelbelow
77
78align16;shouldberedundant
79
80main_loop:
81moveax,dwordptr[ecx];read4bytes
82movedx,7efefeffh
83addedx,eax
84xoreax,-1
85xoreax,edx
86addecx,4
87testeax,81010100h
88jeshortmain_loop
89;foundzerobyteintheloop
90moveax,[ecx-4]
91testal,al;isitbyte0
92jeshortbyte_0
93testah,ah;isitbyte1
94jeshortbyte_1
95testeax,00ff0000h;isitbyte2
96jeshortbyte_2
97testeax,0ff000000h;isitbyte3
98jeshortbyte_3
99jmpshortmain_loop;takenifbits24-30areclearandbit
100;31isset
101
102byte_3:
103leaeax,[ecx-1]
104movecx,string
105subeax,ecx
106ret
107byte_2:
108leaeax,[ecx-2]
109movecx,string
110subeax,ecx
111ret
112byte_1:
113leaeax,[ecx-3]
114movecx,string
115subeax,ecx
116ret
117byte_0:
118leaeax,[ecx-4]
119movecx,string
120subeax,ecx
121ret
122
123strlenendp
124
125end
6.
测试结果
为了对上述各种实现的效率有一个大概的认识,我在VC8和GCC下分别进行了测试,测试时均采用默认优化方式。下面是在GCC下运行几百万次后的结果(在VC8下的运行结果与此相似):
转载注明出处:http://www.cppblog.com/ant/archive/2007/10/12/32886.html
分享到:
相关推荐
c/c++:strlen源码
strlen、strcpy和strcmp源码
分析sizeof和strlen具体区别(源码和解析)
目的:文章对strlen 和 wcslen 以及_tcslen做了简单的介绍。 语言:C++ 编译器:VisualStudio2010 ...1、strlen & wcslen & _tcslen.zip中含有源码。 2、strlen & wcslen & _tcslen.pdf中含有函数说明。
本文介绍的是sizeof与strlen区别
使用AVX2指令集实现的strlen函数,一般情况下较新的CPU都支持avx2指令集,使用avx2指令集可以加快程序的运行速度
strlen和sizeof的区别,介绍详细,值得一看
操作符sizeof和函数strlen的区别,代码已经过测试,可以直接使用!
c语言本身有strlen函数,这个是利用递归自己写的
strlen
C语言常用函数源码 strcmp strlen atoi atol memcpy strchr strstr printf等,不可不看.公司面试的时候很容易让写出其中某些函数的源码.这些函数的源码确实简洁,高效
strlen
都是在网上下载资料,然后自己整理而成。详细的介绍了strlen和sizeof的区别和用法,这在应用程序是,有很高的帮助。
求一个字符串的长度,但不能使用函数strlen()
strcpy,strcat,strcmp,strlen,strchr
编写一个程序,求字符串的长度,不能使用strlen函数。 (代码提示:i=0;while(s[i]!= '\0')i++; 则最后i的值就是字符串长度)
strlen
c语言中最常遇到的问题是字符串处理问题,特别是字符串长度:sizeof与strlen.两者使用时一定要区分开,否着会很容易出错。本文对两者的区别做了详细介绍。
C语言中strcpy_strcmp_strlen_strcat函数原型