現在、ジャंक社には独自のカスタム赤外線（IR）プロトコルが用意されています。

皆様、朗報です！Jank に新しいカスタム中間表現（IR）が生まれ、これを用いて JVM と競合するレベルでの最適化を実現しています。今日はその詳細についても掘り下げますが、まずは今年通じ GitHub スポンサー様および Clojurists Together 様による多大なるご支援に心より感謝申し上げます。皆様が本当に大きな力を与えてくださっています。まだ全件収入を確保して Jank の開発を専業で行う資金の調達方法を探っておりましたが、もし今後ご寄附をご検討いただいている方には、ちょうど良い機会です！

中間表現（IR）とは何ですか？

コンパイラは、ターゲット CPU の命令セットに収まるよりも抽象度の高い命令集合としてプログラムを表現することがよくあります。これにはいくつかの利点があります：

• まず第一に、プログラムは後に x86_64 や arm64 など様々な CPU アーキテクチャへ「ローアード（下位化）」できるよう表現することができます。中間表現は通常 CPU アーキテクチャよりも上位レベルであるため、一般的に移植性が高くなります。
• 次に、IR は特定の最適化を容易にするようにプログラムを表現するよう設計することが可能です。例えば、単一静的代入（SSA）形式などが挙げられます。
• 最後に、IR 設計師は自分が表現しようとするセマンティクスに合わせて IR の抽象レベルを選択することができます。これにより、IR をより汎用的にしたり、特定の言語向けに特化させたりできます。

JVM のバイトコード、CLR の共通中間言語（CIL）、GCC の GIMPLE、LLVM の IR などが一般的で人気のある IR の例です。いくつかのコンパイラは、コンパイル過程でプログラムを複数の IR を通します。

カスタム IR の理由

歴史的に Jank は最適化を行うコンパイラーではありませんでした。ほぼ全ての最適化作業を C++ または LLVM IR から生成したものに基づいて LLVM に委譲してきました。しかしながら、LLVM IR は Clojure と比較して非常に低レベルで動作し、Clojure の変数（vars）、一時的データ（transients）、永続データ構造、 Ленивая シーケンス（lazy sequences）などの概念を備えていません。Clojure の動的性質は多形性（polymorphism）と間接参照（indirection）に大きく依存していますが、そのせいで Jank から生成された LLVM IR を処理する際、LLVM には最適化の機会が非常に少ないという状況でした。

これまでの Jank における最適化作業は、ランタイム自体やコンパイラ自身を最適化する助けとなりましたが、コンパイラによってコンパイルされるコードについてはそれほどではありませんでした。過去 2 ヶ月間、私はこの状況を根本から変えようと尽力しました。

私が望んだのは、Clojure のセマンティクスに即して動作する IR でした。これは LLVM IR よりもはるかに上位レベルで、さらに JVM のバイトコードよりもはるかに上位レベルのものとなります。私は汎用仮想マシン（VM）やコンパイラプラットフォームを構築しているわけではないため、IR を異なる言語のために汎用化する必要はありません。Jank の IR を Jank に特化させさえすれば十分であり、これにより最適化のパワーをさらに高めております。私が知る限り、このステップを踏んだクロージアの方言はまだ存在していません。

カスタム IR の詳細

Jank の IR に関する参考文献は、こちらにある Jank ブックスに記述されています。当方は現在の時点において Jank の IR の安定性を一切保証できないため、このドキュメントは主に Jank そのものの開発に関わる方々が対象となっております。しかし、ここではその一部を引用し、Jank の IR の概要を理解するのに役立てたいと思います。

まずは簡単な Clojure 関数を見てみましょう：

(defn greet [name]
  (if (= "jeaye" name)
    (println "Are you me?!")
    (println (str "Hello, " name "!"))))

Jank の IR は C++ データ構造としてメモリ上に保存されますが、デバッグやテストのために Clojure データへレンダリング可能です。これは完全なシリアライゼーションではなく、IR から Jank コンパイラーへ元に戻すことは Clang AST 内の内部データがあるため不可能です。この関数に対応する Jank IR モジュールを見てみましょう：

{:name user_greet_82687
 :lifted-vars {clojure_core_SLASH_str_82694 clojure.core/str
               clojure_core_SLASH_println_82691 clojure.core/println
               clojure_core_SLASH__EQ__82689 clojure.core/=}
 :lifted-constants {const_82693 "!"
                    const_82692 "Hello, "
                    const_82690 "Are you me?!"
                    const_82688 "jeaye"}
 :functions [{:name user_greet_82687_1
              :blocks [{:name entry
                        :instructions [{:name greet :op :parameter :type "jank::runtime::object_ref"}
                                       {:name name :op :parameter :type "jank::runtime::object_ref"}
                                       {:name v3 :op :literal :value "jeaye" :type "jank::runtime::obj::persistent_string_ref"}
                                       {:name v4 :op :var-deref :var clojure_core_SLASH__EQ__82689 :type "jank::runtime::object_ref"}
                                       {:name v5 :op :dynamic-call :fn v4 :args [v3 name] :type "jank::runtime::object_ref"}
                                       {:name v7 :op :truthy :value v5 :type "bool"}
                                       {:name v8 :op :branch :condition v7 :then if0 :else else1 :merge nil :shadow nil :type "void"}]}
                       {:name if0
                        :instructions [{:name v9 :op :literal :value "Are you me?!" :type "jank::runtime::obj::persistent_string_ref"}
                                       {:name v10 :op :var-deref :var clojure_core_SLASH_println_82691 :type "jank::runtime::object_ref"}
                                       {:name v11 :op :dynamic-call :fn v10 :args [v9] :type "jank::runtime::object_ref"}
                                       {:name v12 :op :ret :value v11 :type "jank::runtime::object_ref"}]}
                       {:name else1
                        :instructions [{:name v13 :op :literal :value "Hello, " :type "jank::runtime::obj::persistent_string_ref"}
                                       {:name v14 :op :literal :value "!" :type "jank::runtime::obj::persistent_string_ref"}
                                       {:name v15 :op :var-deref :var clojure_core_SLASH_str_82694 :type "jank::runtime::object_ref"}
                                       {:name v16 :op :dynamic-call :fn v15 :args [v13 name v14] :type "jank::runtime::object_ref"}
                                       {:name v17 :op :var-deref :var clojure_core_SLASH_println_82691 :type "jank::runtime::object_ref"}
                                       {:name v18 :op :dynamic-call :fn v17 :args [v16] :type "jank::runtime::object_ref"}
                                       {:name v19 :op :ret :value v18 :type "jank::runtime::object_ref"}]}]}]}

Jank の IR は SSA ベースであり、これは各名前は一度だけ代入されることを意味します。これにより、最適化のカテゴリ全体を扱うことが格段に容易になります。また、Jank の IR は制御依存グラフ（CFG）として表現されており、これは 1 つ以上の基本ブロックで構成され、各ブロックには正確に 1 つの終結命令（分岐、ジャンプ、スロー、リターンなど）を持っています。

IR モジュールから確認できるように、Jank は変数と定数の昇格（lifting）を扱い、Clojure のセマンティクスレベルの命令（変数の参照解除、関数の呼び出しなど）を持っています。この IR から生成された C++ コードを見てみましょう：

extern "C" jank::runtime::object_ref
user_greet_19_1(jank::runtime::object_ref const greet, jank::runtime::object_ref name)
{
  auto const v3(const_33);
  auto const v4(clojure_core_SLASH__EQ__34->deref());
  auto const v5(jank::runtime::dynamic_call(v4, v3, name));
  auto const v7(jank::runtime::truthy(v5));
  if(v7)
  {
    auto const v9(const_35);
    auto const v10(clojure_core_SLASH_println_36->deref());
    auto const v11(jank::runtime::dynamic_call(v10, v9));
    return v11;
  }
  else
  {
    auto const v13(const_37);
    auto const v14(const_38);
    auto const v15(clojure_core_SLASH_str_39->deref());
    auto const v16(jank::runtime::dynamic_call(v15, v13, name, v14));
    auto const v17(clojure_core_SLASH_println_36->deref());
    auto const v18(jank::runtime::dynamic_call(v17, v16));
    return v18;
  }
}

C++ コードと IR を比較すると、その関連性がすぐにわかります。C++ の変数は IR の変名に合わせて命名されています。変数の参照解除は単に

->deref()

への呼び出しとなり、動的呼び出しは単に

jank::runtime::dynamic_call

となります。これは意図的な設計です。

IR の最適化

IR を設計・実装し、C++ コード生成を IR からではなく Jank の AST からではなく IR から生成するように再構築する作業を含めて、これには約 6 ヶ月かかりました。現時点ではまだ IR 上で最適化パスを実行していませんが、それを開始するための全てが必要準備されています。私は可能な限り多くの機能を拡張するよりも、新しい IR パイプラインをマージすることを優先したいと考えており、すでにメインブランチから枝分かれしている状態が 6 ヶ月間も長いためです。今では IR がマージされたので、その後は一つのベンチマークを取り上げ、必要に応じて最適化を繰り返して満足するまで、あるいはそれ以上最適化できないまで進めていくつもりです。いくつかの最適化は IR そのものに直接関わりますが、そうでないものもあります。

この IR の技術的な開発の詳細に興味のある方は、IR を開発した際に行われた様々な Twitch ストリームからのいくつかの動画を Jank TV YouTube チャンネルでご覧いただけます。これらの動画は実装の詳細な部分まで踏み込んでいます。

導入された新しい IR に対し、まず最初のベンチマークである再帰的フィボナッチ数の計算を取り上げます。

イントロダクション

着手する前に、Jank のメーリングリストへの購読をご検討ください。これが Jank のリリース、Jank 関連の講演、ワークショップなどで最新情報を確実に把握するための最良の方法となります。非常にアクセス数が少ないためです。

再帰的フィボナッチ数の最適化

この回における最初のベンチマークは再帰的なフィボナッチ数の実装です。コード自体はわずか 5 行です。我々の目標は、JVM の Clojure と同等かそれ以上の速度を達成することですが、その分努力が必要です。

(defn fibonacci [n]
  (if (<= n 1)
    n
    (+ (fibonacci (- n 1))
       (fibonacci (- n 2)))))

これは最適化すべきベンチマークとして微不足っているように見えるかもしれません。なぜこれが現実世界のアプリケーションを代表するのか疑問に思う方もおられるでしょう。実際には、このベンチマークはコンパイラーとランタイムの本質的な側面をいくつかカバーしています：

• 多形性の算術および関係性述語。 基本的に全てのプログラムは数値を処理し、それを迅速に行う必要があります。
• 再帰。 特にリスプ系言語では、多くの一般的なアルゴリズムは再帰的であるためです。これらのパターンを効率的に扱う能力は重要です。
• ガベージコレクションの生成と収集。 廃車回収車の訪問頻度は週に一度かもしれませんが、できるだけゴミを生成すべきではありません。
• 一般的に、ランタイムが立ち退くこと。 フィボナッチ数の計算を試みている場合、プロフィールにはフィボナッチ数以外の内容が現れてはいけません。

最適化を進める中で、この投稿全体を通してこれら 4 つのカテゴリを検討し、我々の行う各最適化をどのようにカテゴライズできるかを考え込んでください。

ベースラインのフィボナッチ数の時間測定

ベースラインベンチマーク数を得るため Clojure JVM を使用し、その後 Jank でそれらの数字を超えようとする予定であります。当投稿内の全ての数字は、NixOS上で OpenJDK 21 を動作させる AMD Ryzen Threadripper 2950Xを搭載した 5 年前の x86_64 デスクトップで測定されました。この投稿において「JVM」と言う場合は OpenJDK 21 を指します。

❯ clojure -Sdeps '{:deps {criterium/criterium {:mvn/version "0.4.6"}}}'
Clojure 1.12.4
user=> (require '[criterium.core :refer [quick-bench]])
nil
user=> (defn fibonacci [n]
       (if (<= n 1)
         n
         (+ (fibonacci (- n 1))
            (fibonacci (- n 2)))))
#'user/fibonacci
user=> (quick-bench (fibonacci 35))

Clojure は

(fibonacci 35)

を計算するのに約 200 ミリ秒かかります。これが我々のベースラインです！

注記： Lein REPL に注意してください。もともと Clojure のベンチマークを Lein REPL で実施しており、全く異なる結果が得られたことに留意してください。当システムでは Clojure は 200 ミリ秒ではなく約 2,800 ミリ秒という極めて遅い値を示しました。いくつかの注記によれば、Lein REPL が一部の JVM 最適化を無効化しており、ここでのキー要素となっているらしいです。これは Kyle Cesare 様への指摘に感謝いたします。

初期 Jank の時間測定

数週間前に Jank のメインブランチから始め、同じフィボナッチ定義を使用しますが、Criterium は利用できません（これが JVM ライブラリであるため）。代わりに、Jank 自体と共に配布されている専用のベンチマークライブラリーを使用します。

(defn fibonacci [n]
  (if (<= n 1)
    n
    (+ (fibonacci (- n 1))
       (fibonacci (- n 2)))))

(require '[jank.perf])
(jank.perf/benchmark {:label "fib"} (fibonacci 35))

最適化有効および急ぎコンパイルで実行すると、初期の数字を得ることができます：

❯ jank run -O3 --eagerness eager fib.jank

Jank は 5,522 ミリ秒です。それは……高速ではありません。特に JVM の 200 ミリ秒と比較すれば。

算術のインライン化（Inlining）

始めに、Clojure が数学呼び出しをインライン化しており、Jank はかつてそれにハック的な解決策を持っていましたが廃止されていたことを知っています。これを正しく行う時が来ました。Clojure はメタデータ経由でインライン化を行っており、他のネームスペースの関数の本体は入手できません。これは Clojure 特有の問題ではなく、C および C++ の仕組みと全く同じです。翻訳ユニットを跨ぐ C または C++ への呼び出しは、リンク時最適化（LTO）を使用しない限りインライン化されません。他のオプションとして、定義をヘッダーファイルに移動し関数を

inline

とマークして、各翻訳ユニットが自身のコピーを持つようにすることも可能です。Clojure では、変数のメタデータに変数からどこでも読み取れるインライン化情報を追加することにより、同じ効果「関数をヘッダーに置く」を達成できます。

例を見てみましょう：

(defn
  ^{:inline (fn [l r]
              (list 'cpp/jank.runtime.max l r))
    :inline-arities #{2}}
  max
  ([x] x)
  ([l r] (cpp/jank.runtime.max l r))
  ([l r & args]
   (let [res (cpp/jank.runtime.max l r)]
     (if (empty? args) res (recur res (first args) (next args))))))

ここでは

clojure.core/max

に、2 つのキーを持つメタデータが含まれており、

:inline

および

:inline-arities

です。後者はインライン化するアリティ（関数の引数数）の集合です。ここでは

[l r]

のアリティのみが対象です。

:inline

の値は、そのアリティに対する本体を取得するための実際の関数です。Max の場合は、C++ への呼び出し

jank::runtime::max

をインライン化したいだけです。後で Clang にそれをさらにインライン化するよう指示します。

インライン化は解析時に行われ、IR パスでは行いません。変数を通した関数呼び出しを見つけると、その変数のメタデータをチェックし、存在する場合は対応する

:inline

関数を呼び出します。これをマクロ展開の姉妹とみなすことができます。

この種類のインライン化には大きな利点があります：

• まず第一に、

  clojure.core/max

  の変数インターナリングと参照解除を削除できます。
• 次に、各 Clojure 関数は箱詰めパラメータが必要ですが、ネイティブ値で作業している場合、Max を呼ぶ前にそれらを箱詰めする必要はありません。
• 第三に、Max が未箱詰めのネイティブ値を返す場合、関数から戻すためにそれを箱詰めする必要はありません。これにより、箱詰め回避と型情報のより良い伝播が可能になります。

Jank のアナライザーへのインライン化サポートを追加し、すべての算術関数のメタデータを更新した後、新しいベンチマーク結果を確認できます。これは 5,522 ミリ秒から 2,309 ミリ秒へと低下させます。大きな勝利で始まるのが幸いです。

IR の余分な命令の排除

次に、フィボナッチ関数の IR を見てみましょう。現在は Jank 関数の IR を調べることを非常に楽しんでおり、コンパイラーが見るコードに関する素晴らしいビューを提供されるためです：

{:name user_fibonacci_82580
 :lifted-vars {}
 :lifted-constants {const_82598 2
                    const_82597 1}
 :functions [{:name user_fibonacci_82580_1
              :blocks [{:name entry
                        :instructions [{:name fibonacci :op :parameter :type "jank::runtime::object_ref"}
                                       {:name n :op :parameter :type "jank::runtime::object_ref"}
                                       {:name v3 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
                                       {:name v4 :op :cpp/call :value "jank::runtime::lte" :args [n v3] :type "bool"}
                                       {:name v5 :op :cpp/into-object :value v4 :type "jank::runtime::object_ref"}
                                       {:name v7 :op :truthy :value v5 :type "bool"}
                                       {:name v8 :op :branch :condition v7 :then if0 :else else1 :merge nil :shadow nil :type "void"}]}
                       {:name if0
                        :instructions [{:name v9 :op :ret :value n :type "jank::runtime::object_ref"}]}
                       {:name else1
                        :instructions [{:name v10 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
                                       {:name v11 :op :cpp/call :value "jank::runtime::sub" :args [n v10] :type "jank::runtime::object_ref"}
                                       {:name v12 :op :named-recursion :fn fibonacci :args [v11] :type "jank::runtime::object_ref"}
                                       {:name v13 :op :literal :value 2 :type "jank::runtime::obj::integer_ref"}
                                       {:name v14 :op :cpp/call :value "jank::runtime::sub" :args [n v13] :type "jank::runtime::object_ref"}
                                       {:name v15 :op :named-recursion :fn fibonacci :args [v14] :type "jank::runtime::object_ref"}
                                       {:name v16 :op :cpp/call :value "jank::runtime::add" :args [v12 v15] :type "jank::runtime::object_ref"}
                                       {:name v17 :op :ret :value v16 :type "jank::runtime::object_ref"}]}]}]}

関数には 3 つのブロックがあります。エントリーブロックから始め、パラメータ

n

とリテラル

1

を取得し、インライン化された

cpp/call

命令として戻り値を持つブール型の bool を返す

<=

チェックを行います：

• {:name n :op :parameter :type "jank::runtime::object_ref"}

• {:name v3 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}

• {:name v4 :op :cpp/call :value "jank::runtime::lte" :args [n v3] :type "bool"}

次に、そのブール値を箱詰めされたオブジェクトに変換し、ブランチを行うために真理値としてチェックします：

• {:name v5 :op :cpp/into-object :value v4 :type "jank::runtime::object_ref"}

• {:name v7 :op :truthy :value v5 :type "bool"}

• {:name v8 :op :branch :condition v7 :then if0 :else else1 :merge nil :shadow nil :type "void"}

これは最適化して排除できます。なぜなら我々の

<=

チェックの結果 (

v4

) はすでにブール値であるからです。オブジェクトに変換したのは再びブール値にできるようにするためです。理想的には、ブランチ条件は単に

v4

であればよいはずです。

それを最適化する前に、IR の確認を完了しましょう。我々は

if0

に分岐して結果を返すか、再帰を行う必要がある

else1

に分岐します。

else1

ブランチは 3 つのステップで発生します：

1. (- n 1)

   で再帰呼び出し。

   • {:name v10 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}

   • {:name v11 :op :cpp/call :value "jank::runtime::sub" :args [n v10] :type "jank::runtime::object_ref"}

   • {:name v12 :op :named-recursion :fn fibonacci :args [v11] :type "jank::runtime::object_ref"}

2. (- n 2)

   で再帰呼び出し。

   • {:name v13 :op :literal :value 2 :type "jank::runtime::obj::integer_ref"}

   • {:name v14 :op :cpp/call :value "jank::runtime::sub" :args [n v13] :type "jank::runtime::object_ref"}

   • {:name v15 :op :named-recursion :fn fibonacci :args [v14] :type "jank::runtime::object_ref"}

3. その合計を返す。

   • {:name v16 :op :cpp/call :value "jank::runtime::add" :args [v12 v15] :type "jank::runtime::object_ref"}

   • {:name v17 :op :ret :value v16 :type "jank::runtime::object_ref"}

これが全てです！それでは、余分な

:cpp/into-object

および

:truthy

命令を排除し、IR 生成にブール値を直接使用するだけのサポートを追加しましょう。結果として、2,309 ミリ秒から 2,247 ミリ秒へと低下します。全体的な規模の観点からは非常に限定的ですが、IR に余分な作業がなくなったのは幸いです。2 つのリテラル命令

1

を昇格させて 1 つだけにすることも可能ですが、それはパフォーマンスに影響しないため今は保留します。

最適化された IR:

{:name entry
 :instructions [{:name fibonacci :op :parameter :type "jank::runtime::object_ref"}
                {:name n :op :parameter :type "jank::runtime::object_ref"}
                {:name v3 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
                {:name v4 :op :cpp/call :value "jank::runtime::lte" :args [n v3] :type "bool"}
                {:name v6 :op :branch :condition v4 :then if0 :else else1 :merge nil :shadow nil :type "void"}]}
{:name if0
 :instructions [{:name v7 :op :ret :value n :type "jank::runtime::object_ref"}]}
{:name else1
 :instructions [{:name v8 :op :literal :value 1 :type "jank::runtime::obj::integer_ref"}
                {:name v9 :op :cpp/call :value "jank::runtime::sub" :args [n v8] :type "jank::runtime::object_ref"}
                {:name v10 :op :named-recursion :fn fibonacci :args [v9] :type "jank::runtime::object_ref"}
                {:name v11 :op :literal :value 2 :type "jank::runtime::obj::integer_ref"}
                {:name v12 :op :cpp/call :value "jank::runtime::sub" :args [n v11] :type "jank::runtime::object_ref"}
                {:name v13 :op :named-recursion :fn fibonacci :args [v12] :type "jank::runtime::object_ref"}
                {:name v14 :op :cpp/call :value "jank::runtime::add" :args [v10 v13] :type "jank::runtime::object_ref"}
                {:name v15 :op :ret :value v14 :type "jank::runtime::object_ref"}]}

Nil 使用法の最適化

この時点で IR は良好で、他に計画した最適化はありませんので、炎上グラフ（flamegraph）を見て時間が行き渡っている場所を確認しましょう。算術とフィボナッチへの呼び出しを見ることを期待していますが、興味深いことに

jank_nil

および

jank_const_nil

に多くの時間が費やされていることがわかります。Clojure の方言として、我々は非常に頻繁に Nil をアクセスしており、Nil チェックが必要で、Nil への初期化が必要であり、多数の式が Nil 評価するためです。しかし、それはプロフィールに表示されるべきではありません！表示されるのは、Jank が現在その Nil 値を非常に詳細な理由のために関数の背後に置いているためです。C++ は翻訳ユニット間のグローバルへの初期化順序を保証せず、かつ Jank AOT コンパイルされる全ての翻訳ユニットはグローバル（昇格定数）で満たされており、これらの値が Nil に初期化されたいとします。Nil が別の翻訳ユニットで Jank ランタイムの一部として定義されている場合、それが初期化する前に使用を試みる可能性があります。我々はそれを

jank_nil

と呼ばれる関数の背後に置くことで回避してきましたが、明らかにこれは大きなパフォーマンスコストをもたらしました。

Jank の箱詰めポインタ型は

nullptr

で初期化することを許容しておらず、それは無効な値だからです。Jank は Clojure では Nil の参照解除は良好に定義されていますが C++ では

nullptr

の参照解除は未定義の行動であるため、Nil と

nullptr

を区別します。我々は単にそれをできません。しかし、私たちが AOT コンパイルされたコードのために生成するグローバルについてデフォルト構造を気にしておらず、モジュールが読み込まれた際に後で再初期化するためです。箱詰めポインタ型のカスタムコンストラクターを追加し、実際に

nullptr

に初期化するようにすると良いでしょう。その後、Nil を関数ではなくグローバル値として維持できます。

これにより、2,247 ミリ秒から 1,400 ミリ秒へと低下します！これは大きな勝利です！これはランタイムがベンチマークの邪魔をすることなので、これで整理できて満足です。それでも Clojure JVM の 5 倍遅いため、さらにいくつか大きな塊を切断する必要があります。

なぜ add/sub が遅いのか？

上記に埋め込まれた炎上グラフの残りを確認すると、予期される疑わしい箇所を見つけます。つまり、

add

および

sub

です。これらの関数の最も遅い部分は、炎上グラフによれば、新しい数字の GC 割り当てです。加算または減算から出る全ての整数結果は新しい動的割り当てです。現時点では、ほぼ全時間を数字の割り当てに費やしています。

何故未箱詰めの数字を使用しないのか疑問に思うかもしれません。あるいは「型ヒントを追加する！Clojure はそれをサポートしている！」とお考えかもしれません。しかし、これはこのベンチマークのポイントを見逃しています。このベンチマークは具体的にコンパイラーとランタイムに挑戦するために書かれています。再び Clojure コードを見てみましょう：

(defn fibonacci [n]
  (if (<= n 1)
    n
    (+ (fibonacci (- n 1))
       (fibonacci (- n 2)))))

ここで、

n

の型は単に型消去されたオブジェクトになります。Clojure JVM ではそれは Java Object です。Jank では

jank::runtime::object_ref

です。いずれにせよ、中にどのような種類のオブジェクトがあるのか分かりません。

(- n 1)

および

(- n 2)

を行った場合でも、

n

の型をまだ知りません。浮動小数点数である可能性があります。整数である可能性があります。比率である可能性があります。大きな十進数または大きな整数である可能性があります。算術をサポートしていない何かである可能性もあります。したがって、

n

上の算術を処理するために多形のダンス全体を行う必要があります。幸運にも、1 および 2 の型を知っているので、それのために最適化できますが、これを箱詰めのいずれかに十分なほどではありません。

+

呼び出しについても同様です。fibonacci の戻り値の型も分かりません。我々は

n

の型を知らないか、あるいは

+

の結果で両方の入力から fibonacci の戻り値を返すもので、これもまだ型が分からないため、ここに静的に何もしられません。これがこのベンチマークを困難にする鍵となる側面です。現在、JVM は我々よりもはるかにうまくこれを処理しています。

ポインタタグ化

これを是正するため、整数のための動的割り当てを完全に回避しましょう。言語ランタイムはそれを正確に行うためにいくつかのよく知られたトリックを使用しており、Jank はまだこれらを使用していません。最も簡単なトリックから始め、後のベンチマーク投稿でより複雑な設計に構築していきます。

64 ビットシステムでは、ポインタの下の 3 ビットが実質的に未使用であることを知っていましたか？これはポインタが 64 ビット機械ワードに整列されているためです。例えば、整合されたポインタはアドレス 0, 8, 16, 24 など存在します。ただし、整合されたポインタは 8 バイト（64 ビット）で割り切れないアドレスには存在しません。ポインタの下の 3 ビット、

000

は 1 の位（最低ビット）、2 の位（中間ビット）、4 の位（最高ビット）用です。全てのビットがオン

111

であれば、値は 7 (4 + 2 + 1) です。さらに一つ足すと、8 になり、下の 3 つのビットは再び 0 に戻ります。

これは素晴らしい知識で、これによりポインタに非常に簡単に追加情報を埋め込むことができます。例えば、最低ビットを 1 に設定すると、ポインタが実際にはポインタではないことを伝えられます。代わりに、エンコードされた整数です。次に、他の 63 ビットを使用して実際の整数値を格納できます。これで、我々の整数が高すぎて管理できない値を保存する必要がない限り、動的割り当てを行わずに直書きで保存できます！全 64 ビットが必要な場合は、通常の割り当てを行い、通常ポインタ（下の 3 つのビットは全て 0）を取得するだけです。

視覚化のために、通常の 64 ビットポインタは以下のようになります。最も高い 61 ビットはポインタデータに使用され、下の 3 つのビットは 0 です：

pppppppp pppppppp pppppppp pppppppp pppppppp pppppppp pppppppp ppppp000

エンコードされた整数は以下のようになります。最低ビットは 1 で、残りは整数データに予約されています。実際の 63 ビット整数を取得するには、全体を右に一度シフトするだけです：

xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxx1

我々のフィボナッチベンチマークにおいて、実際にはほぼ全てのベンチマークおよび現実世界のアプリケーションにおいて、これは整数のための全動的割り当てを効果的に排除します。これが数字にどう影響するか見てみましょう。

63 ビット整数のためにタグ付けされたポインタを使用する場合、Jank は 1,400 ミリ秒から 282 ミリ秒へと変化します。私が言ったように、我々は基本的に全時間を割り当てに費やしていました。さらに良いのは、これで Clojure の 200 ミリ秒の範囲内に近づいたことです。

激しいインライン化

最新の変更のある炎上グラフを見て、余分な脂肪をどのように切り取るかを検討しましょう。ここで見るべき理想は、単にフィボナッチだけであり、何もありません。何かが重要ならすべてがインライン化されているはずです。代わりに、

jank::runtime::add

、

jank::runtime::sub

、および

jank::runtime::lte

が見えます。これはそれらの呼び出しが Clang によってインライン化されていないことを意味します。Clang に算術関数を常にインライン化するよう指示しましょう。C++ add, sub などの関数にいくつかの属性を置くことで可能です。現代的な C++ シンタックスはこれを容易にします：

template <typename L, typename R>
[[gnu::always_inline, gnu::flatten, gnu::hot]]
auto add(L const l, R const r)
{ ... }

算術は何でも高速でありたいものであり、数値計算よりもインライン化すべき良いものではありません。今から再試行しましょう。幸運にも、安堵の息をしながら、これは Jank を 282 ミリ秒から 114 ミリ秒へと低下させます。Clojure JVM のほぼ 2 倍速いです！さらに良いのは、5,522 ミリ秒から 114 ミリ秒という同じ仕事を効果的に行うことです。

以前、チェーンソー彫刻を行う芸術家のインタビューを見たことがあります。インタビュアーは大きな丸太から熊のようなものを作るのにどうアプローチするかを尋ねました。彼は「ただ熊に見えないものをすべて取り去るだけです」と答えました。それほど役に立つ回答ではありませんが、最適化とは非常に類似しています。プロフィールを行い時間をどのように費やしているかを検討する際、最も本質的なタスクを行っていません全ての時間を単に排除する必要があります。一般的には、何が本質的なタスクかを突き止め、その後他の全てを行わない方法を突き止めるということです。

次に何があるか

一つのベンチマークを下にし、まだ多くの残っています。次に、数年前に Clojure で書いたレイトレーサーを見直し、新しい IR と最適化されたランタイムを活用して Jank をどれほど速く押せるか見てみましょう。この投稿および最初のベンチマークは単に始まりです。私は今後数ヶ月間、より大小様々なベンチマークを扱って、Jank が実用的な観点で適度に速いことを保証します。これは全て Jank のベータリリースに向けて構築されています。

JVM とネイティブに関する注記

初めて Jank を使用する方々の多くは「なぜ Jank は遅いのですか？C++ で書かれていないのでしょうか？」と言うようなことになります。まず、Jank は未最適化だから遅いです。ここで見られるように、Jank はこのマイクロベンチマークで JVM と競合でき、私は将来の投稿で大きなベンチマークでもそれを示すつもりです。第二に、何もうたがって C++ で書かれているかご存知ですか？JVM です。Jank は確かに小さな JVM で、いくつかの重要な違いがあります。

• JVM は単に JIT コンパイラーだけでなく、JIT オプティマイザもあります。JVM はどの関数が呼び出され、どれほど頻繁でどのような値で使用されるかに基づいて、実行時に適応的にインタープロシージャー最適化を行います。これは驚くべきエンジニアリングです。
• ネイティブの世界では、現在 JIT 最適化はありません。存在する可能性もありますが、LLVM は実装しておらず、主要な C および C++ コンパイラーにもありません。さらに、ネイティブエコシステム全体はそれに設計されていませんが、JVM スペースでは本当に当然のことです。これは JVM プログラムを使うほど速くなることを意味しますが、ある点までです。しかしながら、もし Jank が Clojure より速ければ、それは早く始まり、それを維持したためです。
• 最後に、Jank が C++ で書かれているからといって、Clojure のセマンティクスから逃げることはできません。Clojure は動的型付け、ガベージコレクション、多形性で完全に動いています。コンパイラーおよびランタイムのために使用される言語に関わらず、これらのセマンティクスは真のクロージア方言にとって維持する必要があります。我々はこのベンチマークを実際の実用的な C++ に書き直しても、Clojure との間には競争はありません。C++ が単純に勝利し、それは静的型付けを使用し、素数の算術を使用し、実走時間がほとんどなく、特に Clang は優れた AOT 最適化を持っています。Clojure コードの型ヒントを加えても同様です。信じていないなら試してください。私が書いている時にしました。:)

ご参加をご希望ですか？

• Slack または Discord のコミュニティに参加する
• デザイン議論に参加するか、GitHub でチケットを取得する
• スポンサーになることを検討している
• Jank を専業で開発するために私を雇う！