2009年四月月 发布的文章

GLIBC strlen源代码分析

直接操作C标准库提供的字符串操作函数是有一定风险的,稍有不慎就会导致内存问题。这周用业余时间写了一个小型的安全字符串操作库,但是测试之后才发现自己的实现有很大的性能缺陷。

在Solaris上初步做了一个简单的性能比对,以下是得到的性能数据(以strlen的数据为例):
当传入的字符串长度为10时,执行100w次:
strlen 执行时间是:32762毫秒
my_strlen执行时间是:491836毫秒

当传入的字符串长度为20时,执行100w次:
strlen 执行时间是:35075毫秒
my_strlen执行时间是:770397毫秒

很显然,标准库中strlen的消耗仅是my_strlen的十分之一不到,且其性能消耗随着字符串长度的增加并未有近线性的增加,而my_strlen则是变化明显。想必大家这时也能猜到my_strlen采用了传统的实现的方式,即采用逐个字节判断是否为''方式,这也与测试出的现象相符。本着刨根问底的精神,我在网上找到了GNU提供的C标准库中strlen实现的源码,要看看GLIBC中strlen究竟采用何种技巧才达到了那么高的性能。说实话在性能优化这方面自己一直还处于比较初级的位置,这也将是自己将来努力的一个方向。

下载了全部GLIBC的代码包,这个包还真不小。在string子目录下找到strlen.c,这就是大多数UNIX平台、Linux平台以及绝大多数GNU软件使用的strlen的实现源码了。这份代码由Torbjorn Granlund(还实现了memcpy)编写,Jim Blandy和Dan Sahlin提供了帮助和注释。包括注释在内,GLIBC的strlen的代码足足有近130行,大致浏览一下, 没有怎么看懂,可耐下心来细致阅读,还是有些心得的。下面是strlen源码摘要版,后面我将针对这段代码写一些我的理解:
 
  1 /* Return the length of the null-terminated string STR.  Scan for
  2    the null terminator quickly by testing four bytes at a time.  */
  3 size_t strlen (str)  const char *str;
  4 {
  5         const char *char_ptr;
  6         const unsigned long int *longword_ptr;
  7         unsigned long int longword, magic_bits, himagic, lomagic;
  8
  9         /* Handle the first few characters by reading one character at a time.
 10            Do this until CHAR_PTR is aligned on a longword boundary.  */
 11
 12         for (char_ptr = str; ((unsigned long int) char_ptr
 13              & (sizeof (longword) – 1)) != 0;
 14              ++char_ptr)
 15                 if (*char_ptr == '')
 16                         return char_ptr – str;
 17
 18         /* All these elucidatory comments refer to 4-byte longwords,
 19            but the theory applies equally well to 8-byte longwords.  */
 20
 21         longword_ptr = (unsigned long int *) char_ptr;
 22
 23         himagic = 0x80808080L;
 24         lomagic = 0x01010101L;
 25
 26         if (sizeof (longword) > 8)
 27                 abort ();
 28
 29         /* Instead of the traditional loop which tests each character,
 30            we will test a longword at a time.  The tricky part is testing
 31            if *any of the four* bytes in the longword in question are zero.  */
 32
 33         for (;;)     
 34         {                        
 35                 longword = *longword_ptr++;    
 36
 37                 if ( ((longword – lomagic) & himagic) != 0)
 38                 {
 39                         /* Which of the bytes was the zero?  If none of them were, it was
 40                            a misfire; continue the search.  */
 41
 42                         const char *cp = (const char *) (longword_ptr – 1);
 43
 44                         if (cp[0] == 0)
 45                                 return cp – str;
 46                         if (cp[1] == 0)
 47                                 return cp – str + 1;
 48                         if (cp[2] == 0)
 49                                 return cp – str + 2;
 50                         if (cp[3] == 0)
 51                                 return cp – str + 3;
 52                         if (sizeof (longword) > 4)
 53                         {
 54                                 if (cp[4] == 0)
 55                                         return cp – str + 4;
 56                                 if (cp[5] == 0)
 57                                         return cp – str + 5;
 58                                 if (cp[6] == 0)
 59                                         return cp – str + 6;
 60                                 if (cp[7] == 0)
 61                                         return cp – str + 7;
 62                         }
 63                 }
 64         }
 65 }

从这段代码开头作者的注释我们大致可以了解到该strlen实现的原理:就是通过每次测试四个字节来代替传统实现中每次测试一个字节的方法。知道这个原理了,那么还需要解决两个难题:
1) C标准库要求有很好的移植性,在绝大部分系统体系结构下都应该能正确运行。那么每次拿出4个字节比较(unsigned long int),就需要考虑内存对齐问题,传入的字符串的首字符地址可不一定在4对齐的地址上;
2) 如何对四个字节进行测试,找出其中某个字节为全0,这是个技巧问题。

12~21行的代码解决的就是第一个问题:
      for (char_ptr = str; ((unsigned long int) char_ptr
             & (sizeof (longword) – 1)) != 0;
             ++char_ptr)
                if (*char_ptr == '')
                        return char_ptr – str;

        /* All these elucidatory comments refer to 4-byte longwords,
           but the theory applies equally well to 8-byte longwords.  */

        longword_ptr = (unsigned long int *) char_ptr;
作者通过一个for-loop找到传入字符串中第一个地址对齐到4的字符的地址,由于该地址已经对齐到4,所以最后一行那个强制转型是安全的。虽然可以通过圆整算式直接得到该对齐地址,但是考虑到这个区间可能存在的'',一个字符一个字符比对也是不可避免的。在很多严格对齐的架构上(比如SUN的SPARC平台),编译器一般会将字符串地址在编译器就放到对齐的地址上,这样一来,实际执行strlen时for-loop很少能执行一步。

第二个问题作者则是通过一个"带前提"的技巧来解决的。作者设定了两个掩码变量:
 himagic = 0x80808080L;
 lomagic = 0x01010101L;
并通过一个conditional expression完成了对四字节中全0字节的检测:((longword – lomagic) & himagic) != 0
我们将himagic和lomagic按bit展开:
himagic   1000 0000 1000 0000 1000 0000 1000 0000
lomagic   0000 0001 0000 0001 0000 0001 0000 0001

对于这样的代码,似乎没有什么理论可以遵循,需要在实践中去理解。起初我构造了一个不含全0字节的longword,比如:
longword  1000 0001 1000 0001 1000 0001 1000 0001,然后按照那个条件表达式计算后,居然也满足!=0的条件,是不是作者的逻辑有问题呢?后来转念一想,这种逻辑是有“前提条件”的。回顾一下strlen是做什么的,其输入参数是任意的么?当然不是。输入的字符串中每个字符的值都在[0, 127]的ascii码范围内,也就是说每个字节最高位的bit都是0,这样longword就应该是如下这个样子了:
longword  0xxx xxxx 0xxx xxxx 0xxx xxxx 0xxx xxxx

基于这样的前提我们考虑两种情况:
当longword中没有全0字节时,比如:
longword 0000 0001 0000 0001 0000 0001 0000 0001
这样在做完计算后,值为0,不满足条件。

当longword中有全零字节时,比如:
longword 0000 0000 0000 0001 0000 0001 0000 0001
这样在做完计算后,最高字节最高bit的值肯定为1,满足!=0条件,全0字节被检测出来。也就是说一旦有全0字节,在减去lomagic时势必会产生借位,全0的那个字节在减去lomagic后最高位bit肯定由0变1,这样与himagic一与,肯定不为0,就是这么检测出来的。

这一方法在64位平台依然适用,上面的代码摘要中省略了对64bit平台的特殊处理,为的是使代码逻辑更清晰,更易读。

梅西·与巴萨一起碾碎拜仁

2009年4月9日凌晨2点45分(北京时间),2008-09赛季欧洲冠军联赛四分之一决赛开始了首回合较量,西甲豪门巴萨坐镇主场诺坎普迎来了德甲巨 人拜仁慕尼黑的挑战。八强抽签结束后,巴萨躲过了英超四强的包围圈却遭遇了德甲NO.1拜仁,不过媒体和博彩公司依旧看好巴萨,巴萨和曼联并列赔率榜首 位。拜仁本赛季的表现很不稳定,既有欧冠赛场两回合大比分屠杀里斯本竞技的记录,也有在刚刚进行的联赛中大比分被沃尔夫斯堡血洗的耻辱。不过拜仁的哀兵姿 态也让巴萨全队格外重视,毕竟拜仁是欧洲足球最具代表性的球队之一,任何时刻他们都有进球得分和翻盘的实力,队中的里贝里和托尼也都是久经沙场的精英,所 以此役巴萨主帅瓜迪奥拉也排出了巴萨最强阵,以争取在主客场两回合的比赛中占据有利位置,要知道先主后客的比赛可不好打。

与 人们事先预测的基本一致,巴萨主力阵容中,巴尔德斯继续镇守龙门,马科斯和皮克坐镇中路防守,万金油普队顶替受伤的阿比达尔打左后卫,阿尔维斯则一如以往 的出现在右翼;中场则由西班牙国家队核心哈维和伊涅斯塔领衔,图雷辅助增加中场硬度,前锋线依旧是目前欧洲乃至世界攻击力最强的三叉戟组合:亨利、埃托奥 和梅西。针对巴萨的控球优势,拜仁主帅克林斯曼排出了加强中场的4-5-1阵容:老门将布特替代本赛季的主力门将伦辛首发,因卢西奥的受伤,拜仁的后卫线 捉襟见肘,奥多、德米凯利斯、布雷诺和莱尔出任首发,中场则是由队长范博梅尔领衔,老将泽-罗伯托、大阿尔滕托普、小猪施魏因斯泰格和里贝里辅佐,前锋线 则是单箭头高个子托尼。

刚一开场,巴萨队员就表现出了很好的气势和状态。第6分钟,梅西右路发起进攻,中路哈维得球后直塞给亨利,亨利反 越位成功,在角度很小的角度打门,可惜球速太慢,球在入门前被对方后卫解围,不过这次进攻给了拜仁众将士一个下马威。巴萨角球,哈维和梅西配合,梅西右路 突破射门,再次被后卫挡出。不过巴萨的进攻依旧潮水般涌向拜仁后方。第9分钟,擅于打大赛的梅西为巴萨打入开罐之球。亨利左路发起进攻,中路哈维和埃托奥 接球后连续横敲,被打懵的拜仁后卫居然露了后点的梅西,梅西拿球后,前突几步,直面门将冷静左脚推射,球直挂打门左下角,1:0。梅西进球后也是格外兴 奋,并用手势带动主场观众一起庆祝。

img{512x368}
梅西射门瞬间

img{512x368}
梅西射门瞬间

img{512x368}
梅西进第一球后疯狂庆祝

img{512x368}
梅西进第一球后疯狂庆祝

img{512x368}
梅西庆祝面部特写

仅仅三分钟过后,状态极佳的梅西再次帮助E9打入锁定胜局之球。梅西右路拿球招牌式内切,禁区右路突然送出直塞球,埃托奥在与对方后卫平行位置快速启动,在门将封堵前射门,球从布特小门穿过应声入网,2:0。入球后的埃托奥再次与亨利做出了本赛季新发明的敬礼式庆祝动作。

巴 萨取得梦幻般开局,场面打的更加开了,巴萨队员细腻的传球让拜仁队员几乎拿不到球。仅有左路的里贝里几次灵光的突破,不过没有致命威胁。第17分钟,场上 出现意外局面,梅西禁区内拿球变线突破莱尔,莱尔伸腿将梅西绊倒在禁区里,全场目光瞬间都集中在主裁判身上,意外的是当值主裁并没有判罚点球,而是对梅西 出示黄牌,认为梅西禁区内假摔,不过慢镜回放多次,这的确是莱尔的犯规,不过这件事还未结束,场外巴萨主帅瓜迪奥拉发狂似的怒吼和抗议也同样招致主裁的红 牌惩罚,不得不被请上了观众看台,如果说巴萨这一夜是完美的,那唯一的一点点瑕疵就是裁判的误判以及瓜帅的冲动。

img{512x368}
梅西禁区内被绊倒

场 上的巴萨球员并未因这一插曲而受到任何影响,而是一如既往的进攻。全场巴萨球员跑动十分积极,三叉戟尤其;镜头里经常看到梅西、埃托奥和亨利的协防以及丢 球的奋力的就地反抢。这样的努力再次在第38分钟收到效果。亨利左路纳球,突然一个加速突破了奥多的防守,底线横穿中路,身材矮小但却极其机敏灵活的梅西 在门前三名高大中后卫的干扰下倒地铲射,皮球第三次滚入球网,疯狂梅西梅开二度。镜头里气急败坏的拜仁队长范博梅尔在大声训斥着中后卫德米凯利斯。而这边 巴萨队员正在疯狂的庆祝着。

img{512x368}
梅西倒地铲射打入本场第二粒进球

img{512x368}
梅西庆祝个人第二粒进球

0:3 落后的拜仁球员似乎受到了自信心上的打击,不过巴萨队员依旧没有放弃进攻。第43分钟,梅西又来了。梅西突入禁区,范博梅尔肘击梅西,后者痛苦倒地,拜仁 后卫顺势解围,球却落到了左路无人盯防的亨利脚下,亨利顺势推射皮球入网,比分锁定在4:0。进球后,大家围拢到梅西处,观察梅西伤势,慢镜回放,这一肘 力度不小,不过梅西还是坚韧的站了起来。就这样巴萨带着4粒金子般的入球结束了上半场。

下半场,已经四球领先的巴萨显然放慢了进攻步伐,不过控制场面的还是巴萨。梅西甚至还有多次上演帽子戏法的机会,不过布特的精彩补救以及马里人凯塔的头没能让梅西带帽。

全场比赛结束,巴萨首回合4:0大胜,基本上100%挺进欧冠四强了。这样的魔鬼赛程的开局,让巴萨从上到下士气大振,今年的巴萨有戏!已经打入8球的梅西独占欧冠射手榜榜首,同样本赛季已经打入32球的梅西正向着他的首个欧洲金球奖奖杯和世界足球先生的荣誉大踏步前进着。


微博:@tonybai_cn
微信公众号:iamtonybai
github.com: https://github.com/bigwhite

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats