No Such Blog or Diary

やっとこ冥界組でHardクリアでけた．この調子でLunaticも行きたいところだけど...　そのまえに霊夢単体Hardクリアせねば．

最近 screen は良いよとの話を何度か振られたので，試しに使ってみることにした．でもまあ，使い方も良くわからんのでとりあえず使い方の乗ってるところをリンクしてみる．

http://www.atmarkit.co.jp/flinux/rensai/linuxtips/692usescreen.html

http://www.ayu.ics.keio.ac.jp/members/mukai/tips/screen.html

結構高機能のようで，ターミナルを切り替えられたり前の状態をレジュームできたりするらしい．とりあえず，ログアウトしてもプロセスを走らせっぱなしにできるのはありがたい．これからちょっと設定の仕方を学んでみよう．

グリチャレのプログラムをさらに速くしようと，徹夜で研究室のドクターと一緒にプログラムを改良してみた．

ビット操作でちまちまやっていたのを一部バイト操作に置き換え高速化していたのだが，とりあえずそれを全体的にバイト操作にすることで倍以上のスピードアップを達成した．これに関しては誰もが思いつく単純な改良であり，これだけではつまらないと

少々壊れ気味の我々は続いてif 文を殲滅するという奇策に走った．よく知られていることだが，if 文とかでちまちまジャンプしまくるプログラムは遅くなる場合が多く，無駄な if を消すことは速度向上の上でとても好ましい（分岐したときにパイプラインで処理されてたものを破棄しなければならないし）．

というわけで我々も無駄な if を探してみたのだが，既にかなり最適化したつもりのコードなのでそんな無駄な if はもう既にない．でもまあ，必要そうに見える if はまだごろごろいるわけで，そいつをどうにかして殺したい衝動に駆られるのは自然な流れである．そして，我々はいくつかの必要そうな if を愉快な方法で抹殺することに成功した．

抹殺例の一つは以下のような感じである．この次の if で分岐する部分が，

     if(cnt < rem){
       *p = (*p << cnt) | (((1<<cnt) - 1) * bit);
       rem -= cnt;
    } else {
     *p++ = (*p << rem) | (((1<<rem) - 1) * bit);
     cnt -= rem;
     rem = 8-cnt & 0x7;
 }

次のようなわけのわからないコードに置き換わった．

    const int min = cnt - ( ( - 1 + ( ( unsigned ) ( cnt - rem ) >> 31 ) ) & ( cnt - rem ) );
    rem -= min;
    cnt -= min;
    const int isRem0 = ( -1 + ( ( unsigned ) ( -rem + 1 ) >> 31 ) ) & ( -rem + 1 );    
    *p = ( *p << min ) | ( ( ( 1 << min ) - 1 ) * bit ); p += isRem0;
    rem += isRem0 * ( 8 - ( cnt % 8 ) );

これにより if 文が抹殺され，実際に実行時間も少しばかり（このルーチンのクロック数で半分くらい）速くなった．

ここでの肝は， signed の x に対して， max(x, 0) = (-1 + ((unsigned)x>>31)) & x のようにif を用いずに max を表現できることだったりする．上の例ではこれを改良して， x>0 なら 1 を，そうでないなら 0 を返す演算を記述している．

このように，あほな努力でちょっとでも速くてとても読みにくいコードが出来上がるのはとても面白い．

雪が降ったて多少積もったことはなんとなくうれしく感じるのだけど，研究室で徹夜してるときに降らなくてもいいじゃないか．自転車は濡れるわ，手は冷たいわ，立ちこぎで家につくころには腰が痛いわ...　まあ，これらは自転車に乗らなければ良かったのだけど．

でも雪の上を走るのはすべるので面白い．

とりあえず予選を通過できたグリチャレであるが，予選通過時のプログラムは少々お馬鹿で一問解くたびにプロセスを立ち上げ直さねばならなかった．そのせいで，問題を解くのに用いた時間よりプロセス立ち上げとコネクションの確立の時間のほうが長いというあほな状況に．そこで，一度プロセスを立ち上げてコネクションを確立したら，それを使いまわせるようにプログラムを書き直してみた．

結果として今日半日分の時間を（主にデバッグに）かけ，結果としてちゃんと動くプログラムが出来上がった．ほとんどのバグは同期に関連していて，スレッド間のロックが一番面倒で何度かデッドロック（というかロックのかけっぱなし）をやってしまった．こんなことをやっていると誰でもが簡単に正しい並列プログラムを作れる環境はやはり必需品なのだなぁと改めて感じたりする．研究しなきゃ...

前回えーりんをぶっちぎったうどんげが勝つかなぁと思っていたら，なにやらゆかりんが２００票以上の差をつけて勝ったみたい．最近予想が外れまくり...　でもまあ，今日は咲夜さんの勝ちでしょう．