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

[討論] 不用if做if(x < 0) x = 0; 與if(x > 25 …

看板C_and_CPP (C/C++)作者 (啤酒肚)時間15年前 (2011/02/14 01:38), 編輯推噓6(6推 0噓 58→)
留言64則, 6人參與, 最新討論串1/1
(是YUV轉RGB的其中一部份) short R; : : if(R < 0) R = 0; 上面這程式，能否不要用if呢? 我做法是這樣: #define MIMUS_SIGN 0x8000 /* 1000 0000 0000 0000*/ #define IS_POSITIVE(XX) ( 1 - ( (XX) & MIMUS_SIGN) >>15) ) char bitand_map[2] = {0x00, 0xff}; #define BYTE_AND(XX, SIGN) ( (XX) & bitand_map[(SIGN)] ) #define MINUS_BE_ZERO ( XX) BYTE_AND_BIT( XX, IS_POSITIVE (XX) ) : R = MINUS_BE_ZERO( R); 這程式用到了 bitand_map 這表，且在IS_POSITIVE 用了一個 bit and ，一個平移與一個減法，量有點多。 在想有沒辦法更精簡。 有人有建議的嗎? 另外，對於 if(R > 255) R = 255; 這要不用if來優化就難了。。 (R >> 8) | (R >> 9) | (R >> 10) | (R >> 11) | (R >> 12) | (R >> 13) | (R >> 14) 看0或是1再用上面的查表法做bit and.... 這樣做太多次平移與bit or 還不如直接用if 有人有類似經驗的嗎? 謝謝指教 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.115.143.194
→
02/14 01:48, , 1F
最近大家都跟 if 有仇就對了
02/14 01:48, 1F
→
02/14 01:50, , 2F
你探討的問題很低階, bit shift, bit and/or, 哪個比較
02/14 01:50, 2F
推
02/14 01:50, , 3F
換組合語言or硬體繞線接 你想搞定問題 還是讓C搞你?
02/14 01:50, 3F
→
02/14 01:50, , 4F
快都要看你的機器和 compiler ... 如果你分析的結果
02/14 01:50, 4F
→
02/14 01:51, , 5F
hot spot 的確在那上面的話 ... 我想你也只能用組語
02/14 01:51, 5F
→
02/14 01:52, , 6F
搞定 ... SSE 或是 MMX 指令集都可以用
02/14 01:52, 6F
→
02/14 01:53, , 7F
能用SIMD的 應該不會問這問題 XD
02/14 01:53, 7F
→
02/14 01:54, , 8F
最終使用環境不是x86平台 不能用SSE
02/14 01:54, 8F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 01:55)
→
02/14 01:56, , 9F
分析過hot spot，就是在這些if上。
02/14 01:56, 9F
→
02/14 01:58, , 10F
如果你平台上的指令集也不能解決這個問題 ... 換硬體
02/14 01:58, 10F
→
02/14 01:58, , 11F
可能會比較快 orz, 除非你要手動幹掉 hazard 或是
02/14 01:58, 11F
→
02/14 01:59, , 12F
arm的cpu + 機器人操作系統。。。
02/14 01:59, 12F
→
02/14 01:59, , 13F
cache miss 這種非人哉的偉業
02/14 01:59, 13F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 02:00)
→
02/14 02:00, , 14F
增加緩存命中率這方法試過，不過不同手機緩存大小不同
02/14 02:00, 14F
→
02/14 02:00, , 15F
很難有統一的優化法
02/14 02:00, 15F
推
02/14 02:07, , 16F
好吧, 如果你真的很堅持的話 ... 通常 cmp 是作 sub
02/14 02:07, 16F
→
02/14 02:08, , 17F
但如果改成只用 and 就會比較快, 所以 U > 255 的地方
02/14 02:08, 17F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 02:11)
→
02/14 02:10, , 18F
可能可以改成 U & 0xFF00, 避掉一次加法器
02/14 02:10, 18F
→
02/14 02:11, , 19F
結果會怎樣還是要看硬體 ...
02/14 02:11, 19F
→
02/14 02:14, , 20F
U & 0xFF00 不行吧，最後一個bit是正負號，該是0x7f00吧
02/14 02:14, 20F
→
02/14 02:17, , 21F
呃, 抓到意思就好, 我怎麼知道最後你是要不要 sign QQ
02/14 02:17, 21F
→
02/14 02:20, , 22F
以前試過在x86上，if用mask(and)來做會比用cmp來快約5趴
02/14 02:20, 22F
→
02/14 02:21, , 23F
但分析過主要開銷還是在branch上(緩存不命中)
02/14 02:21, 23F
→
02/14 02:21, , 24F
所以想有沒辦法根本不用if
02/14 02:21, 24F
推
02/14 02:24, , 25F
小弟有點疑問, 請問您的轉換公式是?? 查了一下YUV2RGB或
02/14 02:24, 25F
→
02/14 02:25, , 26F
反轉, 應該沒有用到branch啊?? 本來猜是不是用全整數運
02/14 02:25, 26F
→
02/14 02:25, , 27F
算需要clamp, 可是處理的對象又是source....@_@"
02/14 02:25, 27F
→
02/14 02:26, , 28F
是YUV to RGB。。轉換時可能會暴表 所以要用if
02/14 02:26, 28F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 02:27)
→
02/14 02:27, , 29F
啊對不起, 我查到fixed用的公式是有clamp沒錯....Orz
02/14 02:27, 29F
推
02/14 02:27, , 30F
有的CPU會在overflow的時候設為最大值,但我不知道ARM
02/14 02:27, 30F
→
02/14 02:28, , 31F
ARM確定是沒有 x86也沒有 :)
02/14 02:28, 31F
→
02/14 02:28, , 32F
有沒有...否則就是觀察branch miss看是哪邊的機率高
02/14 02:28, 32F
→
02/14 02:28, , 33F
疑, 可是查了一下YUV2RGB是clamp結果不是source啊@_@"
02/14 02:28, 33F
→
02/14 02:29, , 34F
再手動 predict
02/14 02:29, 34F
→
02/14 02:30, , 35F
02/14 02:30, 35F
→
02/14 02:30, , 36F
看到修文了, 不好意思....:)
02/14 02:30, 36F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 02:32)
→
02/14 02:32, , 37F
不過這已經算是人工解決 control hazard 了吧 @@
02/14 02:32, 37F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 02:36)
→
02/14 02:37, , 38F
可能從定義域或值域的range來把bitmask設得更精簡嗎??
02/14 02:37, 38F
→
02/14 02:41, , 39F
想過，因為暴出來就從256~251之間 所以理論上只要檢查第
02/14 02:41, 39F
→
02/14 02:41, , 40F
9個bit是否為0或1即可
02/14 02:41, 40F
→
02/14 02:42, , 41F
"若"是0就對第一到第八個bit做 bit and 0xff
02/14 02:42, 41F
→
02/14 02:43, , 42F
反之設為 0xff
02/14 02:43, 42F
→
02/14 02:43, , 43F
但這樣等於沒優化 因為用了個 if
02/14 02:43, 43F
推
02/14 02:45, , 44F
為什麼?? 不是跟負數一樣用個bit array就好了嗎??
02/14 02:45, 44F
→
02/14 02:46, , 45F
小弟想到的是 OR 0x00 或 0xFF....@_@"
02/14 02:46, 45F
→
02/14 02:47, , 46F
當然8th bit以上要一律AND 0掉, 這樣判斷<0先跑再跑>255
02/14 02:47, 46F
→
02/14 02:47, , 47F
應該可以吧....@_@"
02/14 02:47, 47F
→
02/14 02:52, , 48F
of=(R&0x0100)>>8; R = (R | bitmap[of]) & 0xFF;
02/14 02:52, 48F
→
02/14 02:53, , 49F
of用途同SIGN, bitmap就是bitand_map[]那個這樣@_@"
02/14 02:53, 49F
→
02/14 02:54, , 50F
了解了 用or_map[2] = {0x00, 0xff};
02/14 02:54, 50F
→
02/14 02:55, , 51F
在將節果與這個表bit or即可
02/14 02:55, 51F
→
02/14 02:55, , 52F
剛一直想到包絡線問題(另個類似的問題)，兩個搞混，。。
02/14 02:55, 52F
→
02/14 02:56, , 53F
謝謝VictorTom :)
02/14 02:56, 53F
※ 編輯: DrStein 來自: 58.115.143.194 (02/14 02:57)
→
02/14 02:59, , 54F
不會啦XD
02/14 02:59, 54F
→
02/14 09:45, , 55F
哪一顆 ARM ? ARMv6 的指令有 sat 可以用阿...
02/14 09:45, 55F
→
02/14 09:49, , 56F
google "yuv rgb arm" 有人家寫好的組合語言加速版 試試吧
02/14 09:49, 56F
推
02/14 13:23, , 57F
要加速用CUDA不是比較快嗎...
02/14 13:23, 57F
→
02/14 13:37, , 58F
非x86，只有少數的平板電腦能用CUDA
02/14 13:37, 58F
→
02/14 21:59, , 59F
如果能夠full lookup, 可以用查表指令 xlat試試
02/14 21:59, 59F
→
02/14 22:00, , 60F
小弟也覺得, 要是有低階指令可以做sat可能是最快的XD
02/14 22:00, 60F
→
02/14 22:05, , 61F
再看了一次推文發現你說 overhead 在branch, 但在 arm 上
02/14 22:05, 61F
→
02/14 22:05, , 62F
這種 code 可以很直覺的交給 compiler 轉 cond execution
02/14 22:05, 62F
→
02/14 22:06, , 63F
最佳化開下去那種 code 不應該生出 branch 的
02/14 22:06, 63F
→
02/14 22:07, , 64F
手邊的 arm gcc 開個 -O1 就會轉了
02/14 22:07, 64F
‣ 更多 DrStein 的文章
文章代碼(AID): #1DM1SG6k (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DrStein 的文章
文章代碼(AID): #1DM1SG6k (C_and_CPP)