PTT數位生活區 / C_and_CPP (C/C++)

Re: [問題] glibc 2.7 strlen.c

看板C_and_CPP (C/C++)作者時間9年前 (2015/04/28 23:24), 編輯推噓5(5推 0噓 19→)
留言24則, 6人參與, 最新討論串2/2 (看更多)
試著練習一下 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
推
04/28 23:30, , 1F
vc 也是用這種作法 , 只是它已包成了 strlen.asm ,所以..
04/28 23:30, 1F
推
04/28 23:32, , 2F
抱歉...J大 我不太了解loop展開的意思
04/28 23:32, 2F
→
04/28 23:33, , 3F
意思是，把原本的逐位檢查改成if()if()if()嗎?
04/28 23:33, 3F
推
04/28 23:34, , 4F
04/28 23:34, 4F
→
04/28 23:43, , 5F
loop unrolling
04/28 23:43, 5F
→
04/29 01:31, , 6F
glibc的實作真變態 比我用AVX2一次比對32 bytes還要快...
04/29 01:31, 6F
→
04/29 12:45, , 8F
測試了一下，發現真的會快一點點，到底為什麼啊
04/29 12:45, 8F
→
04/29 13:08, , 9F
可能glibc的版本我的cpu的micro-architecture比較喜歡吧XDrz
04/29 13:08, 9F
→
04/29 13:09, , 10F
不過基本上差距都在5%以內 所以可接受
04/29 13:09, 10F
→
04/29 16:02, , 11F
應該是有對齊比較符合CPU的運作方式
04/29 16:02, 11F
→
04/29 16:03, , 12F
這部分只要看編譯後的asm就能比較了
04/29 16:03, 12F
→
04/29 18:58, , 13F
我的AVX2版本也有先對齊啊XDrz
04/29 18:58, 13F
推
04/29 20:41, , 14F
因為 glibc 的實作裡頭有 SSE2 的版本也有 SSE4
04/29 20:41, 14F
→
04/29 20:42, , 15F
04/29 20:42, 15F
推
04/29 20:46, , 16F
剩下就是得分析此情況下 AVX2 跟 SSE4 為啥會輸了 :P
04/29 20:46, 16F
→
04/29 20:51, , 17F
這篇比較的表格也許可以看看 http://goo.gl/G04iPI
04/29 20:51, 17F
→
04/29 20:51, , 18F
說不定你的 glibc 剛好有 AVX2 實作也不一定 XD
04/29 20:51, 18F
→
04/29 20:52, , 19F
用 gdb 下個斷點 step into 進去 strlen 看看應該可知
04/29 20:52, 19F
→
04/29 22:39, , 20F
我比較的對象是上一篇那個純 C 的實作
04/29 22:39, 20F
→
04/29 22:39, , 21F
另外我有點好奇這樣不會出現違規存取的問題嗎？
04/29 22:39, 21F
→
04/29 22:42, , 22F
我電腦裡面的是 SSE2 實作，速度跟純 C 很接近
04/29 22:42, 22F
→
04/30 08:25, , 23F
基本上你的memory access都是align在4或8 bytes上
04/30 08:25, 23F
→
04/30 08:26, , 24F
不會有跨越page的問題 所以在x86上面ok
04/30 08:26, 24F
‣ 更多 johnjohnlin 的文章
文章代碼(AID): #1LFwOPgj (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 johnjohnlin 的文章
文章代碼(AID): #1LFwOPgj (C_and_CPP)