查看完整版本 : bitwise shift 並唔係傳說中咁快

煙民母親生賤種 2017-10-31 10:43 AM

bitwise shift 並唔係傳說中咁快

:fst_016::fst_016::fst_016:

好多人鐘意用 rightshift / leftshift 代替 X ,  /
[url=http://rextester.com/YOCV87104]http://rextester.com/YOCV87104[/url]
[attach]7512338[/attach]

ncream 2017-10-31 11:00 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-31 10:43 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470173181&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
:fst_016::fst_016::fst_016:

好多人鐘意用 rightshift / leftshift 代替 X ,  /
[url=http://rextester.com/YOCV87104]http://rextester.com/YOCV87104[/url]
7512338 [/quote]

寫快速開方最岩用。不過都唔夠拉馬克開方法快。:smile_o05:

Susan﹏汪汪 2017-10-31 11:16 AM

你試下Del左個for loop就咁行
[code]
sw1.start();

    cout<< "r = div10(1024) " << r << " N: " << N << " takes " << sw1.elapsed() <<"ms"<< endl;
[/code]

stupidsing 2017-11-1 09:04 AM

compiler 一早做晒 constant folding 啦。
居然仲剩低個乾 loop 係度...
唔係 0ms 已經偷笑

code4food 2017-11-8 03:08 PM

bitwise shift同加係間單ALU指令。整數成份一般只係慢小小。如果你用一大串shift同加代替乘法,你會慢過就咁用乘。舉例Intel Skylake。register only嘅shift同加latency係1個cycle。乘係3個cycle,除係23個cycles。如果shift同加嘅組合太複雜,咁不如用乘數算。除數做strength reduction會大D機會有著數。如果除數係constant,可以用shift,甚至用乘同shift嚟代替。詳情可以睇一本叫“Hacker's Delight”嘅書。

[url=http://www.agner.org/optimize/instruction_tables.pdf]http://www.agner.org/optimize/instruction_tables.pdf[/url] 231頁
[url=http://www.hackersdelight.org/]http://www.hackersdelight.org/[/url]

ncream 2017-11-8 05:27 PM

[quote]原帖由 [i]code4food[/i] 於 2017-11-8 03:08 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470566375&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
bitwise shift同加係間單ALU指令。整數成份一般只係慢小小。如果你用一大串shift同加代替乘法,你會慢過就咁用乘。舉例Intel Skylake。register only嘅shift同加latency係1個cycle。乘係3個cycle,除係23個cycles。如 ... [/quote]

我發覺用c寫swap。用+係快過bitwise小小。

sswroom 2017-11-8 08:57 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-8 05:27 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470572591&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


我發覺用c寫swap。用+係快過bitwise小小。 [/quote]真正睇速度, 不是睇單一運算, 而是睇運算的目的........
例如這個Function:[code]Int32 Test(Int32 a, Int32 b)
{
    return a * 5 + b * 10 + 13;
}[/code]正常Gen出來的Assembly Code(Windows x64)會是:[code]Test:
lea ecx, [ecx+edx*2]
lea eax, [ecx+ecx*4+13]
ret[/code]完全不用Add, Mul等數學運算指令。還有, Shift Constant才會快, Shift Variable會較慢

ncream 2017-11-8 09:04 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-8 08:57 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470583299&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
真正睇速度, 不是睇單一運算, 而是睇運算的目的........
例如這個Function:Int32 Test(Int32 a, Int32 b)
{
    return a * 5 + b * 10 + 13;
}正常Gen出來的Assembly Code(Windows x64)會是:Test:
lea ecx, [e ... [/quote]

Thx指點。ching

我依家寫sorting寫到sort sort地。好複雜數學。:smile_o16:

code4food 2017-11-9 07:54 AM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-8 04:57 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470583299&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
還有, Shift Constant才會快, Shift Variable會較慢[/quote]
要睇ISA同實際implementation。上面Intel Skylake嘅例子shift amount係constant同響register係一樣咁快。我以前用過有CPU嘅variable shift要用兩個指令嚟做,第一指令先準備,第二個係真係做shift動作。

code4food 2017-11-9 07:59 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-30 06:43 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470173181&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
:fst_016::fst_016::fst_016:

好多人鐘意用 rightshift / leftshift 代替 X ,  /
[url=http://rextester.com/YOCV87104]http://rextester.com/YOCV87104[/url]
7512338 [/quote]


benchmark 可以咁寫[code]// make this global
volatile int x;

r = x;
for (i = ...) {
   r = div10(r)
}
x = r;[/code]

code4food 2017-11-9 08:04 AM

[quote]原帖由 [i]ncream[/i] 於 2017-11-8 01:27 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470572591&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


我發覺用c寫swap。用+係快過bitwise小小。 [/quote]XOR swap 呢招而家無乜用,除非你寫assembly又剛剛唔夠register同(例如interrupt handler)。[url=http://computer.discuss.com.hk/viewthread.php?tid=14199030]http://computer.discuss.com.hk/viewthread.php?tid=14199030[/url]

sswroom 2017-11-9 08:34 AM

[quote]原帖由 [i]code4food[/i] 於 2017-11-9 08:04 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470599952&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
XOR swap 呢招而家無乜用,除非你寫assembly又剛剛唔夠register同(例如interrupt handler)。[url=http://computer.discuss.com.hk/viewthread.php?tid=14199030]http://computer.discuss.com.hk/viewthread.php?tid=14199030[/url] [/quote]
Assembly用XOR Swap有甚麼好處?

為何不這樣寫: (Register不足時)[code]mov eax,a
xchg b,eax
mov a,eax[/code]Register足夠時: (理論上較快)[code]mov eax,a
mov edx,b
mov b,eax
mov a,edx[/code]還可以: (Register極度不足時)[code]push a
push b
pop a
pop b[/code]

Susan﹏汪汪 2017-11-9 08:41 AM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-9 08:34 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470600878&ptid=27027290][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]

Assembly用XOR Swap有甚麼好處?

為何不這樣寫: (Register不足時)mov eax,a
xchg b,eax
mov a,eaxRegister足夠時: (理論上較快)mov eax,a
mov edx,b
mov b,eax
mov a,edx還可以: (Register極度不足時)push  ... [/quote]
push pop唔會慢?

ncream 2017-11-9 09:01 AM

[quote]原帖由 [i]code4food[/i] 於 2017-11-9 08:04 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470599952&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
XOR swap 呢招而家無乜用,除非你寫assembly又剛剛唔夠register同(例如interrupt handler)。[url=http://computer.discuss.com.hk/viewthread.php?tid=14199030]http://computer.discuss.com.hk/viewthread.php?tid=14199030[/url] [/quote]

Ching,多謝指教小弟。

我比較過呢兩個swap:

void xorSwap (int *x, int *y) {
    if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
}



void addSwap (unsigned int *x, unsigned int *y) {
     if (x != y) {
         *x = *x + *y;
         *y = *x - *y;
         *x = *x - *y;
     }
}

發覺add係快小小。

[url=https://en.wikipedia.org/wiki/XOR_swap_algorithm]https://en.wikipedia.org/wiki/XOR_swap_algorithm[/url]

至於呢個:

temp = x;  /* 1 */
x = y;     /* 2 */
y = temp;  /* 3 */
最直觀,我試下先。:smile_o06:

不過可能GCC compiler 同你轉晒最快既machine code。所以點寫都係差唔多。:smile_o08:

[[i] 本帖最後由 ncream 於 2017-11-9 09:10 AM 編輯 [/i]]

sswroom 2017-11-9 09:16 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-9 08:41 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470601137&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

push pop唔會慢? [/quote]睇CPU, 有些CPU的Optimization Guide話PUSH/POP最快, 因為完全沒有Dependency.......

Susan﹏汪汪 2017-11-9 09:20 AM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-9 09:16 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470602511&ptid=27027290][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
睇CPU, 有些CPU的Optimization Guide話PUSH/POP最快, 因為完全沒有Dependency....... [/quote]
Optimization guilde講push/pop最快
係以咩做比較?

mov registers同mov indirect memory 應該唔同

sswroom 2017-11-9 09:32 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-9 09:20 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470602720&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Optimization guilde講push/pop最快
係以咩做比較?

mov registers同mov indirect memory 應該唔同 [/quote]當年是睇如果減少Register Dependency, Register Dependency會令速度下降, 這部分有個例子就是做Memory Swap時建議用push/pop取代mov
你可以下載Optimization Guide看, AMD Optimization Guide和Intel Optimization Guide都是免費下載的

code4food 2017-11-9 09:33 AM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-8 04:34 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470600878&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Assembly用XOR Swap有甚麼好處?

為何不這樣寫: (Register不足時)mov eax,a
xchg b,eax
mov a,eaxRegister足夠時: (理論上較快)mov eax,a
mov edx,b
mov b,eax
mov a,edx還可以: (Register極度不足時)push  ... [/quote]

我寫過類似BIOS嘅code,有時RAM係sleep state,唔會有stack俾你push同pop。咁如果又唔夠register時可以用XOR swap,但99.99999999%嘅programmer都唔會遇到呢類情況。

ncream 2017-11-9 09:35 AM

[quote]原帖由 [i]ncream[/i] 於 2017-11-9 09:01 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470601899&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


Ching,多謝指教小弟。

我比較過呢兩個swap:

void xorSwap (int *x, int *y) {
    if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
}



void addSwap (unsi ... [/quote]


比較過,其實差別真係好細,完全睇唔到有咩分別。

可能gcc 已經選擇最好既code。

但今次又學到野。:smile_o13:

ching你地好勁。我都要努力寫好個自家quick sort先。

[[i] 本帖最後由 ncream 於 2017-11-9 09:37 AM 編輯 [/i]]

code4food 2017-11-9 09:38 AM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-8 05:16 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470602511&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
睇CPU, 有些CPU的Optimization Guide話PUSH/POP最快, 因為完全沒有Dependency....... [/quote]
其實有memory dependency同埋stack pointer有dependency。不過CPU可能做store forwarding。

Susan﹏汪汪 2017-11-9 09:40 AM

[quote]原帖由 [i]ncream[/i] 於 2017-11-9 09:35 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470603371&ptid=27027290][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]



比較過,其實差別真係好細,完全睇唔到有咩分別。

但今次又學到野。:smile_o13: [/quote]
Swap operation做速度測試
sample太細、measurement error又咁大

好難做到比較

ncream 2017-11-9 09:43 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-9 09:40 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470603628&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Swap operation做速度測試
sample太細、measurement error又咁大

好難做到比較 [/quote]

我又係用個個program,1億個數,做quick sort swap。

同一組數,總之差唔多,用咩都影響唔大。

:smile_o13::smile_o13:

Susan﹏汪汪 2017-11-9 09:46 AM

[quote]原帖由 [i]ncream[/i] 於 2017-11-9 09:43 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470603802&ptid=27027290][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


我又係用個個program,1億個數,做quick sort swap。

同一組數,總之差唔多,用咩都影響唔大。

:smile_o13::smile_o13: [/quote]
因為只係個for loop increments
都同個swap operations 係一比一嘅速度

最終量度出來的時間、當中swap operations 佔據的時間都唔知有冇20%

[[i] 本帖最後由 ncream 於 2017-11-9 11:34 AM 編輯 [/i]]

Susan﹏汪汪 2017-11-9 11:11 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-9 09:46 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470603916&ptid=27027290][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]

因為只係個for loop increments
都同個swap operations 係一比一嘅速度

最終量度出來的時間、當中swap operations 佔據的時間都唔知有冇20%


我睇10%都無。所以對成個program來講用咩分別不大。 [/quote]
版主要睇清楚編輯同回覆:lol

ncream 2017-11-9 11:34 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-9 11:11 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470608145&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

版主要睇清楚編輯同回覆:lol [/quote]

SORRY,搞錯左。:smile_o14::smile_o14::smile_o04::smile_o04:

我睇10%都無。所以對成個program來講用咩分別不大。

煙民母親生賤種 2017-11-10 05:20 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-9 11:11 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470608145&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

版主要睇清楚編輯同回覆:lol [/quote]唉..... 做咩叫「版主」咁見外... 你都係友壇版主啦! :fst_006:

煙民母親生賤種 2017-11-10 05:22 AM

[quote]原帖由 [i]code4food[/i] 於 2017-11-9 07:59 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470599844&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]



benchmark 可以咁寫// make this global
volatile int x;

r = x;
for (i = ...) {
   r = div10(r)
}
x = r; [/quote]

授教! :fst_011:

好耐無見閣下, 去左邊度玩多? :fst_002:

code4food 2017-11-10 05:53 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-11-9 01:22 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470647497&ptid=27027290][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


授教! :fst_011:

好耐無見閣下, 去左邊度玩多? :fst_002: [/quote]

呢期好忙,多數做CD-ROM。
頁: [1]
查看完整版本: bitwise shift 並唔係傳說中咁快