概要
シンプルで高速な純粋関数型プログラミング言語 Fix を作っています。
AtCoder に続き、yukicoder にもFixを導入していただいたので、何か紹介記事を書こうかなー、と思っていたところで、
ある言語が「C++より速い」と話題になっていたので、便乗して、yukicoder のいくつかの問題を使って Fix と C++ の性能を比較してみます。
注：AtCoder のジャッジに入っているのは Fix 1.1.0 で、今回、yukicoder に入ったのは Fix 1.6.0 です。この間に大幅な性能改善が入っており、本記事で紹介している性能は、AtCoder のジャッジでは出せない可能性が高いです。AtCoder の次の言語アップデートが始まるのを楽しみにしています。
性能比較
私が Fix で解いた yukicoder の問題のいくつかについて、同じ解き方を C++ に書き直して、速さを比べてみました。
C++ については、入出力を scanf / printf で書いたものと、getchar_unlocked / putchar_unlocked で書いたもの（高速入出力）の2通りを用意しました。
括弧の中は対 Fix 比です（大きいほど、Fixのほうが速い）。
| 問題 | Fix | C++ | C++（高速入出力） |
|---|---|---|---|
| No.1170 Never Want to Walk | 16.0 ms 17 ms |
30.2 ms（1.89） 38 ms（2.24） |
13.4 ms（0.84） 17 ms（1.00） |
|
No.1170 Never Want to Walk （Fixの出力を一気にやる版） |
11.9 ms 14 ms |
30.2 ms（2.54） 38 ms（2.71） |
13.4 ms（1.13） 17 ms（1.21） |
|
No.1955 Not Prime （数値で結合版） |
33.4 ms 24 ms |
36.2 ms（1.08） 30 ms（1.25） |
34.2 ms（1.02） 29 ms（1.21） |
|
No.1955 Not Prime （文字列結合版） |
71.1 ms 59 ms |
67.6 ms（0.95） 54 ms（0.92） |
65.4 ms（0.92） 50 ms（0.85） |
| No.1054 Union add query | 139.5 ms 128 ms |
218.3 ms（1.56） 229 ms（1.79） |
153.7 ms（1.10） 189 ms（1.48） |
| No.877 Range ReLU Query | 50.3 ms 59 ms |
72.7 ms（1.45） 96 ms（1.63） |
53.6 ms（1.07） 74 ms（1.25） |
|
No.567 コンプリート （配列の配列版） |
1390.0 ms 674 ms |
1258.0 ms（0.91） 547 ms（0.81） |
1257.6 ms（0.90） 547 ms（0.81） |
|
No.567 コンプリート （2つの配列版） |
1172.7 ms 402 ms |
1258.0 ms（1.07） 547 ms（1.36） |
1257.6 ms（1.07） 547 ms（1.36） |
- セル内の1行目：ジャッジで一番時間がかかったテストケースをダウンロードし、私のPCで30回計測して中央値をとったものです。測定環境は注釈1に記載しています。
- セル内の2行目：yukicoder のジャッジで1度だけ計測したものです。
- 私の「コンプリート」の解答は、想定解より効率の悪い解法でしたが、改善せずそのままにしています。また、私のPCとジャッジで大幅に時間が違いますが、原因はわかりません。
- Fix から C++ への翻訳はAIに行わせました。できるだけ同じ解き方にしてありますが、ライブラリは Fix 側が cp-library、C++ 側が ACL なので、ライブラリの実装の差も含みます。
十分に C++ と張り合うことができる速度が出ていると思います！
特に、「No.567 コンプリート」のように、パッと思いついた解法が多少効率が悪くても、ACできる、という水準にいるのは嬉しいことです。
さて、以下では、このベンチマークで見えた Fix の弱み、C++ との違いについて書いていきます。
コンパイル時間とバイナリサイズ
Fix の目標は、
- 抽象度の高い、高水準言語でありつつ、
- コンパイラがすごく頑張って、高速に動作するバイナリを生成すること
です。
したがって、割り切りとして、最適化に十分な時間をかけ、インライン化や特殊化を積極的に行うようにしています。
速くコンパイルしたいときは、最適化レベルを落としてください（-O basic など）、というスタイルです。
そのため、コンパイル時間とバイナリサイズはどちらも C++ より大きいです。
| 問題 | コンパイル時間（Fix） | コンパイル時間（C++） | バイナリサイズ（Fix） | バイナリサイズ（C++） |
|---|---|---|---|---|
| No.1170 Never Want to Walk | 1.15 秒 | 0.40 秒 | 22.1 KB | 16.6 KB |
| No.1955 Not Prime | 1.17 秒 | 0.68 秒 | 34.4 KB | 21.8 KB |
| No.1054 Union add query | 1.18 秒 | 0.37 秒 | 25.6 KB | 16.7 KB |
| No.877 Range ReLU Query | 1.22 秒 | 0.69 秒 | 26.4 KB | 26.1 KB |
| No.567 コンプリート | 1.18 秒 | 0.29 秒 | 38.4 KB | 16.6 KB |
- 私の PC での計測です。yukicoder のジャッジと同様に1コアに固定して計測しました。
- yukicoder ではコンパイルにもっと時間がかかっています。かなり待たされます。原因不明です。
コンパイル時間については、性能を損なわない範囲で、今後改善を行っていくつもりです。
ライブラリ：Short String Optimization がない
「Not Prime」において、2つの数字の10進表示を結合して素数かどうかを調べるときに、素朴に「数字を文字列化して、結合して、数値化する」という実装にした場合、C++ に負けてしまいます。
| 問題 | Fix | C++ | C++（高速入出力） |
|---|---|---|---|
|
No.1955 Not Prime （文字列結合版） |
71.1 ms 59 ms |
67.6 ms（0.95） 54 ms（0.92） |
65.4 ms（0.92） 50 ms（0.85） |
C++ の std::string には SSO (Short String Optimization) という工夫があります。これは、短い文字列のデータは構造体に埋め込んでしまうことで、ヒープメモリ確保を避けるものです。
本問のように「短い文字列」がたくさん出てくるケースで有利に働きますが、Fix の Std::String には SSO は実装されていません。
文字列操作を避け「a を 10^n 倍して b を加える」にすると、Fix が追いつきます。
| 問題 | Fix | C++ | C++（高速入出力） |
|---|---|---|---|
|
No.1955 Not Prime （数値で結合版） |
33.4 ms 24 ms |
36.2 ms（1.08） 30 ms（1.25） |
34.2 ms（1.02） 29 ms（1.21） |
ライブラリ：標準出力のたびにヒープ確保が発生する
「Never Want to Walk」で、C++（高速入出力）に Fix が負けた原因です。
Fix で数値を標準出力するときは「42.to_string.println」あるいは「"{}".printfln((42,))」としますが2、どちらもその場で使うヒープメモリを確保します。
前者は 42.to_string の結果が文字列なのでデータがヒープになります。後者については、printfln 側がバッファを確保し、そこに42の10進表示を書き込みます。
バッファを1つ共有して、printfln の呼び出しのたびに再利用するようにすれば解決する可能性があります。
答えを配列xsにあつめておいて、printfln のフォーマット機能で改行をはさむようにする（"{}".printfln((xs.to_iter.joined_with("\n"),))）と、printfln のバッファ確保は1回ですみます。
これなら C++ より速くなります。
| 問題 | Fix | C++ | C++（高速入出力） |
|---|---|---|---|
|
No.1170 Never Want to Walk （Fixの出力を一気にやる版） |
11.9 ms 14 ms |
30.2 ms（2.54） 38 ms（2.71） |
13.4 ms（1.13） 17 ms（1.21） |
最適化：uniquenessチェックを消しきれないことがある
「コンプリート（配列の配列版）」で Fix が負けた原因です。
Fix の値はすべて（意味としては）immutableです。
そのため、DPにありがちな、dp[i][j].imod(f)（fは値を値に変換する関数、imod はそれを配列要素に適用する関数）のような処理を行うときは
更新しようとしている配列への参照は1つか？
-> （Yesなら）値を直接書き換えてもバレないので、in-placeに要素を書き換える。
-> （Noなら）配列をコピーしてから要素を更新する。
という判定（uniquenessチェック）をする必要があります。
このコストを低減するために、コンパイル時の静的解析で「ここでは必ずuniqueだ」とわかる場合には、uniquenessチェックのコードを生成しないようにしています。
ところが、配列の配列（Array (Array F64)）の場合、内側の配列については静的解析が uniqueness を証明できず、uniquenessチェックのコードが生成されてしまっています。
「外側の（長さ2の）配列」を避けて、nxt と cur という2つの配列を扱うようにすると、この問題が解消し、Fix が勝ちます。
| 問題 | Fix | C++ | C++（高速入出力） |
|---|---|---|---|
|
No.567 コンプリート （2つの配列版） |
1172.7 ms 402 ms |
1258.0 ms（1.07） 547 ms（1.36） |
1257.6 ms（1.07） 547 ms（1.36） |
インストール方法
Fix に興味をもった方はぜひ使ってみてください。