ELF loader をまた書いたというはなし
IOCCC 2013 向けのエントリとして何書こうかなーと考えて、あまりネタが無いのと、まぁ一度入賞したし好き勝手なのを書こう、ということで ELF loader を書きました。
http://shinh.skr.jp/dat_dir/elf.c
C 的な obfuscation はあまりしてないわけですが、 1k bytes 以内で ELF loader が書けたのでだいたい満足しました。圧縮されたバージョンはこれ。
https://github.com/shinh/tel_ldr/blob/master/elf-tiny.c
作りとしては maloader の逆で、 Linux だけでなく、 Mac や Cygwin でも Linux バイナリが限定的ですが実行できます。ソースコードはこのへんにあります。
https://github.com/shinh/tel_ldr
IOCCC 的にはポータビリティ無いの微妙だし(ていうか審査員の環境で動いたんだろうか…)、あんま C 的な obfuscation してないしでひどいわけですけど、これ自体はまぁまぁ面白いものではないかと思ってます。
Code Zip
http://www.codechef.com/CDGF2013/
ずっと勝てないなあと思ってたけど、なんかうっかり勝ちました。なんかややこしい書き方してあるけど、実はすごく簡単な問題、ってのばっかりで、ゴルフの問題としてはかなり残念感がある問題セットではありました。
BINGCD
最右の 1 が立ってる bit の位置を探す問題。なんで 1B 負けてるのかわからない。謎です。
eval [*$<]*'p$_&-$_ if$_=2*' eval [*$<]*'p _&=-_ if _=2*'
Perl だと 26B になりますが、精度的に WA になるというクソゲー。
<>;print$_*2&-$_*2,$/for<>
FCTRIZE
brainfuck or whitespace or intercal 限定問題。最初は解埋め込みで BF とか WS とかで適当に解いておいて、マジメに縮めてくる人いたらマジメにやるかなぁとか思ってたけど、なんか一番マジメにやる運命になった。
http://shinh.skr.jp/dat_dir/enc_fctrize3.rb
GCD のループから出る時にゴミが残るようにしておいて、そのゴミをうまいこと使ってる点と、
int i, j;
for (i = 2; i <= 1000; ) {
for (j = 1; j <= i; j++) {
}
i = j; // ココ
}の上記のココみたいな感じで i++ をはぶいてるのが最後の方にやった変更で、これで意外なくらい縮みました。
PRQUIN
いつも通りの変形 Quine
#define q(x)b=#x;x q(v;main(i){for(scanf("%d",&v);v%++i;);v=!printf(i-v?"#define q(x)b=#x;x\nq(%s)":"YES",b);})
TOTAREA
色々書いてあるけど x**2*17/6 を計算するだけの問題。何故か最初の行で指定する入力数以上の入力があるらしく、一行目読み飛ばしではダメ。
printf"%f ",<>**2*17/6for 1..<>
Perl6 でも書いてみたけど 1B 長い。
printf("%f ",get**2*17/6)for^get
Bash でも書いてみたけど 1B 長く、そして何故か WA 喰らうので謎。これが WA じゃなければ、これをゴルフすればもうちょい短くなる気がするんだけどな。
dc -e'6k?[?d*17*6/pr1-d0<L]dsLx'
ちなみに入出力が常識的なものだったら 9B くらい縮んで楽勝だったんですがね…
sed '1!a6kd*17*6/p'|dc
glibc lock elision の感想もうひとつ
glibc の lock elision パッチへの感想ですけど、 RTM をウラで使われると、典型的なデッドロックであるところの AB-BA 的な deadlock 、つまりロックの順番が逆転してるコードパスがあると deadlock 、ってケースの発見率が減ることがあるんじゃないかな、とか思いました。
つまり、 RTM に頼った動作をしている時は AB-BA をやっててもデッドロックせず、 conflict がたまたま何度も発生して普通の mutex に fallback した時にだけ再現する deadlock になる、と。
試しに書いてみた以下のコード
https://github.com/shinh/test/blob/master/deadlock.cc
だと、適当に何度か実行してみた感じでは、 lock elision を有効にしている時は 10 回中 2 回くらいしか deadlock せず、無効にすれば 10 回中 8 回ほど deadlock しました。
うーんこれはちょっとめんどくさそうですね…
TSX の話
x86/64 最適化勉強会6 で TSX の RTM について最近調べたりしたことを発表してきました。
スライド: http://shinh.skr.jp/slide/tsx/000.html
なんか速くしたいなーと思ってたんですが、あまり何を速くしようっていうアイデアが無かったので、調べてわかったことをだらだら話しただけになってしまいました。
というのは既存のよく動いてるパフォーマンスが重要なものは適切に粒度の細かいロックを取ってるだろうし、パフォーマンスが重要でないものは、別にこれ使うようにしても嬉しくないだろうし…という
あと TM が有効になるようなある程度大規模なもので、好き勝手にいじりやすいコードが手元にあんまり無いということもあり。
しかし速度を大きく損なわないどころか、広めに transaction 取ってる場合速くなる可能性を持ちつつ、プログラムがラクになるってのは結構嬉しいのではないかなーと思っているので、 HTM には割と期待していたりします。
書き込み時に reader lock を取るテクニック
昔、データを書く時に reader lock を取って、読み時に writer lock を取るワザがある、っていうのを聞いたのを覚えていて、詳細を忘れてたんですが、最近思い出す機会があったので書いておきます。
thread local storage を使って各スレッドにあるキャッシュなんかだと、当然読み書きする時にロックはいらないわけです。ただ、例えばダッシュボードの URL にアクセスされた時にキャッシュの使ってるメモリの総量が知りたいなど、 worker たちを管理しているスレッドが、各スレッドのキャッシュの状態全てにアクセスしたい、なんてことがあったりします。
こういう時に、普通に lock を取ってしまうと、 thread local storage を使って lock しなくて良いようにしてあるメリットが失われてしまう、と、そういう時に使うワザっぽいです。
具体的には、各 worker がそのキャッシュを読み書きする時は reader lock を取ります。 reader lock だから、各 worker は同時にガンガン読み書きしますが、 thread local storage で分離してあるので問題無い。
で、 worker を管理しているスレッドが、全スレッドの状態を取得する時に、読み込み目的にも関わらず、 writer lock を取ります。すると、うまいことに、全ての worker が働きやめるのを待ってから状態を取る感じになってくれます。
ついでに、この rwlock が glibc のデフォルトのままだと reader が忙しいとダッシュボードがなかなか表示されない、みたいなことがあると思われるので、 PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP を使っておくと良いやもです。
\BV interpreter in sed (ICFPC 2013)
去年と似たようなネタでこっちの方がはるかにラクでしたけど、まぁまともに参加できる日程でなかったので…
使いかたはプログラムと入力を空白くぎりで入れる感じ。
$ echo '(lambda (x_78920) (fold 0 (not (xor (not (shr1 (not (plus (if0 (plus (not (shr16 (xor (not (or x_78920 (shr4 x_78920))) 0))) x_78920) x_78920 0) x_78920)))) 0)) (lambda (x_78921 x_78922) (or (shr4 x_78921) x_78922)))) 0xFEDCBA9876543210' | sed -f bv.sed 0x91A2B3C4D5E6F7
コード。 GNU sed と Mac の sed で動作確認
h s/.* // s/0x// y/abcdef/ABCDEF/ s/^/0000000000000000/ s/.*\(.\{16\}\)$/\1@/ :hex2bin s/$/;10;32;54;76;98;BA;DC;FE/ s/\(.\)@\([^;]*\).*;\1\(.\).*/\3@1\2/ s/@\([^;]*\);.*/@0\1/ s/$/;20;64;A8;EC/ s/\(.\)@\([^;]*\).*;\1\(.\).*/\3@1\2/ s/@\([^;]*\);.*/@0\1/ s/$/;40;C8/ s/\(.\)@\([^;]*\).*;\1\(.\).*/\3@1\2/ s/@\([^;]*\);.*/@0\1/ s/8@/;@1/ s/0@/@0/ s/;// /^@/!b hex2bin s/^@// x s/\(.*\) .*/\1/ s/ 0/ 0000000000000000000000000000000000000000000000000000000000000000/g s/ 1/ 0000000000000000000000000000000000000000000000000000000000000001/g G s/^(lambda (\([a-zA-Z0-9_]*\)) \(.*\))/\1@\2/ :subst s/^\(.*\)@\(.* \)\1\(.*\n\)\(.*\)/\1@\2\4\3\4/ /^\(.*\)@.* \1/ b subst s/.*@// s/\n.*// h x s/.*// x :main_loop # i\ # === main loop pattern space === # p # x # i\ # === main loop hold space === # p # x /;fold1 /{ s/;fold1 // s/ .*// b ret } /;fold1/{ s/\(;fold1 [01]* \)\([01]*\)\( .*\)/\1@\3 #\2/ H x s/ #.*// x :acc_subst_loop s/!// s/\(@ [a-zA-Z0-9_]* \)\([a-zA-Z0-9_]*\)\( .*\) \2\([^a-zA-Z0-9_].* #\(.*\)\)/\1\2\3 \5\4!/ /!/ b acc_subst_loop s/ #.*// :iter_subst_loop s/!// s/\([01]\{8\}\) @ \([a-zA-Z0-9_]*\)\( .*\) \2\([^a-zA-Z0-9_].*\)/\1 @ \2\3 00000000000000000000000000000000000000000000000000000000\1\4!/ /!/ b iter_subst_loop s/[^(]*(/(/ b main_loop } s/(if0 0\{64\} \([01]\{64\}\) [01]\{64\})/\1/ s/(if0 0*1[01]* [01]\{64\} \([01]\{64\}\))/\1/ s/(not \([01]*\))\(.*\)/@\2;not \1/ /;not/{ H s/.*;not // y/01/10/ b ret } s/(shl1 \([01]*\))\(.*\)/@\2;shl1 \1/ /;shl1/{ H s/.*;shl1 // s/^.// s/$/0/ b ret } s/(shr1 \([01]*\))\(.*\)/@\2;shr1 \1/ /;shr1/{ H s/.*;shr1 // s/.$// s/^/0/ b ret } s/(shr4 \([01]*\))\(.*\)/@\2;shr4 \1/ /;shr4/{ H s/.*;shr4 // s/....$// s/^/0000/ b ret } s/(shr16 \([01]*\))\(.*\)/@\2;shr16 \1/ /;shr16/{ H s/.*;shr16 // s/................$// s/^/0000000000000000/ b ret } s/(and \([01]*\) \([01]*\))\(.*\)/@\3;and \1 \2/ /;and/{ H s/.*;and // s/$/;/ :and_loop s/1\( .*\)1;/\1;1/ s/0\( .*\).;/\1;0/ s/.\( .*\)0;/\1;0/ /^ ;/ ! b and_loop s/ ;// b ret } s/(or \([01]*\) \([01]*\))\(.*\)/@\3;or \1 \2/ /;or/{ H s/.*;or // s/$/;/ :or_loop s/0\( .*\)0;/\1;0/ s/1\( .*\).;/\1;1/ s/.\( .*\)1;/\1;1/ /^ ;/ ! b or_loop s/ ;// b ret } s/(xor \([01]*\) \([01]*\))\(.*\)/@\3;xor \1 \2/ /;xor/{ H s/.*;xor // s/$/;/ :xor_loop s/\([01]\)\( .*\)\1;/\2;0/ s/1\( .*\)0;/\1;1/ s/0\( .*\)1;/\1;1/ /^ ;/ ! b xor_loop s/ ;// b ret } s/(plus \([01]*\) \([01]*\))\(.*\)/@\3;plus \1 \2/ /;plus/{ H s/.*;plus // s/$/;/ :plus_loop s/0\( .*\)0;/\1;0/ s/1\( .*\)0;/\1;1/ s/0\( .*\)1;/\1;1/ s/1\( .*\)1;/\1:0/ s/0\( .*\)0:/\1;1/ s/1\( .*\)0:/\1:0/ s/0\( .*\)1:/\1:0/ s/1\( .*\)1:/\1:1/ /^ [;:]/ ! b plus_loop s/ .// b ret } s/(fold \([01]*\) \([01]*\) (lambda (\([a-zA-Z0-9_]*\) \([a-zA-Z0-9_]*\)) \(.*\)/@\5;fold \1 \2 \3 \4 !/ /;fold/{ :paren_match_loop s/@\([^()]*(\)\(.*\)!\(.*\)/@\2!!\3\1/ s/@\([^()]*)\)\(.*\)!\(.*\)/@\2\3\1/ /!!/ b paren_match_loop s/@))/@/ s/!// H s/.*;fold/;fold1/ b main_loop } /(/{ s/.*/Unknown operation/ q } x /;fold1/{ s/\(;fold1 [01]*\)[01]\{8\}/\1/ s/$/;/ x b ret } x s/$/@/ :bin2hex s/0000@/@0/ s/0001@/@1/ s/0010@/@2/ s/0011@/@3/ s/0100@/@4/ s/0101@/@5/ s/0110@/@6/ s/0111@/@7/ s/1000@/@8/ s/1001@/@9/ s/1010@/@A/ s/1011@/@B/ s/1100@/@C/ s/1101@/@D/ s/1110@/@E/ s/1111@/@F/ /^@/! b bin2hex s/^@0*/0x/ s/x$/x0/ q :ret G s/\(.*\)\n\n\(.*\n\)*\(.*\)@\(.*\);.*$/\3\1\4/ x y/\n/!/ s/![^!]*$// y/!/\n/ x s/\n// b main_loop
成績自体は 3 時間くらいで作ったやつで遊んで
"contestScore": 281,
"lightningScore": 198,
"trainingScore": 1,
"mismatches": 31,
"numRequests": 753,
"cpuTotalTime": 737.843
