Gitbookで生成したファイルがGitHub pagesに無視される

TL;DR: .nojekyllという名前の空ファイルをgithub pagesのルートに入れる

タイトルの通りの現象が起きて困っていた。

状況としては結構こんがらがっていたのだが、順に説明していこうと思う。

以前に書いた方法で、Gitbookを使って生成したHTML/CSS/JSその他をgh-pagesブランチにぶち込んだ。そこで数式表示のためにmathjaxを使っていたのだが、何か読み込みと実行とのタイミングがずれているらしく、ページを開いただけでは数式が出てこず、移動せずにF5などでページを更新して初めて数式が出てくるようになった。普通の人はWebページを開いたあとで戯れに一度更新してみたりはしない。よってこれは問題だ。

これを解決するために、mathjaxの設定として"forceSVG": trueを追加した。これでページ生成時にsvgファイルも一緒に設定され、htmlファイルはそれを読み込むだろうから、mathjaxの実行タイミングの問題は解決するはずだ。

ところでここで完全に別の問題が起きたので、並行して無理やり解決した。その問題はというと、mathjax関連のJSコードから、Error: TypeError: speech.processExpression is not a functionなるエラーが出てファイル生成が中止されてしまうというものだ。これは、最終的にこの人の解決策を流用することにした。

Error: TypeError: speech.processExpression is not a function · Issue #2 · kgryte/tex-equation-to-svg · GitHub

mathjaxが古いAPIを叩いていることが原因らしいので、この呼び出しを全てtoSpeechにすれば解決する。未だにNPMがどうやってパッケージを管理しているか理解していないので、ローカルにダウンロードされてきたパッケージのソースコードを直接sedした。GitHub pages用のファイルが生成されるまでの一瞬だけ動けばそれでいいんだよ!!!

というわけでこの問題は解決したのでページが生成されるようになったのだが、見てみると何故かmathjaxの画像が全て404になっている。生成できていないのかと思ってGitHubを見に行くと、gh-pagesブランチには同名のファイルがある。中身も正しい画像だった。だがその名前をコピペしてもGitHub pagesでは404 File Not Foundになる。完全にわけがわからなかった。

そこで「github pages file 404」とかで検索するとStackoverflowで似たような問題に出くわしている人がいた。以下の回答が今回は有用だった(most votedでもbest answerでもなかったので質問者の問題は別のところにあったのだろうが)。

How to fix HTTP 404 on Github Pages? - Stack Overflow

私はすでに忘れていたがGitHub pagesはjekyllを使って書くと想定されているので、jekyll的に無視するべきファイルは無視するようになっている。_で始まる名前のファイルなどだ。mathjax_mathjax_XXXXXXXX.svgみたいなファイルを生成するので、ものの見事に全て無視されていた。というわけで、GitHub pagesに「このページはJekyllとは関係ないですよ」と伝える必要がある。これは、.nojekyllという名前のからのファイルをGitHub pagesのルートにおけば良い。

というわけで、最初の問題、「ページを更新しないと数式が表示されない」が解決した。めでたしめでたし。面倒くさすぎるだろ何だこれ

小さなlisp処理系を作った

ふと、そういえばbrainfuckよりも高級な言語処理系を作ってない(太古の昔に作ろうとした滅茶苦茶なやつは除く)ことを思い出し、ちょっとlisp処理系でも作るか〜〜と思って実装した。連休だし、普段やってるプロジェクトしかやらずに過ぎていくのももったいない。

「あの機能使いたいな〜」みたいな雑念に惑わされたくなかったので、一番手に馴染んでいるC++、それも最新規格の17を使うことにした。Cで書く、とか標準ライブラリを使わない、とか色々な縛りが考えられるが、それはまあ一回作ってからチャレンジした方がいいだろう。

変数と関数を宣言できるくらいまで実装するまでにだいたい3時間くらいかかった。この時間は概ね始める前にこれくらいで済めばいいな、と思っていたのと同じくらいだったので満足している。

GitHub - ToruNiina/smallisp: a small lisp implemented in C++17

; comment
(define (increment x) (+ x 1))
(let a 0)
(+ (increment a) (+ 2 4 6) 3 5)

上のようなファイルを渡すと、下のような結果になる。一つのリストが評価される度に評価結果が出力されるので、3行表示されている。

$ ./smallisp sample.sl
(increment x)
a
21

一応、以下のような仕様になっている。

  • ファイルを渡すと実行する(対話的にはできない)
  • (let <symbol> <expr>)で変数宣言
  • 変数の型は整数・関数・コンスセルのみ
  • (define (<symbol> ... ) (<expr>))で関数宣言
  • ビルトイン関数は+, -, car, cdr, printlnのみ
  • スコープはない(関数の引数が同名の外の変数を上書きする)
  • GCもない(関数の引数を含め、全ての変数が定義されたら終了するまで生き残る)

変数宣言と関数宣言ができるようになったのでまあもうこんなもんでいいんじゃないの、と思ってここで止めている。比較演算子とか文字列サポートとかするべきことは結構ある気はするが、やろうと思えばできる、というところまで来て熱が冷めてきた。

それにしてもlisp処理系が簡単だというのはその通りっぽい。

私自身はlispを常用しているわけではなく、一年くらい前にgaucheを使ってproject eulerの問題(別言語で解いたことがある)をschemeで書いて練習していたくらいのレベル感だ(なのでちょっと変なところがあったりするかもしれない)。

言語処理系に関して体系的に学んだこともないため、割とゴリ押しで突破している。一応、大分忘れているが以下の本を読んだことがある。

www.oreilly.co.jp

そんな私が3時間くらいで書けるというのは意外なレベルの簡単さだ。

あまり自明ではないなと感じた(そして無理やり突破した)ところについて、少しメモ書きを残しておこうと思う。断っておくが、上記のようなレベル感なので、以下のやり方が、例えば効率がいいとか、実装が綺麗になるとか、そういうことはない。とりあえずそうしたら動かせた、というだけなので注意していただきたい。

とはいえ、こんなにできることが少ないのだから非自明な部分も殆ど無い。ここで、言語処理系を作ろうと思いたつような人は、以下のようなことは自力で実装できるものと勝手に思っている(これはスタート時の私を想定している)。

  • (fn (+ a b) -10)のような、ASCII列のsymbolと整数のみで構成されるリストを正しくパースし、木にできる
  • (+ 1 (- 4 2))のような、整数と四則演算だけで構成される構文木evalできる

この辺りができるなら、実質困るのは変数宣言と関数宣言くらいだ。

変数定義

これは、GCとスコープを導入するのを諦めた瞬間に自明になった。つまり、以下のようなenvがあればよい。

std::map<symbol_t, object_t> env;

シンボルからオブジェクトへのマップがあれば、シンボルをオブジェクトに変換できる。なんだこの自明な文章は。言い換えよう。シンボルをevalする際はマップを検索して見つかったオブジェクトを返せば良い。

そう実装しておけば、構文木evalしていく時に変数が出て来たとしても、eval中に変数はenvから検索されて一度普通のオブジェクトになる。普通のオブジェクトになったら話は簡単だ。単に評価すればよい。

(let a 100) ; ここで`env["a"] = object_t(100)`が実行される
(+ a 50) ; ここで、`eval({"+", "a", 50})`が実行される
; ` => eval(env["a"]) + 50`
; ` => 100 + 50`

ここにスコープやGCを導入しようとすると、このままではちょっといただけない。何か策を練る必要があるが、やっていない。多分考えるより普通に本読んで勉強した方が早い。

関数定義

ここで一番時間を使った。

ユーザー定義の関数は、ビルトイン関数、例えば足し算とか、とは実装方法が違ってくる。ビルトイン関数は、関数を書いた後それをオブジェクトの一種としてそのままぶち込めば実装できる。

struct func_t
{
    std::function<object_t(const object_t&, env_t&)> fn;
};
struct object_t
{
    std::variant<nil_t, cell_t, func_t, ...> data;
};

object_t builtin_plus(const object_t& arg, env_t& env)
{
    // ...
}

env["+"] = func_t(builtin_func);

ユーザー定義関数にこの方法は容易には適用できない。関数は、引数のリストと、引数を使った手続きという形で与えられるので、そのように動くC++関数をその場で生成するのは難しい。

だが、要するに構文木が来ているだけだと気づいて、引数の名前と単にfunction-bodyの定義そのもののリストを持たせておけば良いのだとわかった。関数が呼び出されると、引数として渡された値をenvに登録し、その後普通にfunction-bodyとして持っているコンスセルを、関数でもなんでもないただのリストだと思い込んでevalしていく。すると関数が実行できる。

これに気づくまでは結構時間がかかったが、気づくと一発で腑に落ちた。リストがそのまま構文木として機能することの妙というか、考えてみれば当たり前なのだけれど。

スコープを諦めたことで何が起きたか

この記事を直前の節まで書いて下書き保存したあと食事を摂っていたのだが、その時ifがないのは流石にダメだろうと思って(if (cond) (then) (else))と比較演算子を導入した。じゃあ記念にフィボナッチ数列でも計算するか、とlispスクリプトを書き始めたところ、奇妙なことが起きた。

最初に以下のようなコードを書いた。

(define (fibo-aux n m next curr)
    (if (= n m) curr (fibo-aux n (+ m 1) (+ next curr) next))
    )

(define (fibo n)
    (fibo-aux n 0 1 0)
    )

(println (fibo 1))
(println (fibo 2))
(println (fibo 3))
(println (fibo 4))
(println (fibo 5))

動きそうに思える。だが結果はこうなった。

1
2
4
8
16

なんだろう。再帰は正しくできていそうに見えるのだが、答えが明らかに変だ。しばらく考えて、関数呼び出しの際に何も考えずに引数リストの前から評価した値をenvに追加していっていたことに気づき、かつ最初に呼ばれたfibo-auxとそこから再帰的に呼ばれているfibo-auxが同じ変数名を共有しているために、関数呼び出しの中で引数を渡す際にこの関数での引数が上書きされていることに気づいた。

これで説明になっているのかわからないのでもう少しちゃんと喋ると、

(define (fibo-aux n m next curr)
    (if (= n m) curr (fibo-aux n (+ m 1) (+ next curr) next))
    )

このコードの、

(fibo-aux n (+ m 1) (+ next curr) next)

この部分で、第三引数に(+ next curr)が代入されている。これは内部ではenv["next"] = env["next"] + env["curr"]になっており、この瞬間に実行されている。続いて、env["curr"] = env["next"]が実行されるが、このenv["next"]はさっきすでに変更され、next + currになっている。なので、全体がフィボナッチ数列にならずに、2のべき乗になってしまった。

これに気づいて以下のように書き換えると、期待通りフィボナッチ数列が出力された。

(define (fibo-aux n m next curr)
    (if (= n m) curr (fibo-aux n (+ m 1) (+ next curr) (- next curr)))
    )

(define (fibo n)
    (fibo-aux n 0 1 0)
    )

だが流石にわかりにくすぎるので、解決策を考えた。これは、関数を呼び出す際にenvを上書きしているから起きる問題だ。なら、関数を呼び出す際にenvをコピーして、そこに次の引数を代入し、新しいenvを使って関数の内容を評価すれば良い。

これで最初のコードが期待通り動くようになった。ついでに、関数のローカルスコープという概念が発生した。つまり、関数が呼び出されるごとにenvがコピーされるので、関数呼び出しの際に外のenvまで引数が漏れなくなった。

その他雑多なこと

コンスセルを実装するとき、コンスセルはオブジェクトの一種なので型が循環し、不完全型が登場する。

struct cell_t
{
    object_t car, cdr; // ここではまだ`object_t`は定義されていない
};
struct object_t
{
    // これを先にすると、今度は`cell_t`が定義されていない状況になる
    std::variant<nil_t, cell_t, ...> data;
};

というわけで、最初はstd::unique_ptrを使ってコンスセルを作っていた。非常に順当だ。

struct object_t; // 前方宣言
struct cell_t
{
    // ポインタならサイズがわかるのでとりあえずOK
    std::unique_ptr<object_t> car, cdr;
};
struct object_t
{
    std::variant<nil_t, cell_t, ...> data;
};

が、だんだん面倒になってきた。気軽にコピーできないし(ちゃんとムーブしろという話だが)、使うときにいちいちデリファレンスするのもだるい。

そこで、今使っているのがC++17だということを思い出した。C++17からアロケータに不完全型サポートが入ったため、vectorlistforward_listには不完全型を格納することができる。

つまりこれが許される。

struct object_t; // 前方宣言
struct cell_t
{
    // ここではまだ`object_t`は定義されていないが、vectorに入れられる
    std::vector<object_t> objs;
};
struct object_t
{
    std::variant<nil_t, cell_t, ...> data;
};

ちょっと意外なところで便利なことがわかった。

感想

書いてみて初めてわかることってやっぱり結構多いんだな、という認識を新たにした(N回目)。

追記

文字列とmodを実装し、FizzBuzzが動くようになった。

(define (print-fizzbuzz n)
    (if (= 0 (% n 15))
        (println "FizzBuzz")
        (if (= 0 (% n 3))
            (println "Fizz")
            (if (= 0 (% n 5))
                (println "Buzz")
                (println n)
                )
            )
        )
    )

(define (fizzbuzz-aux n m tmp)
    (if (= n m) tmp (fizzbuzz-aux n (+ m 1) (print-fizzbuzz m)))
    )

(define (fizzbuzz n)
    (fizzbuzz-aux (+ n 1) 1 nil)
    )

(fizzbuzz 30)

この辺りで、文はかならず値に評価され、評価を続けることで実行するというモデルだとちょっと面倒になった。複数の文を書くことができる仕組みがないのだ。 ループがないので再帰しているのだが、prinlnnilを返すので、再帰のときに無意味な引数を作ってそこにprintlnを入れている。引数は評価されるので再帰する際の引数評価でprintが実行され、FizzBuzzになる。

toml11をバージョンアップした

しすぎじゃない?

変更点

まずは、C++17になっていたら文字列をstd::string_viewで受け取ったり、toml::valuestd::string_viewで初期化できるようにした。どうやらC++17で使っている人がいたっぽいので、特に要求はなかったがあったほうがいいかなと思って入れた。C++17の新機能の中でもstring_viewはかなり待ち望まれていた機能でもあるし、使っている人も比較的多いのではないか。

あとは、値を取り出すときに、簡単に書くためにas_integer()とかas_string()みたいなのを入れた。これは複雑な変換はできないが、今ちょっとだけ中身を覗きたい、というときに仰々しくならないので便利だ。

const auto v = toml::parse("sample.toml");
if(v.is_integer() && v.as_integer() == 42) // あっさり
{
  // ...
}

あまり順当でない変更としては、コメントを取得できるようにしたことだろう。以下のようなファイルがあったとき、

# comment for a.
a = 42

b = 3.14 # comment for b.
const auto data = toml::parse("sample.toml");
std::cout << data.at("a").comment();
// "# comment for a."
std::cout << data.at("b").comment();
// "# comment for b."

のようにして関連するコメントを取り出せる。

こんな機能足したら重くなるんじゃない? というのは当然の疑問だと思うが、重くはならない。ここまでの実装からコスト無しに導入できる機能だったので、それと要望もあったので、入れた。

前に記事を書いたとおり、toml11では、各toml::valueがファイル内のどの領域に対応するかを保持している。これは前にも記事を書いたとおり、エラーメッセージのためだ。値が文字列であることを期待して変換しようとしたが失敗した、というとき、何行目で何が書かれているのか、型は何で何への変換に失敗したのかなどをパースが終わってからも出力するためだ。以下のように。

terminate called after throwing an instance of 'toml::type_error'
  what():  [error] toml::value bad_cast to integer
 --> example.toml
 3 | title = "TOML Example"
   |         ~~~~~~~~~~~~~~ the actual type is string

ここでは、整数だと思って取り出そうとしたら文字列だった、というエラーが表示されている。これを表示するにはファイル名と部分文字列と行数を覚えておく必要がある。だがそれを全てのtoml::valueが覚えるのはしんどいので(配列とかだと部分文字列が超長くなることもある)、実際にはファイルの全内容とファイル名を入れた構造体へのshared_ptrと、その中で何文字目から何文字目かだけをtoml::valueは覚えている。ファイル中での位置はパースの時も使っているから、廃物利用だ。地球に優しい(無駄なコピーを発生させないことによってエネルギー消費を抑えているため)。

で、ここでファイル内の全データとその値が対応する場所を覚えているということは、その周囲にあるコメントを検索できるということでもある。value.comment()を呼ぶと周囲のコメントを探し、見つけた分だけ返してくれる。よってtoml::valueにはデータメンバは一切追加されていない。また、パース時もコメントは今までどおりガン無視している。もしコメントが必要なら後で探せばいいので。パース時はガン無視しているのに後でコメントを取得することもできるというのはちょっとおもしろい。

今後の方向性

問題点としては、これは単にコメントを取得できるようにしただけであって、コメントを編集することはできないということだ。編集できないならあまり意味もないかと思い、シリアライズの時も気にしていない。ついでに、値のデータが変更された時は、基本的にファイル内のどの領域に対応していたかという情報は失われる。なので、まあまだあまり役には立たないだろう。

将来的には、シリアライズの際にコメントを色々できるようにしてみたい気持ちは少しある。だが、コメントは必要無い場合が多かろうとも思うので、必要のない場合はオフにできる機能であってほしい。だがtoml::valueの構造を変えるとなるとかなり大きな変更ということになるので、メジャーアップデートとして出したい。

そうなってくると他にもやりたいことが色々ある。例えば、初期はキャメルケースを使っていたが途中でスネークケースに切り替えたなどの経緯で滅茶苦茶になっている命名を統一したい(今の所、キャメルケースのAPIは一切触らずに使えるようになってはいるので、最近知って使ってみようとしてくれている人は「そうだったの?」くらいの話かも知れない)。命名を直すのはとてもやりたくてウズウズしているが確実にユーザーコードをぶっ壊すのでやってこなかった。メジャーアップデートにしかならないが、名前を直すだけのメジャーアップデートって……と二の足を踏み続けている。だが便利機能がいっぱい入るならついでにやるのはありかもしれない。移行準備は色々やらないとダメだろうが……(片方をdeprecateしておいて両方使える期間を取るとか)。

あと、toml::parsetoml::tableを返す(toml::valueではなく)のも修正したい。これは初期からのことで、TOMLファイルがテーブルに一対一対応するからなのだが、今やvalueはただのtagged-unionではなく、ファイル内の位置などの情報を持ってしまっているし、その情報を利用するために「toml::valueをテーブルだと見当を付けて値を検索する」というような機能を足してきているので、逆に不自然になってしまった。今になって見るとtoml::tableは、ただのunordered_map<key, value>エイリアスなので、多機能なtoml::valueに比べて前面に押し出すにはあまりにも簡素すぎる。当時は全てが簡素だったのでバランスも取れていたのだが、toml::valueの機能が増えて重点がそっちに移ってしまった。

他には、コンテナの種類を選べないのも気になってはいた。std::unordered_mapは定数時間でルックアップができるが、メモリをそれなりに使う。std::mapの方が良い場面もそれなりにある、というような記事は見るし、かなり使う要素でもあるので、そうなると選べるようにしておきたい。そうしておけば、flat_mapが入った時も対応が簡単だ。その場合、まさしく型を変えるのだから、これはテンプレートを使う以外の方法はない。あと、配列を格納するときにstd::vectorを使うことに文句を付ける人は少ないかも知れないが、一応std::dequeとかに切り替えられるようにするのはありかも知れない。

だが、普通に考えるとtoml::valueがテンプレート引数を取るとは思わないので、そこは隠さないといけない。デフォルトテンプレート引数はこういうときは不便で、C++17以前だとtoml::value<> v = ...のような奇妙な宣言になってしまう。なのでデフォルト引数でうまく隠すことはできない。隠すとしたら、std::stringのようにエイリアスを使うしかない。つまり、toml::basic_value<...>を作っておいて、using toml::value = toml::basic_value<...>のようにするのだ。

そうしておけば、コンテナの種類も変えられるし、コメントをstd::stringのようにして別に保持するかどうかも決められる。アロケータも変えられるようにしてもいいのかもしれない。toml::valueにはデフォルトの型を設定する必要があり、それを決めるのも難しくはあるが、まあ何とかなるだろう。型パラメータの異なるtoml::value間の変換は難しい話だ。それに関してはサポートしなくてもいいかもしれない。他の問題としては例えば、toml::arraytoml::tableのような、コンテナの型に依存してしまう型名はややこしいことになるが、デフォルトの型を入れておくということでよいのではないだろうか。

指定はどうするのが良いかだが、これは決まっている。関数テンプレートの場合はデフォルトパラメータを使うときに<>が必要無いことを利用して、toml::parseをテンプレートまみれにすればよい。autoで受け取っていれば簡単だ。

const auto v = toml::parse("sample.toml"); // デフォルト
const auto v = toml::parse<toml::comment::preserve, std::map, std::deque>("sample.toml"); // カスタム

のようにすればいいのだ。

こうすれば、デフォルトでいい場合は今まで通りの書きかたで動き、カスタマイズしたい場合は必要に応じて設定を色々できるということになり、悪くない辺りに落ち着くのではないだろうか。むしろ何で最初からこうしなかったんだろ。多分パーサを書くところで手一杯だったんだろうな。

とまあ、やりたいことは沢山あるのだが、やることが結構種類があって手が回らないというのと、疲れているのかわからないが「よっしゃ書くぞ!」となる時間が短くなってきている気がするのが懸念材料だ。上記のを全て盛り込むととても大きな変更になるが、バージョン3、いつ出せるだろう。

fishでgitの補完が遅い場合は3.0にアップデートする

遅すぎた(間違えてtabを押すと数秒止まる)ので「fish completion slow」とかでぐぐってみたところ、「遅いよ」なるIssueが立っていた。

github.com

このコメントで「3.0で速くしたよ」というコメントがあった。

Slow git auto-complete... how to turn off? · Issue #4762 · fish-shell/fish-shell · GitHub

のでアップデートしたら実際速くなった。それだけ。

ソースからビルドしたのだけれど、普通にaptとかにビルド済みのものがアップロードされているらしい。

Packages in “fish shell - 3.x release series” : fish shell - 3.x release series : “Fish shell maintainers” team

まあ自分でビルドしてもそんなに時間はかからないので、どっちでもよいのではないか。

追記:前まで使っていたものは2.7.0だったっぽい。

toml11を60倍高速化した話

toml11はしばらく前に開発して、最近も結構いじり続けており、それなりの数のユーザーがついてるっぽくて結構嬉しくなっているライブラリだ。そもそもが自分のために作ったものなので、自分の都合で結構改変することがある。これは、まあレポジトリのオーナーなので当然と思っているし、作者が困ることは大体ユーザーも困るだろうから、むしろ放置するより良いことだろうと考えている。*1

github.com

折角これを作っているので大体自作のアプリケーションではtomlを使っているのだが、そこに自動生成した5万行のtomlファイルをぶち込んだら、パースが終わるまでに3分ほどかかった。これは流石に遅い。実際の計算は何時間、何日というオーダーでかかるので3分は誤差なのだが、設定ファイルが正しくてちゃんと動くことを確認したいだけ、という場合が考えられる以上3分は遅すぎる。この5万行というファイルサイズはそのプロジェクトでそんなに例外的に大きいわけではなく、まあそういうこともあるよね、という程度なので、これくらいならせめて5秒以内くらいに終わって欲しい。

というわけで、3分を3秒まで高速化した。

雑感

元々のコードはどちらかというと、速度面に関しては深く気にしておらず、流石にアホすぎるコードは書かないようにしようくらいの気持ちでしかなかった。設定ファイルの読み込みがホットスポットになるケースはあまりないと思われるからだ。ホットスポットでないなら、求められるのは速度ではない。やっていることは設定ファイルのパースなので、どちらかというと求められるのはエラーメッセージのわかりやすさや、コードの書きやすさだと思っていたからだ。今もそう思っているが、遅いと感じた以上少しは高速化しなければならない。

既に結構最適化されているコードを追加で最適化するとなると長丁場になる。初期からある程度最適化が行われている以上、現在地点からあまり大きく変更せずにたどり着ける局所最適くらいまではたいてい既にたどり着いているからだ。プロファイルを取っても実行時間は均一でホットスポットはない。ここから速度を上げようとすると、ライブラリを変えるくらいで済めば良いほうで、コンポーネントのそれぞれを少しずつジリジリと高速化していって最終的に全体を速くするか、設計を変える(つまり書き直し)レベルの変更が必要になることが多い。時代背景が違うコードなどは最初のコードをほぼ完全に捨て去ることで2倍くらい速くできたケースは何度かあるが、遅くなってしまうこともなくはないので、結果が出るまでが長い博打になってしまってつらいものがある。それも2倍程度の高速化のために。100倍なら喜んで何週間かベットするんだけどな。

対して、最初はあまり速度のことを考えていなかったコードを高速化するのはかなり簡単だ。プロファイルを取れば大抵ホットスポットが明確に決まるし(一つの関数が実行時間の8割を占めているなどはザラだ)、そういう場合は始めてすぐに10倍とか100倍速くなったりする。世の中の最適化に対する教えや金言、曰く「早すぎる最適化は悪」とか、「80−20の法則」とか、「〇〇(不向きなデータ構造やアルゴリズム、ヒープアロケーション、割り算、etc)を避けよう」とかそういうやつは、大抵この場合のことを指している。そこを見誤ると一向に性能が上がらなかったりするので注意したい。速くなりようがないようなまずい設計で全体を作ってしまった場合は部分的にでもいいから設計からやり直すほか無いのだが、「動いてるコードに手を入れるな!」「一から書き換えるのは悪手!」みたいなのと共にそれを封じられる場合がある。

動いているコードに手を入れるコストを下げるために自動テストがある(「動いているコードに手を入れるな」、と思考停止で言ってくる人が権限を持っているレポジトリには大抵テストコードはない(偏見))。そもそも何かしらのテストがなければ、動いていることは何の保証にもならない。動いているが間違った答えを返し続けている可能性は普通にある。テストされている分しか実質的に保証できないなら、手を入れてテストが通ったなら、何の問題があろうか? また、一から書き換えるのは確かに悪手であることが多いが、規模(機能の数など)が小さければ問題にならないし、速くするためには実質的に書き直すしかない場合もそれなりにある。その上で書き直しを選択するかどうかは議論が必要だが、即却下するよりは少しは考えてみたほうがよい。

「早すぎる最適化は悪」というのは、最適化の主戦場がアセンブリレベルのバイナリハックで、最適化するとマジで全く何をしているか何もわからないコードになっていた時代に発せられた金言であり、コンパイラがそのかなりの部分をこなせるようになった今となっては、誤った文脈で引用されて人々の動きを止めてしまうことの方が多いように感じる。最初に最適化しづらい構造にしてしまうと尾を引いてしまうので、細かいトリックはしなくていいから、全体の見通しの立てやすい、あとで取り替えの効く疎結合な設計のために最初に少しは時間を割いた方がいい。そもそも、「最初から変なトリックで最適化するよりもちゃんと綺麗でわかりやすいコード書いとけ」という話なので、設計をちゃんと考えようという主張にこれを持ち出して「何でもいいからとっとと書け」というのは筋が悪い。

設計を決めるときに一般的に適用できるソフトウェア的ツールや考え方はあまりない。ないものは伝えられないし、強いて言うと大規模なコードをメンテ・高速化した経験や計算機科学と低レイヤーの知識、コードが解こうとしている問題への理解度くらいしかないので、無理に言及すると「勉強しつつ経験を積み、コードの内容を理解しましょう」という身も蓋もない話になってしまう。なので簡単でバズるTipsは局所最適のためのツールに終止するわけだが、このせいで世の中のプログラムは鈍重になっているのではなかろうかとすら思う(私の観測範囲はかなり特殊な分野に限定されているので、真の”世の中の”プログラムはもっとまともだと信じたいが)。

本題

さて、金言に対してさんざんなことを書いてはみたが*2、今回は最初は何も考えていなかったケースなので、広く知れ渡っている金言が全部おもしろいくらいに当てはまる。普段既に結構最適化されているプログラムをさらにねじって絞り切るような最適化をしているので(手が痛くなってやめることが多い)、普通の最適化はこんなに簡単なのか! と笑みすらこぼれた。

まず、こちらはいかなる場合でも常に成り立つ最適化の金言、「推測するな、計測せよ」を実行した。ただでさえ遅いコードをvalgrind --tool=callgrindに渡したので非常に時間がかかった(典型的には数十倍遅くなる)。だが待ってみただけのことはあった。

とはいえ何も考えずに待っているのも暇だし、勘を養うために(養えるかはともかくとして)予想は立ててみた。まず、toml11はエラーメッセージを綺麗にすることを目標の一つにしている。なのでエラーメッセージに比較的重めの処理が入ることを許容していた。さらに、toml11のそれぞれのサブパーサ、parse_valueparse_integerなどは、失敗するとエラーメッセージを返すのだが、parse_valueはどの型の値が入っているか調べもせずに成功するまで全ての型のパーサを呼ぶ(これはトークナイザをしっかり作りこむのと比べてあまり賢くないというのはわかってはいる)。ここでは文字列の連結などの操作をたくさんするので、そこで小さなヒープアロケーションが頻発するのが主な問題なのではなかろうか、と考えていた。解決策としては、エラーメッセージの定型を整理して、前もってスタックに用意しておいたバッファにstd::snprintfなどで書き出してから、そのバッファをstd::stringに渡せばいいだろうか、と考えていた。

さて、蓋を開けてみたところ、この予想は半分外れていた。parse_valueparse_stringやらparse_integerやらを手当り次第に呼ぶことによるエラーメッセージ地獄というのは当たっていたが、問題になっているのはヒープアロケーションではなかった。エラーメッセージに書き出すための行数カウントだったのだ。これが全体の98%ちょいを占めていた。98%ちょいって全部じゃん。

基本的に、toml11はまずファイル全体を読み込んでおいて、それをtoml::valueで共有管理し、パースが終わった後もエラーメッセージのために定義箇所付近を辿り返せるようにしている。このためにパース途中もイテレータをラップしたlocationというものを関数間で受け渡しつつパースを進めているので、エラーメッセージは基本的にこれの位置に基づいて出力することになる。パースに成功したら、範囲を表すregionを作ってtoml::valueに渡している。

このlocationregionからエラーメッセージを生成するとき、何行目でエラーが起きているかを表示するために、行数を取得するメンバメソッドを用意してある。これは単純な作りで、std::count(begin, current, '\n')を返すだけだった。そしてこれが実行時間の98%だった。5万行ともなれば、流石に一行に10回も改行文字の数を数えてたら時間も食いますわな。

というわけで、locationを少し改造し、イテレータを進める・戻す操作の際に必ず改行回数の増減をチェックし、行数を取得する関数は単にカウント済みの値を返すだけにした。するとこの98%ちょいがまるごと消え去り、全体が60倍速くなった。

な〜んだ、最適化って簡単じゃん!(既にある程度最適化済みの大規模な数値計算のコードを見て絶望する)

高速化後のプロファイルも見てみたが、これの他にはそこまで目立ったものはなかった。他に時間を食っているのは出力とヒープアロケーションのようで、まあ順当ではあるがずば抜けて時間を食っているわけではないのでもういいかな、という具合だった。

この手の高速化を1、2回やると、大体残りはどんぐりの背比べになってしまって、明確なホットスポットはなくなる。なのでこれ以降の最適化はつらく厳しい戦いになってしまい、難しい割に10倍も速くならないので、大体ここで引き返すことになる。だが、本気で最高に速くしたいならここからが本番でもあるのだ。一つ一つをジリジリ1.5倍くらいずつ速くして最終的に全体を1.4倍くらい速くする、みたいなのを2回根性でやり通せば、「2倍速くなりました!」と宣伝できる。とはいえ、最初のコードに例えばキャッシュヒット率やSIMDなどの特殊命令や冗長な演算などの考慮漏れがなければ、1.5倍高速化するのは不可能なのだが。

まあ、今回は十分速くなったので、これ以上はやらない。なのでここでとりあえずこの話は終えることができる。設定ファイルの読み込みが大抵のプロジェクトでホットスポットではないのは、その意味ではありがたいことかもしれない。

*1:唯一ユーザーが困りそうなのは前まで通ってたやつが落ちるようになったみたいなのだが、そういうのは前通してたのがバグだったことになるので諦めて欲しい。とはいえ今回はそういう変更ではない。

*2:金言は既にある程度正しいことが知られているので、当てはまる部分に言及してもしょうがない。あと本題にはちゃんと金言が当てはまるというのもある

std::alignを動的メモリ確保と一緒に使う

はい。C++17を使っている人はnewが全部やってくれるようになったので不要な話です。C++17以前のコードのため。

Introduction

アライメントとは、ざっくり言うとメモリ上の位置調整であり、普段は気にしなくていい(コンパイラmallocがちゃんとやってくれる)。だが、SIMDなどの特殊用途や、キャッシュ効率の最適化などの際は考慮する必要がある。SIMDは、例えば一度に256bit分の長さの値(double x4とか、std::int32_t x8とか)を足し算するとかいう感じの命令だが、この256bitの値(普通は何かの配列)がメモリ上で32byte境界にぴったり乗っている(メモリアドレスが32の倍数になっている)と読み書きが楽だったりする。あるいは、CPUキャッシュは大抵64byte境界から64byteを一単位として持ってくるのだが、キャッシュされて欲しいデータが一つのキャッシュラインに収まっていれば効率がよくなる。"false sharing"などでググってみると面白い話が出てくる。

値がスタックに乗る場合、スタックメモリはコンパイラの管理下にあるので、そのアドレスはコンパイラが制御できる。だが、ヒープアロケーションを伴う場合、普通のmallocnewにはアライメント情報を渡せないので(newに関してはC++17以前の話)、適切なアライメントになっている保証はない。これを解決する方法は大きく分けて3つある。コンパイラを新しくしてC++17を使うか、posix_memalign_mm_allocintel製CPUのみ)、_aligned_allocWindows)などの環境依存な関数を使うか、多めにメモリを確保してアライメントが満たされる領域を使うかだ。

std::alignはこの第三の選択肢を実装するためにもってこいだ。これは、あるメモリ領域の中に、指定したアライメントを満たす指定したサイズの領域があれば、その領域の先頭を返す。

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

今回の記事は、これを使えばposix_memalign_aligned_allocを使い分けなくていいじゃん! と思ったものの意外と難しかったという記録だ。できたっぽいけど。

Method

まず、void* malloc(size_t)の変種みたいなものvoid* aligned_alloc(align, size)を作る以上、void aligned_free(void*)できる必要がある。これがあとで結構色々な制限に繋がってくる。

基本的なアイデアを少し詰めていこう。まず、大きめの領域を確保して、そこからアライメントがあっている箇所を抜き出してくる。常に満たされるアライメントをmin_alignとすると、要求されたアライメントがreq_alignとして、req_align - min_alignだけ広く取れば、必ずアラインされている(req_alignの倍数になるメモリアドレスから始まる)領域があることになる。例えば、常に16byteアラインが満たされる時、64byteアライメントを満たすには、48byteだけ広く取っておけば大丈夫だ。

,_____________allocated size _________,
|             ,____ required size ____,
|             |                       |
| padding ... | aligned memory region |
^ min_align   ^ req_align

ここまではいい。だが、正しくメモリを解放しようと思うと、これでは足りない。というのも、アライメントされた領域のポインタを返すと、もともと確保されたメモリ領域がどこまでだったかわからなくなるからだ。最初のアライメントはmin_alignの保証しかないことを考えると、何バイトにアラインされているかがわかっても、絞り込めないケースが出てくる(例えばreq_align = 64bytemin_align = 16byteだったとすると、パディングのサイズは16, 32, 48の3通りあり得、先頭ポインタからはその情報は消えている)。つまり、パディングの量か、本来の先頭へのポインタを覚えておく必要があるのだ。

ではどちらを覚えておくべきだろうか。パディングの量だとメモリ消費が少なくなりそうだが、よく考えると要求されるアライメントのサイズが不明なので結局ptrdiff_tを使うことになりそうだ。するとポインタを覚えておくのと特に変わりない。また、パディングに「パディングのサイズ」自体を含めるかどうかが曖昧で、こういうミスが許されないところで使うのは怖い(いや、プログラムは大抵どこでもミスは許されないのだが)。となると、本来の先頭を指すvoid*を覚えておくのが楽だろう。

,_____________allocated size _________,
|             ,____ required size ____,
|             |                       |
| padding ... | aligned memory region |
^
+-- ここを覚えておきたい

ではどこにそのvoid*を置くか。今後使う領域に置くわけには行かないので(早晩書き換えられてしまうだろう)、選択肢は概ね3つだ。真の先頭、アラインされた領域の直前、アラインされた領域の直後だ。

|void*| padding ... | aligned memory region |
| padding ... |void*| aligned memory region |
      | padding ... | aligned memory region |void*|

だが、実際にfreeする時のことを考えると、取り得る選択肢は1つに絞られる。上の図では真ん中にある、「アラインされた領域の直前」しかない。まず、最初の選択肢は、先に述べてある「パディングのサイズが不明」という問題を解決できない。なので、そもそもこのvoid*を取りに行けない。よって却下。次に、最後の選択肢、最後尾に置くというものだが、往々にして人はインデックスを溢れさせてこの値が書き換えられるだろうから、ではなく、aligned_free(void*)は領域のサイズを受け取らないので、aligned memory regionがどれくらいの長さかわからず、結局これも取りに行けないのだ。

というわけで、aligned_free(void*)からvoid*sizeof(void*)バイトだけ一つ後ろにずらすだけで必ず取りに行ける、真ん中の選択肢が唯一生き残る。その場合、aligned_freeの実装は以下のようになるだろう。まず、受け取ったvoid*void**だと思い込み、一つ後ろを見る(これでvoid*一つぶん後ろに動く)。そこの内容を取ってきて、std::freeに渡す。

void aligned_free(void* ptr)
{
    if(ptr)
    {
        std::free(*(reinterpret_cast<void**>(ptr) - 1));
        return;
    }
}

ここまでの議論があれば、わりかしシンプルな実装に落ち着いたように思えるが、いきなりこれを見ると驚くかもしれない。

というわけでメモリ解放ができるようになったので、アロケーションの方をちゃんと実装しよう。アライメントされた領域を確保するには、パディングと、freeするためのvoid*分だけ大きな領域を取らなければならない。さて、min_alignだが、mallocany scalar typeに対して正しくアラインされたものを返すらしいので、void*のためのアライメントは保証される。以降もvoid*は使うので、これを保証されたアライメントの値ということにしよう。

void* aligned_alloc(std::size_t req_align, std::size_t size)
{
    constexpr std::size_t min_align = alignof(void*);
    const auto offset = req_align - min_align + sizeof(void*);
    void* const ptr = std::malloc(size + offset);
    // ...
}

この領域からstd::alignを使ってアライメント要求に合う領域を取り出すのだが、その前に、最低限void*を格納できる領域を先に確保しておく必要がある。

void* aligned_alloc(std::size_t req_align, std::size_t size)
{
    // ...
    void* const ptr = std::malloc(size + offset);
    // void* 1つ分後ろにずらす
    void* aligned_ptr = reinterpret_cast<void*>(
        reinterpret_cast<void**>(ptr) + 1);
    std::size_t space = size + offset - sizeof(void*);
    // アライメント要求に合う領域を探す
    std::align(req_align, size, aligned_ptr, space);
    // ...
}

この時点でaligned_ptrの値が欲していた領域の先頭を指すポインタになっている。なので、忘れずその一つ前に本当の先頭ポインタをメモしておいて、完了だ。

void* aligned_alloc(std::size_t req_align, std::size_t size)
{
    // ...
    void* const ptr = std::malloc(size + offset);
    // ...
    std::align(req_align, size, aligned_ptr, space);
    // aligned_ptrの直前にメモしておく
    *(reinterpret_cast<void**>(aligned_ptr) - 1) = ptr;
    return aligned_ptr;
}

こっちはまあ、想像通りの複雑さになった。加えて、本当はここに「req_alignmin_alignと同じかそれより小さい場合」の対応を入れる必要がある。それは普通にmalloc使えよって話で、assertすればよくね? と思ったが、using aligned_vector = std::vector<T, aligned_allocator<T, alignof(T)>>;みたいな使い方する時は普通にあり得るんだよな……。

Result

valgrindでリークチェックとかしたけど大丈夫そうでした、まる。

Conclusion

std::alignstd::mallocaligned_alloc作ろうとすると超絶面倒くさいから、環境依存の関数をマクロで使いわけましょう。