煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
ncream 2017-10-31 11:00
[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
你試下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
compiler 一早做晒 constant folding 啦。
居然仲剩低個乾 loop 係度...
唔係 0ms 已經偷笑
code4food 2017-11-8 15:08
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 17:27
[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 20:57
[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 21:04
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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來講用咩分別不大。
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
煙民母親生賤種
*** 作者被禁止或刪除 內容自動屏蔽 ***
code4food 2017-11-10 05:53
[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]