作者johnjohnlin ()
看板C_and_CPP
標題Re: [問題] glibc 2.7 strlen.c
時間Tue Apr 28 23:24:06 2015
試著練習一下
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 展開
--
其實我只是把註解翻譯而已 w
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.175.53
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1430234649.A.AAD.html
推 EdisonX: vc 也是用這種作法 , 只是它已包成了 strlen.asm ,所以.. 04/28 23:30
推 OPIV: 抱歉...J大 我不太了解loop展開的意思 04/28 23:32
→ OPIV: 意思是，把原本的逐位檢查改成if()if()if()嗎? 04/28 23:33
→ johnjohnlin: loop unrolling 04/28 23:43
→ PkmX: glibc的實作真變態 比我用AVX2一次比對32 bytes還要快... 04/29 01:31
→ johnjohnlin: 測試了一下，發現真的會快一點點，到底為什麼啊 04/29 12:45
→ PkmX: 可能glibc的版本我的cpu的micro-architecture比較喜歡吧XDrz 04/29 13:08
→ PkmX: 不過基本上差距都在5%以內 所以可接受 04/29 13:09
→ TobyH4cker: 應該是有對齊比較符合CPU的運作方式 04/29 16:02
→ TobyH4cker: 這部分只要看編譯後的asm就能比較了 04/29 16:03
→ PkmX: 我的AVX2版本也有先對齊啊XDrz 04/29 18:58
推 LiloHuang: 因為 glibc 的實作裡頭有 SSE2 的版本也有 SSE4 04/29 20:41
推 LiloHuang: 剩下就是得分析此情況下 AVX2 跟 SSE4 為啥會輸了 :P 04/29 20:46
→ LiloHuang: 說不定你的 glibc 剛好有 AVX2 實作也不一定 XD 04/29 20:51
→ LiloHuang: 用 gdb 下個斷點 step into 進去 strlen 看看應該可知 04/29 20:52
→ johnjohnlin: 我比較的對象是上一篇那個純 C 的實作 04/29 22:39
→ johnjohnlin: 另外我有點好奇這樣不會出現違規存取的問題嗎？ 04/29 22:39
→ johnjohnlin: 我電腦裡面的是 SSE2 實作，速度跟純 C 很接近 04/29 22:42
→ PkmX: 基本上你的memory access都是align在4或8 bytes上 04/30 08:25
→ PkmX: 不會有跨越page的問題 所以在x86上面ok 04/30 08:26