Re: [問題] glibc 2.7 strlen.c

作者: johnjohnlin (嗯?)   2015-04-28 23:24:06
試著練習一下
37 /* Handle the first few characters by reading one character at a time.
38 Do this until CHAR_PTR is aligned on a longword boundary. */
39 for (char_ptr = str; ((unsigned long int) char_ptr
40 & (sizeof (longword) - 1)) != 0;
41 ++char_ptr)
42 if (*char_ptr == '\0')
43 return char_ptr - str;
這邊註解寫的很清楚
把 char pointer 對齊到 long* 的位置
這樣之後我們一次就可以比一個 long
59 magic_bits = 0x7efefeffL;
60 himagic = 0x80808080L;
61 lomagic = 0x01010101L;
62 if (sizeof (longword) > 4)
63 {
66 magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
67 himagic = ((himagic << 16) << 16) | himagic;
68 lomagic = ((lomagic << 16) << 16) | lomagic;
69 }
70 if (sizeof (longword) > 8)
71 abort ();
magic number 先跳過
不過方便起見之後假設 long 是 4B
76 for (;;)
77 {
107 longword = *longword_ptr++;
這個跟你的寫法差不多
不過他現在就是要一次比 4B
108
109 if (
122 ((longword - 0x01010101) & 0x80808080)
124 != 0)
125 {
整個程式裡面神奇的只有這個
我把 magic number 展開了
如果 4B 裡面有 0
那麼每個 byte 減掉 1 的時候就會退位
導致該 byte 前面的 byte 的 MSB 是 1
128
129 const char *cp = (const char *) (longword_ptr - 1);
130
131 if (cp[0] == 0)
132 return cp - str;
133 if (cp[1] == 0)
134 return cp - str + 1;
(下略)
承上
會進來這邊就是他認為這 4B 裡面有可能 0x00
這邊就是把 loop 展開
作者: EdisonX (卡卡獸)   2015-04-28 23:30:00
vc 也是用這種作法 , 只是它已包成了 strlen.asm ,所以..
作者: OPIV (Monitor)   2015-04-28 23:32:00
抱歉...J大 我不太了解loop展開的意思意思是,把原本的逐位檢查改成if()if()if()嗎?
作者: LiloHuang (十年一刻)   2015-04-28 23:34:00
作者: johnjohnlin (嗯?)   2015-04-28 23:43:00
loop unrolling
作者: PkmX (阿貓)   2015-04-29 01:31:00
glibc的實作真變態 比我用AVX2一次比對32 bytes還要快...https://gist.github.com/PkmX/ea6ee1e0b56187006e80
作者: johnjohnlin (嗯?)   2015-04-29 12:45:00
測試了一下,發現真的會快一點點,到底為什麼啊
作者: PkmX (阿貓)   2015-04-29 13:08:00
可能glibc的版本我的cpu的micro-architecture比較喜歡吧XDrz不過基本上差距都在5%以內 所以可接受
作者: TobyH4cker (Toby (我要當好人))   2015-04-29 16:02:00
應該是有對齊比較符合CPU的運作方式這部分只要看編譯後的asm就能比較了
作者: PkmX (阿貓)   2015-04-29 18:58:00
我的AVX2版本也有先對齊啊XDrz
作者: LiloHuang (十年一刻)   2015-04-29 20:41:00
因為 glibc 的實作裡頭有 SSE2 的版本也有 SSE4詳見 http://goo.gl/kzQ9sX剩下就是得分析此情況下 AVX2 跟 SSE4 為啥會輸了 :P這篇比較的表格也許可以看看 http://goo.gl/G04iPI說不定你的 glibc 剛好有 AVX2 實作也不一定 XD用 gdb 下個斷點 step into 進去 strlen 看看應該可知
作者: johnjohnlin (嗯?)   2015-04-29 22:39:00
我比較的對象是上一篇那個純 C 的實作另外我有點好奇這樣不會出現違規存取的問題嗎?我電腦裡面的是 SSE2 實作,速度跟純 C 很接近
作者: PkmX (阿貓)   2015-04-30 08:25:00
基本上你的memory access都是align在4或8 bytes上不會有跨越page的問題 所以在x86上面ok

Links booklink

Contact Us: admin [ a t ] ucptt.com