やる夫が(インライン)アセンブラを使って競技プログラミングに挑戦するようです
この記事はCompetitive Programming Advent Calendar Div2013の9日目の記事です。
今年も、競技プログラミングでほとんど役に立たないネタをお送りします。
1:名無しのターゲットさん:2013/12/9(月) 00:25:07 id:jetbead
! | !l |! ! | ! | ! l | ! l |! | !ll |! l |!| !l | ! ! | !l |! ! | ! !ll |! l !| l !ll |! l !| | ! l il i (ヽ======== | |! ! | ! | ! l | l | !| ! l | ! l ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ある日の競技プログラミング終了直前のやる夫家 |! l |! ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ! l ! | | l | ! l |! | | ! l |! l l |! ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ !l |! ! | ! i | ! l i !i li | ! l ! ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ ! ! | | ! | ! l | !l |! ! | ! li ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ !l ! ! | | ! | ! l | !l |! ! ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ ! | !l |! ! | ! | ! l | ! l |! | ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ノ ̄ | ! | ! l | ! l | ! l |! | @二|二|二|二|二|二|二|二|二|二| | ! l | ! l |! | !ll |! l |!| | ! |二二二|二二二|二二二|二二 ! | | ! | ! l | !l |! ! | | ! |二二二|二二二|二二二|二二
2:名無しのターゲットさん:2013/12/9(月) 00:25:25 id:jetbead
____ / \ / ─ ─\ あー、これ、TLEあやしいお / (●) (●) \ | (__人__) | ________ \ ` ⌒´ ,/ .| | | ノ \ | | | /´ | | | | l | | | ヽ -一ー_~、⌒)^),-、 | |_________| ヽ ____,ノγ⌒ヽ)ニニ- ̄ | | | ____ / ― \ /ノ ( ●) \ | ( ●) ⌒) | | (__ノ ̄ / でも書き直してる時間ないし、たぶん大丈夫。そのまま提出するお | / \_ ⊂ヽ∩\ /´ (,_ \.\ | / \_ノ ____ / \ /:::::::─三三─\ System> yaranaio successfully challenged yaruo's 500-point problem. /::::::::: ( ○)三(○)\ | 、" ゙)(__人__)ル ゚。 ゚ ___________ \ ゝ'゚ ≦ 三 ゚ | | | __/ 。≧ 三 = | | | | | / , -ァ, ≧= .| | | | | / / .イレ,、 > | | | | | | ⌒ ーnnn ,≦`Vヾ ヾ ≧ |_|___________|  ̄ \__、("二)。゚ /。・イハ 、\、l二二l二二 _|_|__|_
5:名無しのターゲットさん:2013/12/9(月) 00:35:12 id:jetbead
___ ;;/ ノ( \; ;/ _ノ 三ヽ、_ \; なんでよりによって やらない夫 に撃墜されるんだお!! ;/ノ(( 。 )三( ゚ )∪\; ;.| ⌒ (__人__) ノ( |.; ..;\ u. . |++++| ⌒ /; >やらない夫家 / ̄ ̄\ / _ノ \ | ( ●)(●) | (__人__) | ` ⌒´ノ 500はTLEしそうなコードはとりあえず最大ケースでチャレンジっと | } ヽ } ヽ、.,__ __ノ _, 、 -― ''"::l:::::::\ー-..,ノ,、.゙,i 、 /;;;;;;::゙:':、::::::::::::|_:::;、>、_ l|||||゙!:゙、-、_ 丿;;;;;;;;;;;:::::i::::::::::::::/:::::::\゙'' ゙||i l\>::::゙'ー、 . i;;;;;;;;;;;;;;;;;;;;;;|::::::::::::::\::::::::::\ .||||i|::::ヽ::::::|:::!
16:名無しのターゲットさん:2013/12/9(月) 00:50:58 id:jetbead
/´ ̄ ̄ ̄  ̄ ヽ / \ /::::: \ _______ + /::::::::: ヽ |i:¨ ̄ ,、  ̄¨.: i |::::::::::: | |i: /ヘ:\ :i| _ |::.:. : : ,,ノ:..:ヾ、 | 250も落としたし、もう引退かお・・・ .|i:〈`_、/´_`>.、 :i| ,.r:;"三ヽ:: :: . ー""´ ,,、 ー‐‐,, /`、 |ii~~"、;"´`,"~,;~~~~:i|;イ:;:":::::::::::\;;。(ー一) (ー一)。;:;:. /::::: ヽ |i`::;:":::::;::;:"::::::::::;.:i|`。⌒/7, -──〜 、(___人___,)"⌒;;::/::|:::::〆::\ |i::::::;:":::::::::::::::::::::::i| ::::://,::::.. " ニニヽ、⌒ij~";_ ィ /:::::::|:::::〃::: : ヽ ─|`ー=====一 | ::::::|_|;;、:::.__y-ニニ"ー-ァ ゚‐─"───┴────── ‐
20:名無しのターゲットさん:2013/12/9(月) 00:55:26 id:jetbead
/:::/::::/::::::::::::l::::::::|:::::::l:::::::::l:::::::::::::::::::::ヽ:::::::::::::::::::::i:::::: /::;イ::::i::::::::::::::| ::::::l|;::::::li;::::::::|、;::::::::::::::::::::l:::::::::::::::::::::l::::: .l::/ l:::::|::::::::::::/!::::::| li::::::lヽ::::::l. ヽ;:::::::::::::::::l::::::::::::::::::::l:::::: |::l | ::::|::::::::-i-L;;_l .|!i:::::l ヽ::::l ヽ、__;;;;::::| :::::::::::::::::l:::: |:! .|::::::l::__;;;|_ l:::l`ヽヽ;:::l ヾ;レ‐'''゙゙´\ :::::| ::::::::::::::::l::::: l! .|:::/ ___ノ,ィ'ト|''=ミ、 ヾ! ,r-=fニミ;;弍;;| :::::::::::::::l~゙'i あきらめるのはまだ早い! l/ ,/ト、::l゙__゙ヾ::ii::|ヽ ,/ .|:::illi:::゙ii/ |:::::::::::::::j¨゙ l あなたのコード、通せていた可能性がある /⌒ヾ、|/`fト l ゙K);j .l'⌒''h. K);;;;ッリ l:::::::::::::/ .ノ /‐-、 `iノ /'ヽ|、 ノ ヾ、 ,/ |:::::::::::/=7゙ ./ 、. ヽ |゙V,_ l:::i、 ̄ 丶 ゙''ー-‐'' ,l::::::::::/|:;/ i '゙ヽ_j-' .|::::|.\ ‐- ,,イ::::::::/ ,l/ ヽ ヽ jl:::::l. ヽ、 , ''゙ /:::::::/゙`ヽ、 ヽ、. /ヽ::::| ,,`=ー '''i´ /:;/レ'〉;:;:;:;:,.,\ / /. ヽ:| ,,r''゙,.;:;:;r''゙~ノ /イ /;:;:;:;:;:;:;:;:;:; ___ / \ /ノ \ u. \ あんた誰だお!? / (●) (●) \ っていうか、なんで家の中にいるの?? | (__人__) u. | \ u.` ⌒´ / ノ \ /´ ヽ / ヽ \ \ ,' / / l \ ヽ ! / / / ,' | l ハ ヘ、ヽ、_, . | ! l l / / ,イ ! i ! l ヽ ',` ̄ . l | l l ,/ 〃 ,/ /│ l j l│ ! l ノ | ! │ | /_// // / ,' ∧ / | / j l│ ノ l ァ| |尢/‐=乞t/ / /∠ニ「厂! / ,/ / リ わたしは「名無しのターゲット」 イ 八{´l !レ<f{矛:下 'ヽ 〃イ孑代勹 イ } / 雨宿りさせてもらっている . Vハ | r';;_zj r';;zリ / , '// ヽ ', | 、 / / `ヘ lヽ _ 厶 ./ ', {.代ト、 , イ | / \_'i| > 、 _ , イ/ V l./ / ヽj {`ヽ ′ . _ / 「´ ヽ} \ _, -‐ ´ l‐--‐、 _ -‐ | ` ー- 、 . r<\\ ヽ '´ ̄ ___ `ヽl| / /ヽ
32:名無しのターゲットさん:2013/12/9(月) 01:10:19 id:jetbead
ノ L____ ⌒ \ / \ / (○) (○)\ / (__人__) \ 家宅侵入だお! | |::::::| | 警察に通報するお!! \ l;;;;;;l /l!| ! / `ー' \ |i / ヽ !l ヽi ( 丶- 、 しE |そ ドンッ!! `ー、_ノ �堯�l、E ノ < レY^V^ヽl /.:.:. \ /:,:.:.: / ヽ \ /.:.l:.:.:/:/ :/ ', :l ヾ`ー /!:.:.|:.: l/ 〃 / j } :| ハ /イ:.:.i|:.:.jL∠/_/ | /l.ム_/| l l } N:.ハ:.:.:lィfアト/ レ ィ=ト | /| ∧j bit操作でforループを回していた ヽム:.} c;_j c;リ ル iレヽ そこをもし「インラインアセンブラ」で書いていたら・・・ `ヘ:ゝ .' 小/ ヾ:{>、 _ ィ<}/|/ _, ィr'´ヽ{ ___`} ヽ、_ /| l:| | ===| |:l゙ヽ / | l:l l l l::l l ___ / \ /ノ \ u. \ イ、インラインアセンブラっ!? / (●) (●) \ | (__人__) u. | \ u.` ⌒´ / ノ \ /´ ヽ
40:名無しのターゲットさん:2013/12/9(月) 01:18:46 id:jetbead
_ .. --==ニ¨ `ヽ- ―- 、 .._ニ-‐ァ―――- :.‐'´ .. \ アセンブリ言語・・・ /´ /:ィ/:_. - ´ .:/ ヽ: \:.. {:. ヽ { \/∠ -'_二 :// .:/ ヽ: lヽ:. ヽ:.\:| それは、機械に直接命令を与える、古のプログラミング言語・・・ /´ フ´ .:// / :/ | } |:. ト:. l:. \_ / / .:ィ :/ /ノ :/ | / { :|:. ∧ :!|:. l:. `ヽ ̄´ //i :/ / ィ /{ .:!:ハォ:7 丁「「:. }:. | l ! トヽ 今や、それを扱えるのは一部のプログラマーのみとなってしまった・・・ / | ..:!/イ7´丁ミヽト{ /'ァz=≠トv .ト: | | | | /| ../|{ fr筰ミト ´ ´ヤぅ刈イ: ト.}: :|!| しかし、今でも、gccではコード中にアセンブリ言語を埋め込むことが可能・・・ ∧! !:/ 小.`辷:リ `フ7′/.:レ } ハ /{イ:/ハ '_ /´/:. /l: /′ / ´ |l j .:.\ ‘ニ’ /: ,.. ノ}// それが、「インラインアセンブラ」・・・!! ハ ̄ ̄ ̄`ヽl>ュ.. _ イ:イイムハ{ _ノ{_ ノ ̄ ̄ ̄ ‐- 、 ヽ/} |/_j_.ゝ┴‐´三弐 ≦三三三-_ _ \ト/´__.. -==―――`i、 l!  ̄`ヽzzzzf´ ̄ lト} rヘ | _ | l| { ノ、__i! fヽ ! | ハ |ハ { __,、! _| {| ! | __ | ! ヽ ノ{_l! }ハ、 ヽハ. ヽ /´'/ lト.、| ト、 _,l!___ {. l\ ` ー \j { __j-:、:\ レ| {ト:ヽヽ:`ヽ._ ̄` |-‐ニ-――-、::ヽ| _ 上L._ ヽ\\ヽ:ト.二、 {´_: -‐  ̄ `ト、:ヽ{ /´:.:.:.:.:.:_`ヽ }/ >`-/7く_> 、 ` ー‐- 、 ! ヽ:} ⌒ヽ- ´{ `ヽ:\{:.:,.孑{zトミ:.:`ヽミヽ、 ├‐ ´ \ ノ7ァニj彳_/:{`ヽ〉_/`j┬ \ j  ̄ /:リ: : : : /:.:.| ̄  ̄` Lト、 ト、 / /:/ : : : / : :j : : : : : : : | : :  ̄:} ` ー‐' j/! l ! . !: l/! j/! ! / ∧! ヽl lヽ、 ´’ /!:/ あなたのコードを書き直すと・・・ ヽ! j/ト- ィl/ j/ . r‐l ト、 l -┬<´ : ト -―l : `ー┬ 、 | !|__ /.::: ::::!: l l : : l二二 ! : : : : ! ! : ト、!! `ヽヽ 〃 __|l /l ヽ|! :::: l ::l: :l !: : :! l : : : : l l: : ! /|ト、_ ノノ l| / ヽ_ノ! ! トヘl| :::! l !: :`ヽヽ l: : : : :// :// ! `ヽ!| ! 、、 ! ヽヽ ! !|ヽl__!|ノヽ ノノ / : : : // /∧ ∧ |!|\!| ! ノノ j|_∧ l| l ヽ_ノ\ !| \l_ノ /( _j|∠ノ  ̄ /! ∧  ̄!| ̄ノ / ! _ノヽ、_!lノ_.. -―ヽ ヽ从/ ムヽ、!|_ ノ__ / l| /从` ー‐l|<_ __ノ´ !ヽ、_ノ__ >ー‐人ヽ、 \ ≧ !::::::::::::)\! !/ ≦‐-、! ノ \:::::::::::::::::::::::::≦ ヽ、_\ `> |:::::::≦ \j / `>  ̄  ̄ ̄ ̄ ̄ ̄∨ ̄ ̄ ̄ ̄ ̄∨ ̄ ̄ ̄ ̄ ̄∨ ̄ ̄ ̄ ̄ ̄∨ ̄ ̄ ̄ ̄ ̄
41:名無しのターゲットさん:2013/12/9(月) 01:18:51 id:jetbead
//1がセットされているビットのポジションを返す int bsr(int N){ int b,pos = 0; for(b=(N>>1),pos=0; b!=0; pos++) b >>= 1; return pos; }
↓
//1がセットされているビットのポジションを返す int bsr(int N){ int pos = 0; asm volatile ("bsrl %1, %0" : "=r" (pos) : "r" (N)); return pos; }
63:名無しのターゲットさん:2013/12/9(月) 01:42:13 id:jetbead
____ / \ / ─ ─\ / (●) (●) \ asm・・・なんか見たことない文字が並んでるお・・・ | (__人__) | / ∩ノ ⊃ / ( \ / _ノ | | .\ “ /__| | \ /___ / /.:.:. \ /:,:.:.: / ヽ \ /.:.l:.:.:/:/ :/ ', :l ヾ`ー /!:.:.|:.: l/ 〃 / j } :| ハ /イ:.:.i|:.:.jL∠/_/ | /l.ム_/| l l } N:.ハ:.:.:lィfアト/ レ ィ=ト | /| ∧j 「asm volatile (...);」がインラインアセンブラのコード ヽム:.} ii;_j ii;リ ル iレヽ `ヘ:ゝ. _ 小/ 括弧の中に、専用の命令を書くと、そこは機械に直接命令されるコードになる ヾ:{>、 _ ィ<}/|/ _, ィr'´ヽ{ ___`} ヽ、_ /| l:| | ===| |:l゙ヽ / | l:l l l l::l
70:名無しのターゲットさん:2013/12/9(月) 01:45:21 id:jetbead
/.:.:. \ /:,:.:.: / ヽ \ /.:.l:.:.:/:/ :/ ', :l ヾ`ー /!:.:.|:.: l/ 〃 / j } :| ハ /イ:.:.i|:.:.jL∠/_/ | /l.ム_/| l l } N:.ハ:.:.:lィfアト/ レ ィ=ト | /| ∧j あなたのコードはこのbsr()がかなり呼び出されている ヽム:.} ii;_j ii;リ ル iレヽ `ヘ:ゝ. _ 小/ 確認のため、TopcoderサーバーでNに1から(1<<26)=67,108,864まで入れて、ループ回してみると・・・(※) ヾ:{>、 _ ィ<}/|/ _, ィr'´ヽ{ ___`} ヽ、_ 元のbsr() : 約1440ms /| l:| | ===| |:l゙ヽ 書き直したbsr() : 約85ms / | l:l l l l::l (※)SRM144DIV2、200の問題で、「for(int i=1; i<(1<<26); i++){ if(-1 == bsr(i)) return ""; }」をいれてみて、Run System Testでの時間を見ています。 ____ /_ノ ヽ、_\ ミ ミ ミ o゚((●)) ((●))゚o ミ ミ ミ 今までどんだけ遅いの使ってたんだおwww!! /⌒)⌒)⌒. ::::::⌒(__人__)⌒:::\ /⌒)⌒)⌒) | / / / |r┬-| | (⌒)/ / / // 速くなりすぎだおwwwww!!!! | :::::::::::(⌒) | | | / ゝ :::::::::::/ | ノ | | | \ / ) / ヽ / `ー'´ ヽ / / | | l||l 从人 l||l l||l 从人 l||l ヽ -一''''''"~~``'ー--、 -一'''''''ー-、 ヽ ____(⌒)(⌒)⌒) ) (⌒_(⌒)⌒)⌒)) ____ / \ /\ キリッ . / (ー) (ー)\ / ⌒(__人__)⌒ \ これを使えば通せてたお! | |r┬-| | \ `ー'´ / これからはインラインアセンブラの時代だお! ノ \ /´ ヽ | l \ ヽ -一''''''"~~``'ー--、 -一'''''''ー-、. ヽ ____(⌒)(⌒)⌒) ) (⌒_(⌒)⌒)⌒))
240:名無しのターゲットさん:2013/12/9(月) 05:03:58 id:jetbead
i ________ ゚ i /________ヽ ゚ 。 ; || i |./||。 ! || 。i 。 i ゜ ; ||// .. || 。 / || i 。 i ; ; ゚ ||/ 。 || // || 。 3時間後・・・。 i ゜ . || ∧,,∧ ||/ 。 || ゚ 。 。 . ||(´・ω・)||/ 。 || i ; i ゚ ゜ ||/ |。.|| || i 。 ; ゜ | ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄|; ゜ 。 i ゜  ̄ ̄ ̄゜ ̄ ̄ ̄ ̄ ̄ ; ゜ i i i i
254:名無しのターゲットさん:2013/12/9(月) 05:08:00 id:jetbead
____ /ノ ヽ、_\ /( ○)}liil{(○)\ 手元とサーバーでの挙動が違うおおおおお!! / (__人__) \ | ヽ |!!il|!|!l| / | \ |ェェェェ| / ____ /ノ ヽ、_\ /( ○)}liil{(○)\ なんか最適化オプションあるなしで挙動が変わったおおおおお!!! / (__人__) \ | ヽ |!!il|!|!l| / | \ |ェェェェ| / ____ /ノ ヽ、_\ /( ○)}liil{(○)\ たくさん命令ありすぎてどれ使えばいいかわからないおおおおおおおおお!!!!!! / (__人__) \ | ヽ |!!il|!|!l| / | \ |ェェェェ| /
307:名無しのターゲットさん:2013/12/9(月) 07:47:05 id:jetbead
/ ̄ ̄ ̄\ / ─ ─ \ ア...ア...アセンブラ... / <○> <○> \. | (__人__) | コンパイルエラー...ァ..ア゙ア゙ア゙!!! \ ` ⌒´ / / \
308:名無しのターゲットさん:2013/12/9(月) 07:47:15 id:jetbead
, ‐'´ `ヽ、 _/ / / \ ー=ァ'´/ /.., ´ 〃 / ヽ:.. ::::::ヽ /イ/ .:/ .::/: .::/ / .,′ ..:ハ::.. ::::::::: 〃 / .:/ .::/:: .:::/.:::l::: ::| {:. .::::|:::::::::::: l /' ,′.:::l .:::l::.__:/ !:/{:::. .::! ::ヽ:. ::::|::::::::::::::.....| | ::/:::j ::::l:::::/゙`i:ト ',:::..::::l、.:::!ヽ::...:::|:::::::::::::::::::| l ::{:::!ハ::::|代尓ミkハ::::::::iム七弋 :::l:::::::::::::::::::l それ以上いけない!! ∨N':::ヽ:{' rf;;;i./` \:::{ ィテ与、:j::::,::::::j :::八 ィァ'´ ̄l :::::lヽゝー' \ rf;;j /リ::,' :::/:/l:! むやみにインラインアセンブラを使ってはいけない。コンパイラと競合してしまう! / ノ>、ハ::::::l ' ''‐ ' /:::/:::/}/. リ ハ. l" /__,∧ ::ト、 っ /:::/:::/ノ―- 、 ノ j│ レ'´/,∧:ヽ \ ィ':/;イ(: : : : : : : `ー- 、 . /‐^! l fン'う \l/}iヽ、 _,, <〃::/ " ヽ: : : : : : : : : : : `ー-―‐-、 / ∧ rイ ∧ _j /-= ' , ィ_ニ二>、: : : : : : : : : : : : : : : : : :ヽ __ ,r'¬/ 〉 ハ / `、. / // , イ⌒ `ヽ: : : : : : : : : : : : : : : : : : : : : : /´ 〃 \_/ } .∧ー―‐/ / / / ヽ: : : : : : : : : : : : : : : : : : : : : / ̄ ̄ ̄\ / ─ ─ \ コンパイラ ト キョウゴウ・・・? / <○> <○> \. | (__人__) | \ ` ⌒´ / / \ /, | /:: , l:: i::. }::ヽヽ::.ヽ \ .// .:! :| : /:::/:/::/i: /: !: }i:',ヽ:| i,i .::| :|: :: !,/_ム/_ l:/::: l:: !l::! i::! . ! l .: : .::::| :i:.:: レ',ソ,_/`!::/i:/ i:! | コンパイラとは、あなたの書いたコードを機械に命令するコードに変換するプログラム・・・ . !.:! ::. : .:.::/´', !::: | ! ヾ.i´:i` !/ / ! i:l', :::::. :. ::. ::〈 、'_゙il::::. |.| j_ソ ゙、_ あなたが直接機械に命令するコードを書いてしまうと、コンパイラの変換時におかしくなる可能性がある ヽヽ、:::::::::. :::.::::\ニ',::. ii::! ノ ヾ、i::::l::::l::::',:| ',::. !',! ィ´ 今、あなたはコンパイラの仕事を邪魔してしまっている・・・ i|ヾ:!:::i::::/ヽ ヽ. l 丶. / ノ /ii/lノ ヽ:r‐y┬ ' イ'"`'‐- 、 / ヽl/ ' / \__{ヽ、 /_,, -‐‐‐-- ,,_ \_,ヽ‐、
315:名無しのターゲットさん:2013/12/9(月) 07:48:20 id:jetbead
/.:.:. \ /:,:.:.: / ヽ \ /.:.l:.:.:/:/ :/ ', :l ヾ`ー /!:.:.|:.: l/ 〃 / j } :| ハ /イ:.:.i|:.:.jL∠/_/ | /l.ム_/| l l } N:.ハ:.:.:lィfアト/ レ ィ=ト | /| ∧j 「g++ -O2 -S ファイル名」とすれば、コンパイラが変換した後のアセンブリコードが.sファイルに出力される ヽム:.} ii;_j ii;リ ル iレヽ `ヘ:ゝ. _ 小/ さっきのコードは、これを直接書いていたことになる ヾ:{>、 _ ィ<}/|/ _, ィr'´ヽ{ ___`} ヽ、_ これが機械に命令されることになるが、うまくコンパイラと合わせないとおかしな命令が実行されることになる /| l:| | ===| |:l゙ヽ / | l:l l l l::l
320:名無しのターゲットさん:2013/12/9(月) 08:02:23 id:jetbead
____ / ノ \\ / (●) (●)\ / ∪ (__人__) \ ちょちょちょ、ついていけないお・・・ | ` ⌒´ | \ /⌒)⌒)⌒) //⌒)⌒)⌒) っていうか、難しくて何言ってるか全然わからないお! ノ | / / / (⌒) / / / / /´ | :::::::::::(⌒) ゝ :::::::::::/ | l | ノ / ) / ヽ ヽ_ヽ /' / / ヽ __ / / / __ ´: : : : : : : ̄ ̄ 、 / : : : : : : : : : : : : : : : : : :\ . / : : : : : : : : : : : : . . .\ 、__//. /. . . . . . . . . . . : : ! : : : : ヽ  ̄/. : /. : : : :/ : : : : : : : : : : : \l: : : : : : :ヽ . l : : l : / : /. :/ : : ヽ、: : : `ヽ : !: :l: : : : : ヽ、 l :/ l : l: : :l :∧: :ト、: lヽ、: : : :ヽ!: :l: :l: : : l  ̄ l/!: ! : l: :/l/‐-ヽ! ヽ ! _ヽ-―!‐ !: :l: : : ! ヽ! : l : ! rfチミ、 ヽ´ fr旡ミ! : ト、l : : ′ . ヽ !: :l rっソ 匕り !: : !丿/j/ 難しくはない・・・ただ、直接的な書き方ができるだけ・・・ . j∧ :ト、 `¨ . l l :l j/ V: :lヽ、 _ /j/!/ 理解するためにはコンピュータがどのような仕組みで動いているか、の知識も必要になってくる ヽ: ! > __.. ィ ト、〃 ヽ! //j ト!/\ それに、CPUの種類によって命令の種類が違うため、CPUまで意識しなければいけない・・・ _/ :/-―――-l : : : :ヽ、__ /|::|: : : :! -―――-! : : : : : :/∧ _____ /! !::!: : : :! ̄  ̄ ̄/. : : : : :/://:! ∨ ̄ ̄ ̄ ̄ ̄  ̄ ̄ ̄ ̄ ̄∧ /. : : : : :/://.:::l . ∨ ∧ /. : : : : :/://.::::::l
333:名無しのターゲットさん:2013/12/9(月) 08:10:10 id:jetbead
____ / \ んー、やっぱり難しいし、注意が必要だし、危険な気がするお / ⌒ ⌒ \ / (●) (●) \ もっと知識を付けてから使った方がよさそうだお | 、" ゙)(__人__)" .)| ___________ \ 。` ⌒゚:j´ ,/ j゙~~| | | | __/ \ |__| | | | | | / , \n|| | | | | | / / r. ( こ) | | | | | | ⌒ ーnnn |\ (⊆ソ .|_|___________|  ̄ \__、("二) ̄ ̄ ̄ ̄ ̄l二二l二二 _|_|__|_ _,..-'⌒ ' ̄` ‐ 、 / / .: ::. ::::::::..ヽ _,/ ハ ::..ヽ::::::::.ヽ 確かに、そう・・・  ̄フ / { 人 ト、 :::::l:::::::::::ヘ | l l i八iゝ、 l ヽト |:::|i::ゝ それに、あなたは、より適切なアルゴリズムを考えられるようになることの方が大切・・・ {ハ| { i__レ__ゝ ヽj __j_Vl ::::::!::レト | ノ ト{ ィfァッ ィfテ、i::::::|/:/ 蟻本を3周解いてから使うべき・・・ \ ヘ{ iトi. 辷ソ . 辷ノ|::::/ヘ{ {ミi⌒f.} i ト、 _ ノi::/ ─ {ニ} o } 〉 !ト! ゝ、 .._ ,.. ィ'´ j! ヽ`´ノ _,-─ '´/ {\ | `‐´} /i || レニ二ニi ` ̄/ヽ }:::::::lr´::::::i !! !====! //::| /:::::::::ト、:::::::::i || i i //::::::i ____ /⌒ ⌒\ ホジホジ /( ●) (●)\ ・・・ /::::::⌒(__人__)⌒::::: \ | mj |ー"´ | 10年後かな・・・ \ 〈__ノ / ノ ノ
651:名無しのターゲットさん:2013/12/9(月) 13:05:35 id:jetbead
/./. . . . . . . . . . . . . . . . . . . . . \ ヽ_..イ. ./. . /. . /. . . . . . . . . .ヽ . . . \ . \ /. ././. . /. . . ./. . . . . i. . . . . . .ヽ. . . . .', . . \ /. . ././. . /. . . ./. .l. . . . .|. . . . . . . ヾ. . . . .',. .',. .ヽ /. . ././. . /./. . .j. . .|. . . . .|. . . . . . . . .',. . . . .',. .',ヽ._\ j . ./ ..|. . .|. |. . . |. . .|. . . . .|, .ヽ . . . . . .', . . . ..l. . l  ̄ インラインアセンブラはより低級な命令を書くことができるが、人が扱うにはあまり適していない | ./. /.|. . .|. |. . . |. . .|. . . . .|ヽ. . \. . . ..l. . . . .|. . | 'イ. ./. |. . .|-|−-l- 、|\.. .| \ z ‐ヽ−|. . . .:.| . ハ コンパイラの最適化が良くない場合に、ファイナルウェポンとして使うのがよい |. .l!. .|. . .|. |._ | . /ヽ ヽ. | '´ \. . ヽ!. . .:.:.|. | | |. .|l. .|. . .|. く.イ.干≧ミ ヽl ィ≦干下>. . . j. / jイ Ⅵハ..|. . .| 代ュ ::}.l 、 ,r .代ュ ::}.lイ. . . .イ./ ハ ..小イ 弋辷ソ }_{. 辷匕リ }. //.レ , イハj. ハ、 リ⌒ヽ. rォ/ ̄ ̄ ヽ /: :.| ;;;|∧ >==''′- `==イ| |! | _/: : : : | ;;;; V l > .. _ .. < |._.| ト、ー―‐へ / 〃: : : ヽ: :l .;;;; |ー 、 , -rf 1 j ヽ.V;; /: /} /: : : :_ : : ヽハ. ;;;; |ー‐、 z‐| ! }//:// //: : : ―--:: ニュ:ハ. ;;;;. |二ヽ.\/z二ト、 /}〃: :/へ /: : : : : : : : 二>' V:\ ;;;. | \二/ ∧ :  ̄: : : :V-く: : :/ ´  ̄ ̄ ̄ ̄ ̄く / : : : : : : : : : : : : : : : : : :\ . / : : : : : : : : : : : : . . .\ 、__//. /. . . . . . . . . . . : : ! : : : : ヽ  ̄/. : /. : : : :/ : : : : : : : : : : : \l: : : : : : :ヽ . l : : l : / : /. :/ : : ヽ、: : : `ヽ : !: :l: : : : : ヽ、 l :/ l : l: : :l :∧: :ト、: lヽ、: : : :ヽ!: :l: :l: : : l  ̄ l/!: ! : l: :/l/‐-ヽ! ヽ ! _ヽ-―!‐ !: :l: : : ! ヽ! : l : ! rfチミ、 ヽ´ fr旡ミ! : ト、l : : ′ 最後に、いくつか例をあげておく . ヽ !: :l rっソ 匕り !: : !丿/j/ . j∧ :ト、 `¨ . l l :l j/ これらは、Marathon系で高速化などに使える可能性がある(使えないかもしれない・・・) V: :lヽ、 _ /j/!/ ヽ: ! > __.. ィ しかし、このページの内容を実行して、何か損害(レートの激減など)を出した場合、責任をとれないので、 rヾ  ̄ || lr‐ 'フ, '/ |ヾ| ! | ! ,',ヘ ヾヽ|| / ∠- ァ! \| !__ヽ 自己責任で使用してほしい /! ヽ | |||/ r--'ヽヽ `ー、ヽ ¨ァ ,' 〉 ヽ !_/ ,、┬、二ゝニ \ ヽ!/│ ! / / | ィ´ ! ! | \_ |_ ! | ! ,,.イヾ \ 」〉 |│ ! /| / ハ| ! | / ヽヾ ´/ | ! ,、,、 |〈 ヽイ//ヽ
707:名無しのターゲットさん:2013/12/9(月) 17:45:56 id:jetbead
rdtsc
- Read Time Stamp Counter命令
- CPUクロックと同等の精度(単位ns(ナノ秒))時間を計測できる
- 精密さやマルチプロセス、複数コアなど考えないといけない場合は、もうちょっと考えないといけないかもしれないので注意
- rdtscp使う、とか
修正(12/09):コメントで、i386では"=A"でもよいが、x86_64では以下のように取得しないといけないとご指摘をいただきました。Marathonなどでは10秒間程度の測定に使用するので、きちんとサーバーでの挙動を確認してから使用する必要がありそうです。
//現在の時間情報をtに受け取る unsigned int tickl, tickh; asm volatile ("rdtsc" : "=a"(tickl), "=d"(tickh)); unsigned long long res = ((unsigned long long)tickh << 32) | tickl;
745:名無しのターゲットさん:2013/12/9(月) 18:13:12 id:jetbead
bsr/bsf
- bitで最初にビットが立っているポジションを返す
- 上位ビットから探すか、下位ビットから探すか、が用意されている
//int整数を入力とし、ビットが立っている最上位のポジションを返す int i = 12345, pos = 0; asm volatile ("bsrl %1, %0" : "=r" (pos) : "r" (i));
817:名無しのターゲットさん:2013/12/9(月) 19:51:39 id:jetbead
div/mul
- divは、商と剰余を同時に計算できる
- けど、これだけやってもしょうがないようで、普通は最適化オプションに頼ったほうがよいっぽい
- mulは、乗算時にオーバーフロー/キャリーフローしたかどうかを、フラグを確認することで知ることができる
- けど、これを使わない方法でも確認できるし、これ単体で使うのはあんまりメリットなさそう
892:名無しのターゲットさん:2013/12/9(月) 21:03:12 id:jetbead
fsincos
- sinとcosを同時に取得できる
- けど、実際に試してみるとfsincos命令の方が遅いっぽいし、最適化でも使われないっぽい
964:名無しのターゲットさん:2013/12/9(月) 22:56:40 id:jetbead
- MMX/SSE/SSE2/SSE3で提供されている命令セットを使って効率的に演算できる場合がある
- 複数の値や処理をまとめて処理できる
- インラインアセンブラを使うのは、おおよそこれを使いたい場合(だと思う、たぶん)
- 組み込み関数を提供するヘッダが使えたらそれの方がわかりやすい(mmintrin.hとか)
- 例として、srcとdstの乗算をして隣接2つの加算を行う例を試してみる
- 「movdqa(Move Aligned Double Quadword)」を使用することで、128bit単位でまとめて読み込める
- movdquはアライメントの制限がないver
- 「pmadd(Packed Multiply add)」を使用することで、掛け算したものの隣接同士を加算、のような少し複雑な処理を行える
- http://community.topcoder.com/stat?c=problem_solution&rm=300564&rd=13698&pm=10336&cr=10597114
- 本番で使っちゃった系の人
//movdqaは制限で、確保するときに境界を合わせる(アドレスが16で割り切れる)必要がある short src[6400000] __attribute__((aligned(16))); short dst[6400000] __attribute__((aligned(16))); int dst_int[3200000] __attribute__((aligned(16))); void func_naive(){ short tmp[8]; for(int i=0; i<6400000; i+=8){ tmp[0] = dst[i] * src[i]; tmp[1] = dst[i+1] * src[i+1]; tmp[2] = dst[i+2] * src[i+2]; tmp[3] = dst[i+3] * src[i+3]; tmp[4] = dst[i+4] * src[i+4]; tmp[5] = dst[i+5] * src[i+5]; tmp[6] = dst[i+6] * src[i+6]; tmp[7] = dst[i+7] * src[i+7]; dst_int[i/2] = tmp[0] + tmp[1]; dst_int[i/2+1] = tmp[2] + tmp[3]; dst_int[i/2+2] = tmp[4] + tmp[5]; dst_int[i/2+3] = tmp[6] + tmp[7]; } } void func_asm(){ short *psrc, *pdst; int *pdst_int; for(int i=0; i<6400000; i+=8){ psrc = src + i; pdst = dst + i; pdst_int = dst_int + i/2; asm volatile ( "movdqa 0(%1), %%xmm0;\n" "movdqa 0(%2), %%xmm1;\n" "pmaddwd %%xmm0, %%xmm1;\n" "movdqa %%xmm1, 0(%0);\n" : : "r" (pdst_int), "r" (psrc), "r" (pdst) : ); } } //これぐらいの例だとあまり大きな差にはならないかも・・・ // (マラソンで、とにかく試行回数稼ぎたい場合とか for(int i=0; i<6400000; i++){ src[i] = i % 64; dst[i] = (i+1) % 64; } for(int t=0; t<100; t++){ //func_naive(); func_asm(); }
1000:名無しのターゲットさん:2013/12/9(月) 23:55:34 id:jetbead
参考にしたもの
- TopCoderのページ
- その他
- http://www.sci10.org/on_gcc_asm.html
- http://www.wakayama-u.ac.jp/~chen/gccxmm.htm
- http://www.wdic.org/w/SCI/MMX
- http://www.wdic.org/w/SCI/SSE
- http://www.wdic.org/w/SCI/SSE2
- http://www.wdic.org/w/SCI/SSE3
- http://www.cc.u-tokyo.ac.jp/support/press/news/VOL10/No5/200809tuning.pdf
- http://www.intel.co.jp/content/dam/www/public/ijkk/jp/ja/documents/developer/w_big_mul_j.pdf
- http://www.intel.co.jp/content/www/jp/ja/developer/download.html
- http://www.intel.co.jp/content/dam/www/public/ijkk/jp/ja/documents/developer/ia32.pdf
- アセンブラ画像処理プログラミング -SIMDによる処理の高速化-
- など
1001:名無しのターゲットさん:2013/12/9(月) 23:59:59 id:jetbead
、_________ \: : : : : : : : : : : : : : : : `: : : . 、 /: : : : : : : : : : : : : : : : : : : : : : `ヽ /: : : : : : : : : : : : : : : : : : : : : : : : : : : ヽ、 /: : : : : : : : : : : : : : : : : : : :ヽ : : : : : : : : : : :、 ∠〆: : : : : : ∧: : : :ヘ: : : : : : ヽ: : : : : : : : : : :│ /: : : : : : : | ヾ : : :| \: : : : :ヽ: : : : : : : : : : : | (: : : : : /| ./ ヾ: :ヽ \: : : :.ヾ: : : : : : : : : │ このスレッドは1000を超えました : : : : :/ ∨ ~~ ``ゝ┬ : : : |: : : : : :.| ゝ : l | ̄ ̄| | ̄ ̄| │: : : :.|: : : : : :ヽ 最後まで読んでいただき、ありがとうございました ∠∧: l .! ノ ! ノ | : : : : |`ヽ: : : : ヽ ヽ:| ゝ‐ ´ ゝ−´ /: : : : :/ ): /ヾっ 高速化ガチ勢の方、間違いやコメントなどございましたら、おねがいします || /: : : : :/.ノ: :/ へ, ,. ゚ 丿: : :/:/ソ ヽ: :∧ヽ 、 、__,, /´: : ノ∨´ ヽ´ /ソ ソ: ノ\ _, -'"∠__/ ゙ヽ 、 最初、高速化で無理やり通すのに挑戦しようと思ってましたが、 / |i| |____/ __=ゞ´´丶 ./|. |i| |__/ .__ヾ´ /:::::|ヽ 問題を探すのも書くのも読むのも大変で、さらに熾烈なコンパイラの最適化との戦いでボロボロになりました・・・ /::::. |i| .ヽ / _=゙゙ /:::::::::::| 丶 /::::::::. ヾ. ヽ丿 ._=゙゙ /::::::::::::::::::|.__ヽ アセンブラでガチ高速化入門的なのを期待された方、ごめんなさい・・・ ;( ノ:::::::i´ ̄ ̄`i _=゙ /.::::::::::::::::::::::::| |::::ε| |=゙゙_,-∠-::::::::::::::::::::::::::ヾ |::::ε| ||:::::::::::::::::::::::::::::::::::::::::::::| ヽ---.ゝ--、⊂´ヽ:::::::::::::::::::::::::::::::::, -´ 明日も競技プログラミングアドベントカレンダーは続きます , - ´ `ヽ─--ーゝ-:::,::_:.-- -ー ´´:::| / ,,-.、_ ,ーゞー、__`ゝ´ \::::::::::::::\ たくさん記事を読んで、たくさん問題解いて、レッドコーダー目指しましょう!:) 《´ ソ´ 〆.、 \:::::::::::::\ | | `ゝ `\:::::./ ´、___> ´ .)>、_ ,、ヾつ `──ー ´  ̄`´
アドベントカレンダーのページ
Competitive Programming Advent Calendar Div2013