記憶と夢とストリートビュー

技術記事ではない。


知人と、互いが昔住んでいた町をグーグルストリートビューで見ながら紹介するという遊びをした。ここを曲がると昔よく遊んだ公園があって、ここを曲がると帰り道で寄っていたお店が……。なくなっていた店もあったし、改装で様変わりした建物もあったが、懐かしさが消えるわけでもない。ストリートビューの画像の切れ目にできる僅かな歪みを指摘して茶化しながら当時の生活を思い出し、検索ボックスに住所を入力してエンターを押せば瞬時に県を跨げる時代に少し感動を覚えてもいた。

あの町に住んでいた頃、携帯端末はブザーか数字を送るので精一杯だった。そののち、私の成長と共に端末は形を変え、複雑な音声信号を送れるようになり、画像が、動画が、webページが、届くようになっていった。そんな頃を思い出しながら道の途中で立ち止まり、カーソルを動かして周囲を見回していると、嫌でもその変貌ぶりを意識させられる。

変わるのは技術だけではない。多くの建物がなくなって、また新しくなっている。多くの人が出て行って、別の人が住みついただろう。データも同じだ。当時見ていたウェブサイトの多くが消えた。当時は存在しなかったデータが信じられないほど拡充している横で、以前私を楽しませてくれたデータが知らないうちに流れ去っている。きっかけがあれば記憶は呼び覚ませるもので、特に印象深くもなかったはずの出来事が断片的に脳裏に浮かび上がっては消えた。

その夜、風呂に入りながらその日あったことを反芻していると、自分が昔住んでいた町をまさに訪れたように感じていることに気付いた。自分の足で歩き、見、時には触れ、その町の空気を嗅いだかのような記憶に編集されている。いくらよく歩いた道で周囲の3次元的なモデルが頭の中にあるといっても、それは単純すぎるだろうと自分で自分が可笑しかった。ストリートビューの平面的なテクスチャが記憶に貼り付けられて、本物のような密度の記憶を作っている。しばらくはあの町を訪れなくても、昨日行ってきたかのように話ができるぞ、と一人で笑っていた(実際にはストリートビューは昨年に撮影されているのだが)。

翌日のことだ。何か非常にリアルな夢を見たのでその内容を思い返そうとしてみると、非常に具体的な町の様子を見ているらしい。存在しない町を訪れる夢は何度も見たことがあるが、景色の破綻のなさから、直感して訪れたことのある町だと結論づけた。しかし思い出そうとしても町の名前が出てこない。いくつかのシーンをちぎれ飛んでいく夢の欠片から拾い上げて、ようやく気付いた。それは昨日ストリートビュー越しに見た知人の故郷だった。

それに気付いてからは意識的にその場所が思い出されていく。駅からの道筋、公園の横の坂道、頭上にかかる高圧電線、全てが異様なリアリティを持っている。自分の足で訪れたかのようだ。もちろんその町を訪れたことはない。しかし驚いたことに、その場を歩いたかのような記憶がある。ストリートビューでは離散的にしか取れなかったはずの自分の位置が補間され、途中の位置からの景色が挿入されている。当然なかったはずの触感や、ガードレールの鉄の匂い、側溝の水音、雑木林の草いきれが脳裏に浮かぶ。

一番驚かされたことは、グーグルストリートビューからの景色を意識的に思い出せることだった。そこと別の領域に、リファインされた景色が入っている。ストリートビューにはあった景色の歪みが含まれる画像と含まれない景色を思い出せることが決定的だった。どのように格納されているか知らないが、ストリートビュー由来の景色の特徴を抽出して非可逆に圧縮し、想起の過程をフックして質感を追加しているわけではない。ストリートビューの画像からその土地のモデルが形成されて、他の町と同じような領域に格納されている。歩きまわったのと同じように。一晩寝ただけで。

知人の故郷は普通の町だった。よくある大都会でもなく田舎でもない普通の町。基本的な構成要素は私の見たことのあるものがほとんどだった。珍しい南国の樹が植わっているわけでもなく、特殊な文化由来の異国情緒あふれる町並みでもない、普通の日本の町だった。だからこそ私の脳はそこに“ありそうな質感”を付与できたのだろう。私が寝ている間に、記憶が読み込まれ、編集され、カテゴリに分けられて仕舞われていた。自分の身体を完全に制御できていないことを思い知らされる。と同時に、脳が「私」に断りなく行っていた蛮行を一つ暴いたような気がして少し溜飲が下がった。

その日普段の通り道を歩いていると、少し薄ら寒くなったことを白状せねばなるまい。私は普段歩いている道を五感全てで感じていると信じているが、少なくとも私の長期記憶にはそれはさほど重要ではないようだ。私はグーグルストリートビューから得られる程度の情報からでも、この道について持っている長期記憶と同程度の密度の情報を構築できる。もちろんそれには生の感触が大量に必要であって、それはこれまでの私の人生で歩いた道から得られたものなのだが、しかし既に「よくある町」のデータセットは揃ってしまった。この道の記憶は、どの程度再構築されたもので、どの程度が生の記憶なのだろう? 区別できるものだとは思っていないが、それでも気味の悪さは完全には拭えない。自分の記憶を完全には制御できていないという恐怖、とまではいかないものの、違和感、引っ掛かりのようなものは、喉に刺さった小骨のように、足の裏に付いた米粒のように、脳裏から離れることはなかった。

特殊な記憶能力でもない限り、自分の人生で起こったことを全て覚えておくことはできない。記憶は消え、また編集される。一瞬の間は自分がしていることを覚えていられるが、しばらく経つと短期間の記憶は消化され、非常に短くまとまってどこか奥に消えていく。私は二人いるのだ。短期的に自分のしていることを完全に覚えている自分と、より長いスケールで大雑把にしか捉えられていない自分。思い出そうとしても細かいことは正確には思い出せない。思い出せたとしても、編集された結果かも知れない。区別はつかないだろう。短期的な自分が現れては消えていく。それに従って、長期的なスケールの自分がその遺体を拾い上げて解剖し、少しばかりの情報を取り出して、取って代わる。「私」にとっての自分は、短期的なこの瞬間の自分が思い出して自己同一性の拠り所にできる自分は、長期的なスケールの方の自分でしかあり得ない。

当たり前のことなのだが、それを直視すると恐ろしい。自己同一性のほとんど唯一の拠り所のはずの記憶が、「私」にはわからない形で、捻じ曲げられ、消えていっているのだから。

メモリ上での配置に関して、多次元配列と構造体の配列の比較

最近少しアライメントのことを考えているが、古めの書籍だと多次元配列のメモリ配置の説明が必ずと言っていいほどされていて、メモリアクセスが律速になる場合(殆どのケースだ)には次元の順序に十分注意せよと書かれている。

キャッシュ効率のことなどを考えるとこれは非常に重要だ。メモリ上で連続した値に順にアクセスしていく場合、飛び飛びにアクセスするよりもキャッシュが効いて速くなることが多い。(例えば、Fortran Tip集: 多次元配列のアクセス順序に注意する

簡単に言うと、以下のようなデータがあって、

{ {x1, y1, z1}, {x2, y2, z2}, ... {xN, yN, zN} }

今は全てのデータについてZの値だけを見ていきたいとする。 もしこれがメモリ上で以下のように並んでいたなら、

|x1|y1|z1|x2|y2|z2|x3|y3|z3|...

z1とz2の間には(今は)必要のないデータが挟まっていて少し距離があるので、単純に近い領域のものを一緒に持ってくるキャッシュ戦略では効率が悪くなる。

以下のように並んでいたなら、

|x1|x2|x3|...|xN|y1|y2|...|yN|z1|z2|...|zN|

Zの値を取得する場合は必要な値がメモリ上で近くにあり、キャッシュ効率が上がる結果処理速度が高まるだろう。 そういうことをちゃんと考えた上で、多次元配列の宣言は上手くやれというのがよくあるTipsだ。 私はそれ自体に異を唱える気は全くこれっぽっちもないのだが、多次元配列のメモリ上での配置でどっちの次元が先に置かれるとかを覚えるのは苦痛ではないかと思う。

普通に構造体を作ったらどうなるだろう。

struct vec{float x, y, z;};
std::vector<vec> vs;

vsの中身がどうなっているか、迷うだろうか。vectorは要素を一つずつ配置していくだろうから、一つのvecの後に別のvecが続くだろう。どういう配置になるかは考えるまでもない(パディングが予測できないではないか、と思ったあなたは鋭い。そこまで知っているなら今回の記事の対象読者ではない。どんな状況でもイメージが浮かぶだろうから好きにやっていただきたい。一応言及しておくが、alignas__packedなどを使って制御する手があることも知っておられるだろう)。 逆向きの配置を使いたかったらどうするか。

std::vector<float> x;
std::vector<float> y;
std::vector<float> z;

これでも似た感じになるが、xNの次にy1が来ることは保証されない、というかほぼないだろう。一応

std::size_t N;
std::vector<float> x_y_z(3*N);

のようにしてオフセットを使えば完全にxNの次がyNのようにできるが、個数が変わったりすることを考えると悪夢だし(xNの次に追加の要素を入れる場合、後続のyとzを全てずらさなければならない)、オフセットを制御するメンバでも噛まさない限りバグを仕込む可能性は高まるだろう。Zの値だけを必要とする場合、別にXとYも同時に見ないといけないわけではないので、単に配列を3つ持っていればよいと思う。

もちろん、xi, yi, ziを同時に見る必要が生じる場合、それぞれの場所が離れていればあまりうれしくないだろうから、std::vector<vec>の形になっていた方が幸せだろう。要するにする計算に応じて必要になる可能性が高いものを近くに置くべきなのだ。

何にせよ、どちらを優先するにしても、配置に気を配れる方がよい。そして、「できれば〜したほうが良い」をほぼ常に行わせる唯一の方策は、それを簡単にすることだ。多次元配列でどの次元が先に来るかを学んで(そもそもそういうことが起きることを知って)、それを常に思い出すよりは、配列には常に要素型が順に並べられるとだけ思って構造体を並べるか配列を並べるか考えた方が、イメージが楽だろう。

というわけで、最終的に構造体を使うことに決めるかは置いておいて、多次元配列ではなく構造体を使うことが最初に選択肢として挙がっていた方がその後も捗るのではないかと思っている。

注:関連した話なので飛ばし読みして混同する人が出るかも知れないが、AoS、SoAで速度を考えた時常に構造体の配列がよいと言っているわけではない(ちゃんと読んだ人はそんな風に解釈しないだろうが)。それはメモリアクセスのパターンとアーキテクチャに依存する話なのでそんなことが言えるわけはない。今はイメージしやすいかどうかの話をしている。多次元配列のメモリ配置を覚えるのに比べれば、構造体を定義した場合のそれをイメージする方が簡単だ、だから速度的に最終的に使わないことに決めるとしても、構造体を使うことを選択肢に入れた方がよいという話だ。

zip_iteratorとstd::iter_swap

少し頑張って解決しようとした問題が実は解決できないことに気づいてしまったお話

TL;DR: std::iter_swapをフック可能にしてほしい。

背景

配列が二つあったとして、その片方をキーとして使って、両方の配列を同時にsortしたいと言う気持ちがある。

v1 = {4, 2, 5, 3, 1};
v2 = {1, 2, 3, 4, 5};

sort_by_key(v1.begin(), v1.end(), v2.begin());
// v2 == {5, 2, 4, 1, 3}

これは、普通はstd::pair<int, int>のようなものを作ってstd::sortと適当なコンパレータを組み合わせて行う。

std::vector<std::pair<int, int>> v =
    {{4,1}, {2,2}, {5,3}, {3,4}, {1,5}};
std::sort(std::begin(v), std::end(v),
    [](const auto& lhs, const auto& rhs) -> bool {
        return lhs.first < rhs.first;
    });

だがpairでなくて配列を二つ持っていることもあろう。どうするか。

std::vector<int> v1 = {4, 2, 5, 3, 1};
std::vector<int> v2 = {1, 2, 3, 4, 5};

例えばtransformする手はある。

std::vector<std::pair<int, int>> v(v1.size());
std::transform(std::begin(v1), std::end(v1), std::begin(v2),
    std::begin(v), [](const int& l, const int& r) {
        return std::make_pair(l, r);
    });
std::sort(std::begin(v), std::end(v),
    [](const auto& lhs, const auto& rhs) -> bool {
        return lhs.first < rhs.first;
    });
std::transform(std::begin(v), std::end(v), std::begin(v1),
    [](const auto& x) -> int {return x.first;});
std::transform(std::begin(v), std::end(v), std::begin(v2),
    [](const auto& x) -> int {return x.second;});

長い。それにコピーが入ってしまう。あまり嬉しくはない。

もちろん自分でsortを実装すれば回避できるのだが、あまりやりたいことではない。 せっかく質のいい実装があるならそれを使えばいいのだ。

と言うわけで、複数のイテレータを一つにまとめるzip_iteratorを作ることにした。片方を並べ替えるときにもう片方がついてくるようにすればいい。 これをする上で必要なのは、zip_iteratorから取り出した参照を何らかの形で書き込み可能なようにすることである。これに関しては、std::tieが返すオブジェクトと同じものを用意すればいいだろう。

zip_iteratorの実装

zip_iteratorは複数のイテレータをまとめたものなので、std::tuple<Iterator...>をラップしてイテレータのように振る舞わせれば良い。

イテレータとして振る舞わせるためには、基本的にはインクリメント・デクリメントとoperator*operator->による値の取り出しがあれば良い。

インクリメントは順に全部やっていけばいいので、例えばシンプルに再帰で実装するなら以下のようになる。

template<std::size_t N, typename ... Iterators>
struct increment_impl
{
    static void invoke(std::tuple<Iterators...>& iters)
    {
        ++(std::get<N-1>(iters));
        return increment_impl<N-1, Iterators...>::invoke(iters);
    }
};

template<typename ... Iterators>
struct increment_impl<0, Iterators...>
{
    static void invoke(std::tuple<Iterators...>& iters) {return;}
};

template<typename ... Iterators>
zip_iterator<Iterators...>& zip_iterator<Iterators...>::operator++()
{
    increment_impl<sizeof...(Iterators), Iterators...
        >::invoke(this->iters_);
    return *this;
}

operator*は少し面倒だ。 これはIterator::referenceを返すので、zip_iteratorの気持ち的にはstd::tuple<Iterator::reference...>を作って返したい。

どうするか。困った時は最終形から始めて、必要なものを明らかにしよう。 std::tuple<Iterators...>からstd::tuple<Iterators::reference ...>になればいいので、最終的には以下のような関数があれば良いことになる。

template<typename ... Iterator>
std::tuple<typename std::iterator_traits<Iterator>::reference ...>
get_reference(const std::tuple<Iterator>& iters)
{
    return std::forward_as_tuple(
        *(std::get<0>(iters)), *(std::get<1>(iters)), ...
        *(std::get<sizeof...(Iterator)-1>(iters))
    );
}

当然ながらこれはそのままでは動かない。問題は、template parameterを0, 1, ..., sizeof...(Iterator)のように展開して渡すところにあるのだが、標準ライブラリにちょうどこのための機能がある。少し前の記事でも出てきたstd::index_sequenceだ。

template<typename ... Iterator, std::size_t ... Idx>
std::tuple<typename std::iterator_traits<Iterator>::reference ...>
get_reference(const std::tuple<Iterator>& iters,
    std::index_sequence<Idx...>)
{
    return std::forward_as_tuple(*(std::get<Idx>(iters)) ...);
}

index_sequenceは、この型の値そのものは特に使い道がないが、型そのものに出てくる値が重要な珍しいタイプのクラスだ。 variadic templateならコンパイル時に展開することができるので、必要なものをまとめてindex_sequenceとして渡してやれれば、上記でしているように「コンパイル時にその場で全部展開して渡す」というような操作が可能になる。

で、これを作るためのヘルパークラスがある。

make_index_sequence - cpprefjp C++日本語リファレンス

また、pointerを返す場合でも全く同じ操作が可能だ。むしろポインタのシンタックスが値のそれと異なるためにreferenceの場合よりも簡単と言っていい。 というわけでこれらは解決した。

問題点

さて、ちょっとしたテストを書いてzip_iteratorが思った通りに動くこと、関数の戻り値などが思った通りの型になっていること、zip_iteratorを通して書き込みができることなどを確かめたのち、意気揚々とstd::sortzip_iteratorを渡した時だった。

動かない。

何が問題になっているかと言うと、案の定zip_iterator::operator*()だ。定義を見て欲しい。

template<typename ... Iterator>
class zip_iterator
{
    std::tuple<typename std::iterator_traits<Iterator>::reference...>
    operator*();
};

そう、これはIterator::referenceが入ったstd::tupleをその場で作って返すのである。 その場で作って返す。関数から返った瞬間はできたてほやほやでまだどんな値にも束縛されていない。つまりこれはrvalueだ。

ところで<algorithm>が提供するシーケンスを変更する操作の多くは、swap(*a, *b)のようなことをする。 ここでstd::swapを見ていただきたい。

template<typename T>
void std::swap(T& lhs, T& rhs);

これは左辺値を取るのである。当然だ。入れ替えるのだから、代入もするだろう。 だが、zip_iterator a, bを使ってswap(*a, *b)すると、引数は両方右辺値になってしまう!

というわけで無理になってしまったわけだ。

ご存知の通りswapはフック可能だ。 Argument Dependent Lookupなる機能があり、std::swapはユーザー定義型に対してはより効率的な実装が与えられる可能性を考慮して実装されているので、標準ライブラリ内部で使われる時は大抵以下のようになっている。

using std::swap;
swap(a, b);

こうすると、ADLによってabが所属する名前空間にあるswap関数がまず検索され、なかった場合にusingされているstd::swapが適用される。abが所属する名前空間により効率的なswap実装が提供されていれば、そちらが適用されるわけだ。

今回の問題は、返すものがstd::tupleであるということだ。ユーザー定義名前空間にあるものではない。なのでこのような解決策を取ることはできない。 もちろんユーザー定義名前空間std::tupleの薄いラッパーを用意すれば解決可能ではあるのだが、zip_iteratorが返すものが全て独自tuple型になってしまうことを考えるとあまり気持ちのいいものではない。

より細かいことをいうと、実際に<algorithm>で使われているものの多くはstd::iter_swapだ。 これはそれぞれのイテレータが指す先にあるものをswapするというものなので、これをフックできれば一番丸く収まったのだが(zip_iteratorはユーザー定義クラスだ)、何故か全ての関数がexplicitにstd::iter_swapを呼んでいた。これではADLの力は発揮できない。

operator*std::tuple<Iterator::reference...>を返すzip_iteratorstd::sortと共に使おうとするなら、 非常に薄いstd::tupleのラッパーを用意してADLがswapを解決したのち最適化パスのどこかでその薄いラッパーが消え失せることを期待する(これはまともなコンパイラを使っているなら十分抱いていい期待だと思う)しかない。一応std名前空間の禁じられた扉を開くことでも実行可能だが、そういうのは実行可能とは言わない。

おとなしくペアの配列に変換するか、thrustBoost.Computeにあるsort_by_keyを呼ぶのがよいだろう。

satysfi.vimを作った

というわけで中身を読もうとやっていっていたわけだが、SATySFiにはVim向けのシンタックスハイライターがない。当たり前だ。新興の言語なのだから。だが読むに当たってシンタックスハイライトがされないというのは非常にしんどい。なので最低限のハイライトがされるようなスクリプトを書くことにした。 気持ちとしては、SATySFiを使えるようになりたいがシンタックスハイライトがないと読みにくい、しかしSATySFiについて詳しくないのでどこをハイライトしたらいいかわからない、というデッドロックを破るための、ブートストラッピングの最初の一手というところである。

まだとても完成と言える状態ではないが、最低限度の質素なハイライトはされるので、自分でやるのが面倒だという方は使ってみて欲しい。そしてあなたがハイライトに物申したいときは遠慮なくissueなりPRを送っていただきたい。

github.com

これが突貫工事であることを除いても、私はまだvimシンタックスファイルにもOCamlにもSATySFiの構文にも詳しくないので、ハイライトされるべき箇所がされていない可能性は高いし、それを見つけられる可能性も高い。

まあ、vimの構文ファイルもSATySFiも知らない人間が1時間で作ったということに思いを馳せれば、たいていのことは許していただけると思う。


ところで私は今までVim用のシンタックスファイルを書いたことがない。作り方も導入の仕方も知らない。今まで自作言語でも作っていれば経験があっただろうが、仕方のないことだ。調べなければならない。

vimには素晴らしいドキュメントがある。しかも日本語だ。

syntax - Vim日本語ドキュメント

あるいは、こちらでもよい。

Creating your own syntax files | Vim Tips Wiki | FANDOM powered by Wikia

まず、vimの普段のシンタックスハイライトは、c.vimのようなファイルがあることがわかる。単純なコードならこれを見ることで色々とわかるかもしれないが、とても読めるような代物ではない。私と同様の環境なら、/usr/share/vim/vim??/syntax/*.vimのような場所にシンタックスファイルが死ぬほど転がっているが、これを材料に独学するのは非常に難しい。

素直にドキュメントを読み進めることにしよう。ドキュメントの構文ハイライトファイルのセクションを見れば、ある程度のことがわかる。

しかし、書き始める前に確認できる状態を整えねばならない。最終的にはvimのパッケージマネージャで管理できるようにするべきだが、書いている途中に毎度updateするのはしんどい。それ以上に、パッケージマネージャの仕組みを今から調べる時間はない。

よって、一番原始的な方法で実行する。まず、~/.vim/ディレクトリにftdetectsyntaxというディレクトリを作る。まずftdetectsatysfi.vimというファイルを置き、その中に以下を書き込む。

autocmd BufNewFile,BufRead *.saty,*.satyh set filetype=satysfi

ftdetectは file type detect の略で、これによって*.satyファイルや*.satyhファイルを開いた時にファイルタイプが設定されるらしい。 ファイルタイプがわかったら、シンタックスファイルを選べる。syntaxディレクトリにsatysfi.vimなるファイルを設置する。で、とりあえず以下を書こう。

if exists("b:current_syntax")
  finish
endif

これは、既にシンタックスが定義されていた場合に終了するためのものだ。やっておいた方が行儀がよいだろう。

では、まず手始めにコメントがコメントと認識されるようにしよう。

syn match satysfiComment /%.*/
hi def link satysfiComment Comment

一行目がsatysfiCommentという構文要素の定義だ。名前に続く正規表現、つまり%から始まる文字列にマッチする場合、それはsatysfiCommentである。 続いて、hi def linkは構文要素をCommentというハイライトグループに紐付ける。 カラースキームはこれらの構文要素に色を設定していくものだろう、と思っている(作ったことがないのでこれは予想である)。

グループについてはドキュメントの以下の部分が、

syntax - Vim日本語ドキュメント

vimで使える正規表現は以下の記事が参考になる。

vim正規表現リファレンス - Qiita

基本的には、ハイライトしたいと感じる部分を見出し、一応Lexerを見つつどういったものか確認して、マッチする正規表現を書く、という形でやっていった。 括弧ごと何かしたい場合などは、syn region start="" end=""が、単なるキーワードにはsyn keywordが使える。


困ったのはキーワードのinで、これを単にkeywordにすると、例えばプリミティブのtext-in-mathなどの真ん中のinが誤ってハイライトされる。 普通にやるとケバブ・ケースの命名規則はサポートされないのだ。 ケバブ・ケースといえばLispなのでLispの構文ファイルを少し見に行ったが、難しすぎたので逃げ帰ってきた。 だがこの位なら自力でなんとかできるだろう、と思いしばらくsatysfiパッケージのソースなどを読んでいたところ、in直後に改行もしくは空白のマッチでよいのではという気がしてきたのでそのようにした。

とまあ、いくつかの困ったところに関しては死ぬほどアドホックなことをしているので、まだ色々変わると思われる。 順調にSATySFi(とvimの構文ファイル)に詳しくなれればより改善されていくと思うので、暖かく見守ってほしい。

SATySFiのインストール

SATySFiは静的型検査の恩恵を受けられる組版処理システムである。

github.com

Ubuntu16.04を使っているのだが、SATySFiを使ってみようとして少し困ったので。ちなみにそれまでのOCaml経験はHello, Worldのみ、つまりコンパイラを入れたことがある以外はゼロ。むしろデファクトな環境構築法を知らないまま適当な環境を導入した分マイナスかも知れない。

先に結論から行くと、以下のようにすると上手く行った。シェルはfish-2.7。opamがfishにも対応していて少しうれしくなった。普段使う大抵のソフトウェアはfishに対応していないので。

$ sudo apt-get install opam
$ opam init # 少し時間がかかる。configを弄るのはokした
$ eval (opam config env)
$ opam switch list
... # 確認のため
$ opam switch 4.05.0 # 時間がかかる
$ eval (opam config env)
$ git clone https://github.com/gfngfn/SATySFi.git
$ git submodule update -i
$ opam pin add satysfi .
$ opam install satysfi
$ satysfi --version # 確認
  SATySFi version 0.0.1

最初、出ないはずのシンタックスエラーに遭遇してわけがわからなくなっていた。opamのインストールから始めると上手く行ったので恐らく最初の環境構築時点で何かやらかしていたのだとは思うが、よくわからない。最初のopamのインストールは公式のinstallスクリプトwgetしてシェルに流し込むやつでやったのだが、素直にaptで入れると上手く行った。もちろんopam initとかを忘れていただけの可能性はある。

ちなみにopamをソースからビルドしようとしたところ、opamが依存しているライブラリをダウンロードしようとして、md5sumが違うと言って終了するという事件があった。もちろん確認せずに勝手に解凍されては困るのでこの処理は疑いようもなく正しいのだが、こちらとしてはどうにもならないので辛かった。素直にaptで入れよう。

ちなみに、デモやドキュメントをコンパイルしようとするとフォントがないので落ちる。これに関してはフォントを持っていないこちらの問題なわけだが、フリーなフォントを使用するようにしたブランチとそれを入れていくDockerfileがあるので、それを参考にやっていく。

github.com Comparing gfngfn:master...pandaman64:use-free-font · gfngfn/SATySFi · GitHub

ちなみに、インストール前なら上の比較を見ながら変えればよいが、インストール後は~/.satysfiを見に行くのでそちらの同名ファイルを書き換えなければならない。

というわけでPDFが作成できるようになる。

しばらくデモとドキュメントのPDFとソースを比べながら手さぐりしていけばそのうちなんとかなるだろうと考えているが、果たして。

基本ベクトルの場合の最適化(3次元幾何)

数カ月触れていなかった自分が書いたコードを見た所、驚くべきものを発見した。

3次元空間内をある方向に向けてある距離だけ動いたオブジェクトが衝突するかどうかを判定し、また衝突するときはどれだけ動いたら衝突するか計算するコードがあった。 このようなロジックは、通常ベクトルを用いて方程式を立てて解く。その結果を実装するわけだが、この場合オブジェクトの動きを表すベクトルが以下のような特殊なものであった場合、計算がかなり簡略化できる。 - 単位ベクトル(単位ベクトルに変換する処理が含まれることが多いため) - 軸に平行なベクトル(複数の軸の成分を考えなくてよいため) よって、この性質を併せ持つ軸に沿った単位ベクトル、つまり基本ベクトルの場合、計算が非常に簡単になるわけだ。

問題は、実行中に来たベクトルが基本ベクトルかどうかを判定するのは若干手間であることだ。 通常、数値計算の結果(1, 0, 0)になる、というような値は、大抵数値誤差などのせいで(0.999999999, 7e-15, 5e-16)のような値になる。 もちろん適当なtoleranceを用いて判定することは可能だが、軸に平行な単位ベクトルが来ることがあまり期待できない場合、これは単にコストになってしまう。 さらに、ゲームやシミュレーションなどを考えた時、軸に沿ってちょうど距離1だけ移動する、というようなイベントはそうそう起きるものではない。

ではそれをする意味はどこにあるのか。それは、ユーザーからの入力がある場合である。 ユーザーからの入力は、まだ偶然生じるよりは基本ベクトルになる可能性がある。特に軸に平行なベクトルになる可能性はある(空間中に突然オブジェクトを作り、そのまま下に降ろしていく、など)。 そう思ったのかは知らないが、数カ月前の自分はそれを想定していたらしい。コード中に、3次元ベクトルクラスの他に基底ベクトルが存在したのだ。

基本ベクトルクラスは通常のインターフェースを持つが変更は許さず、積や和を作ると通常のベクトルクラスを作成して返す、というようになっている。 長さを計算するルーチンのみならずドット積やクロス積もオーバーロードされて高速化されている。 衝突判定のコードはというと、is_pointなどのメタ関数によるSFINAEが飛び交っており、非常に面白くなっていた。

このようにすると、型レベルで分岐が行われるので(コンパイル時に上手く決められるようにすると)基本ベクトルが来ることを保証できる。 なので、基本ベクトルを前提にした最適化が許されるというわけだ。

まあ、手間に見あうとはあまり思えないので、今から消すのだが。単にcollision_zのような関数を定義すれば済んでしまうので、ホンの少しだけ不格好なことを除けば何らデメリットはない。

コンパイル時ルックアップテーブル生成について

(今更感)

目的

非負整数値を取る関数があるとする。そしてそれを実行中に非常に多くの回数呼ぶ(数百兆回とか)、ということは、科学技術計算ではよく見られる光景である。 整数値を取るので、恐らく何度もピッタリ同じ値を計算することになるだろう。 すると、何度も呼びそうな範囲は先に表にしておいて、それを見に行くことで計算時間を短縮する、という発想は自然なものに思える。 配列アクセスが計算より早い場合はこのテクニックは非常に有用だ。ルックアップテーブルという名前まで付いている。

これが実数値を取る関数だと全く同じ浮動小数点数が来る確率は低いので単純なルックアップテーブル作成は難しくなる。 その場合、メモリが足りるなら十分小さい幅ごとの代表値を表にしておくとか、計算が本当に重くて簡単な補間の方が早い場合は、一定値おきの値を使って引数での値を補間するとかいった方法を用いたりする。

さて、C++ではコンパイル時に計算ができる。つまり、コンパイル時にルックアップテーブルが作れるのだ。 ルックアップテーブルを作るとき、普通はビルドスクリプトの中で適当なスクリプト言語から何かライブラリを呼び出してヘッダファイルを生成するのだが、面白いのでコンパイル時に作ってみよう。

例:階乗関数

インターフェース

例として、単純なので階乗関数を考えてみたい。N=100くらいまでのルックアップテーブルをコンパイル時に作ることを考える。 普通に実装すると以下のようになるfactorialだが、

template<typename Real>
constexpr Real factorial_impl(std::uint32_t i) noexcept
{
    return i==0 ? 1 : static_cast<Real>(i) * factorial_impl(i-1);
}

ルックアップテーブルが完成すれば、factorialは以下のような実装になるだろう。

template<typename Real>
constexpr Real factorial(std::size_t i) noexcept
{
    return factorial_table<Real>::get(i);
}

では中身について考えていきたい。factorial_tableは以下のようになっていると考えられる。

template<typename Real, std::size_t N>
struct factorial_table
{
    constexpr static std::size_t size = N;
    constexpr static std::array<Real, N> value = /* ... ??? ... */;

    constexpr static Real get(std::size_t i) noexcept
    {
        //C++11ではstd::array::operator[]() constはconstexprではない。
        //C++14からstd::array::operator[]() constがconstexprに、
        //C++17からstd::arrayのメンバの殆どがconstexprになる。
        return factorial_table<Real, N>::value[i];
    }
};

template<typename Real, std::size_t N>
constexpr std::size_t factorial_table<Real, N>::size;
template<typename Real, std::size_t N>
constexpr Real factorial_table<Real, N>::value[N];

/* ...???... */の部分をどうするかだ。

配列生成

こういうときのために、C++14にはstd::index_sequenceなるものが存在している。これは整数シーケンスを表現する型、integer_sequencesize_tに対する特殊化である。 cpprefjpによると以下のようなものだ。

integer_sequence - cpprefjp C++日本語リファレンス

namespace std {
  template <class T, T... I>
  struct integer_sequence {
    using value_type = T;
    static constexpr size_t size() noexcept { return sizeof...(I); }
  };
}

これを使うと、variadic templateで渡した整数値を関数内で展開できる。 variadic template argumentの展開は、関数を噛ましつつ行うことができるので、以下のような関数が書ける。

template<typename Real, typename Integer, Integer ... vals>
std::array<Real, sizeof...(vals)>
generate_array(std::integer_sequence<Integer, vals...>)
{
    return {{factorial_impl(vals)...}};
}

パラメータパックの展開により、この関数を以下のようにして呼ぶと

constexpr auto a = generate_array<double>(
    std::integer_sequence<std::uint32_t, 0,1,2,3,4,5>{});

このa{factorial(0), factorial(1), factorial(2), factorial(3), factorial(4), factorial(5)}になるのだ。 これを使うことで、コンパイル時に好きな整数シーケンスを好きな関数で変換した静的配列を生成できる。 しかしこのままだと手でinteger_sequence<std::uint32_t, 0, 1, 2, 3, 4, 5, 6, ..., 100>みたいなのを書く必要があり、無理になってしまう。 もちろんC++がそんなことを許すはずはない。std::make_integer_sequence<Int, N>なるものがあり、これは<Int, 0, 1, ... , N>を一発で作ってくれる。 これにより、

constexpr auto a = generate_array<double>(
    std::make_integer_sequence<std::uint32_t, 100>{});

と書くことができるのだ。

make_integer_sequence - cpprefjp C++日本語リファレンス

C++11縛り

ただ、C++11だとこのinteger_sequenceは存在しない。縛りプレイのために、一応、これをどのように作るか少し考えてみよう。 少々面倒なことが起きるので、まずsize_t決め打ちでindex_sequenceを作る。integer_sequenceは、その後中身をstatic_castすることで作れる。 負の長さを持つ列、というのはないので、深く気にしなくていいのは楽だ。

template<std::size_t ... vs>
struct index_sequence{};

template引数だけが必要なので、中身は別にいらない(sizeとvalue_typeくらいは定義すべきだが、煩雑になるのでやめた)。 0, ... Nみたいなのをつくりたいので、再帰{0, 1, ..., N-1} + {N} -> {0, 1, ..., N-1, N}のようにしていくことを考えた。 そのためには、まず2つのindex_sequenceを結合する必要がある。

template<typename T1, typename T2>
struct index_sequence_concatenator;

template<std::size_t ... v1, std;;size_t ... v2>
struct index_sequence_concatenator<
    index_sequence<v1...>, index_sequence<v2...>>
{
    typedef index_sequence<v1 ..., v2 ...> type;
};

これを使って{0, ..., N}を生成しよう。

template<std::size_t N>
struct index_sequence_generator
{
    typedef typename index_sequence_concatenator<
            typename index_sequence_generator<N-1>::type,
            index_sequence<N>
        >::type type
};

template<>
struct index_sequence_generator<0>
{
    typedef index_sequence<0> type
};

というわけでできた。使いやすいようにエイリアスを定義しよう。 長さがNで0始まりなので{0, 1, ..., N-1}になることをすっかり忘れていたのでエイリアスでこっそり修正しておこう。

template<std::size_t N>
using make_index_sequence =
    typename index_sequence_generator<N-1>::type;

というわけで、C++11でもindex_sequenceが作れて、コンパイル時ルックアップテーブルができた。