melancholic afternoon

現時点でも順序非依存に実行して良いことは(maxの結合則から)十分推論可能(中略)そのレベルの賢さを想定する

現行のアルゴリズム記述の何か延長線上にあって、なおかつ、定義と論理的には同値な記述を可能にするプリミティブが欲しい

欲しいものが分かった気がするけど(自分のために)最大値の問題で確認し直してみる.

配列a[N]が与えられたときに
M_a := { i : a[i] >= a[j] for all j }の元を一つ求めよ

を定義(D)とする.

int maxIdx(int a[N], size_t N)
{
    size_t maxi = 0;
    int max = a[0];
    for (size_t i = 1; i < N; i++) {
        if (a[i] > max) {
            maxi = i;
            max = a[i];
        }
    }
    return maxi;
}

を普通の手続き型の答え(P)とする.
二つの間にはギャップがある. (まずM_aが空集合でないこと, 次にPで求められたものが必ずM_aの元であること脳内で納得することで)普通はPのコードを書く. でもPだとM_aのうちの特別な部分集合しかえられない(Q)点に不満があると.
この場合に限っては, やはりシーケンシャルにとってるところが問題なんだと思う. 通常のfor_eachじゃなくて順序を問わないparallel forみたいなので十分じゃないかしら.

unordered_for_each (i : [0, N) ) {
    if (a[i] > max) {
        maxi = i;
        max = a[i];
    }
}

みたいな.
ところで
twitter 2

「殆ど定義の同義語に戻る」のが(超絶賢い)処理系にとっては一番楽だけど、プログラマにとってそれは決して楽ではないと思うのでそれを避けたい

あれ, 私は(D)でかけるのがプログラマにとって楽な気がするけどkinabaさんにとっては逆なのか.

どちらでもいい
寝ぼけ頭で的外れな事書きそうやけどいいや. 最大値を与えるインデックスに関しては殆ど定義の同義語に戻るしかないんじゃないかという気がする. たとえば配列a[N]に対して各iに対してP(i):={a[i] >= a[j] for all j}という命題を与えて, where_is_the_max_element(a) := 「P(0), ..., P(N-1)の中でtrueになることが最初に確定するP(i)のi」というのはどうだろう. 将来P(0), ..., P(N-1)をN個の独立なスレッドに割り当てて一番速く終わったものが答えとすることができるかもしれない. 現状でも上記の「実装」をしてみたとする. 各P(i)を独立に求めるところで重複する多数の比較がでるけれども, 推論の最適化を頑張らせることによってそれらを省略させて, 結果的に素朴なシーケンシャルになめて解をえる方式をコンパイラが編み出せるかもしれない(ほんまか).
もとの記事ではcointossをうまくかけたとしてもiをシーケンシャルになめるということ自体が既に超絶最適化コンパイラに対する足かせになってるんじゃないかと.
あるいは全くの適当だけど

const int* maxIdx(const int& a, const int& b)
{
    return a &gt; b ? &amp;a : a &lt; b ? &amp;b : (&amp;a |?| &amp;b);
}
cost int* maxIdx(const int a[], size_t size)
{
    if (size == 1) {
        return a;
    } else if (size == 2) {
        return maxIdx(a[0], a[1]);
    } else {
        return maxIdx(*maxIdx(a, size / 2)],
                      *maxIdx(&amp;a[size / 2], size - size / 2)]);
    }
}

こんなの?
ところで個人的にはこの問題はphminposuwの化け物みたいなのが登場して瞬殺できるかもと妄想する. ソーティングアルゴリズムも違ったものになるだろうな.

VCのstd::swapがタコな件はVC10で直るらしい. えがった.

↓何が原因か分からない. 簡単なコードだと差は出ないので原因追求が難しそうだ. ざっくりasm出力を見る限りではスタックの使い方やレジスタの使い回しは微妙に4.4.0の方が優れてるように見える. けど実測値はF₃¹⁹³の乗算が4.3.3で3064clkだったのが5043clkと相当遅くなってる. ちなみにVC10だと1700clkぐらい(もちろん同一ソース).

gcc 4.3.3から4.4.0にupdate. しかしペアリングのベンチマークしたら20%も遅くなってしまった. 何故だろう. もとに戻そうかな.

Debug Hack Conferenceにはいかずに『DEBUG HACKS』読んでた. とりあえず一通り読んだ. 以前デバイスドライバ開発で毎日Oops見てたときはヒントになった(2.4系だったので使えないものも多い)だろうものが沢山. この本でも触れてるけどバージョンやディストリビューションによって機能が違ったりすることが多いのでダンプ周りなど一覧になってると嬉しいかな.
バグ?らしき現象の遭遇から, 再現方法の検討, テストプログラム作成, 追求の一連の流れの例が多いのは素晴らしいと思う. ただ全編を通して「手段を選ばない」感じで進めているのに「最適化オプションを変えるな」(p.20)という主張が宙に浮いてる. この主張はいらんだろう. あと細かいことだがインデントの深さがまちまち(4～13?取りすぎ)なのと基本的な参考文献の重複が少々うっとうしい. 編集で統一してほしかった.

変数が多いクリティカルパスではSSE x 16は効くなあ. うーん, 手で書いてみたくなってきた.

えっMySQLどうなるの?は選択枝にないのか. 意外だ.

↓³のソースをビルドしようとするといつまで経っても終わらない. で, 著者に問い合わせたら, "it takes more than one day"というniceな返事が. とりあえず最適化レベルを落として他も微修正して試すことにする.

slashdotメガデモ
ちょっと頂けないコメントの多さに衝撃を受ける. バイナリサイズを気にしたことない人は試しにexeのhello worldで4KB切れるかやってみればいい. もちろんそちらはそちらでおかしな人たちはいるんだけど.

型レベルの懇親会.
前に座った方は同じ学部で, 右の方は同じRIMS出身(ほぼ同時期)だった. 世の中狭い. Ocamlで仕事してるのか凄いなあ.

コメントがスペイン語のソースファイルがやってきた. うーむ, 読めるかな.

今日のmoshのバグ : VCでmoshビルド中にmoshが使うライブラリをmosh自身が作成する途中でmoshが落ちる. VC上じゃなくてコマンドラインで動かすと落ちない. build中しか発生しないのでデバッガを起動してbreak point置いとけない. 死んでからデバッガでおっかけようとしてもスタックトレースめちゃくちゃ. 結局原因は, build中にmoshのstdoutをVCのIDEが自身の出力ウィンドウに自動的にリダイレクトするのを考慮していなかった点(いやこれは気が付かん)と, そのとき上位でwrite()が失敗するのをケアしてなかったのと, そのせいでsetjmpせずにlonjmpするケースにヒットするトリプルコンポだった(後半二つはわたしのせいじゃないぞーと逃げ). 最後のせいでスタックトレース壊して死んでくれてた模様. 標準出力まわりが原因だからprintデバッグしにくいし, なかなか苦労した. というわけで, やはりエラーチェックはきっちりしておきましょうというお話であった.

家のマシンでmoshをコンパイルしようとしたらコンパイラが落ちる. VC Proなら大丈夫なのでExpressのみの問題か. 何が原因なんだろう.

亀レスだけど多様体としての楕円曲線E/kでのリーマン・ロッホの定理(の一部):
「あるP∈Eをとり, L(dP):={P∈Eで高々d位の極を持つ関数のなすkベクトル空間}とするとd > 0のとき dim L(dP) = d. d > 2ならL(dP)の基底を用いてEから射影空間の中への同型写像φを作れる」を認めてみよう.
とするとdim L(2P) = 2. つまりPで2位の極を持つ関数ξが存在する. もう一つは定数関数. dim L(3P) = 3なのでPで3位の極を持つ関数ηも存在する. 順にL(2P) = <1, ξ>, L(3P) = <1, ξ, η>, L(4P) = <1, ξ, η, ξ²>, L(5P) = <1, ξ, η, ξ², ξη>.であることが容易に分かる. ところがL(6P)については6次元なのに基底の候補が1, ξ, η, ξ², ξη, η², ξ³と7個ある. つまりある(a, b, c, d, e, f, g) ≠ 0が存在して a + bξ + cη + dξ² + eξη + fη² + gξ³ = 0でなければならない. gd = 0ならおかしくなるのでgd≠0. 適当に基底を取り替えて(ch(k) ≠2, 3なら)η² = ξ³ + aξ + bという形に持って行ける. φ:E∋t→[1:η(t):ξ(t)]∈P³が中への同型なので抽象的に定義されていたはずのEはいわゆるY² = X³ +aX + bという形となってしまう. というわけで最初からこれを楕円曲線と言ってしまっても問題ないわけだ.

いろいろ検査した挙げ句, よく分からん喉付近の妙な物体は「ほっといたら治るだろう」とのこと. まあリンパ腫とかじゃなくてよかった.

MoshのWindows版が遅いらしい. 手っとり早く移植するために後回しにしてる本質的に遅い部分(gmpやdirect threaded)は別途ゆっくり対策を練るとして, そうじゃなくても全般にもっさりしてるらしい. 悔しいのでちょっといじって一つ目のベンチを2倍ぐらい速くした(他はまだしんない). POD的なクラスTを引数にとる関数はついついconst T&と書いちゃうけど, 値渡しの方が効率がいいんだよな.

struct A {
    int val_;
};
int func(const A& a)
{
    return a.val_;
}
int func2(const A a)
{
    return a.val_;
}

func1:
    movl    4(%esp), %eax ; ワンクッション入る
    movl    (%eax), %eax
    ret
func2:
    movl    4(%esp), %eax
    ret

憂鬱な午後のひととき