2022.06.25

エフェクト解析による動的言語最適化 Part.1

門脇宗平

こんにちは。ATL客員研究員の門脇です。普段は Julia Computing というボストンにある会社のソフトウェアエンジニアとしてプログラミング言語Julia のコンパイラの開発に携わっています。

今回のブログ記事では、次のJuliaの最新版であるv1.8から追加される新しいコンパイラ機能 エフェクト解析 についてご紹介したいと思います。

エフェクト解析とは、メモリへの書き込みなどプログラムが持つエフェクト(computational effects) を解析する技術のことで、一般的にはエフェクトを解析することでリソースの安全な管理などを行うための発展的なコンパイルタイムチェックを行います。そうしたエフェクトシステムおよび静的解析はいくつかの静的型付けの言語では既に実用化されていて、例えば Haskell ではエフェクトシステムがライブラリレベルで実装されていたり、 Koka という実験的な言語ではエフェクトシステムが言語のコア機能として提供されています。¹

一方でJuliaのような動的言語においてはエフェクト解析の利用はまだ一般的ではありません。今回我々Juliaコンパイラ開発チームは、エフェクト解析をコンパイルタイムチェックのためではなく、もっぱら定数畳み込み最適化のために利用することで、 Juliaのコンパイル時間およびランタイムパフォーマンスを同時に大幅に改善することに成功しました。²

おそらく実用言語の範囲では初の例だと思われるこのエフェクト解析を用いた動的言語の最適化手法について、今回は以下の流れで2つの記事に分けて解説を行いたいと思います:

Part.1
- まずJuliaの設計思想とコンパイラの基本的な原理を説明し、 Juliaコンパイラが直面しているトレードオフについて解説します。
- 次にエフェクト解析を利用してそのトレードオフを改善するアイディアを簡単に説明します。
Part.2
- 次回の記事では、まず具体的にどのようなエフェクトシステムが必要なのかを考察し、その後今回実装したエフェクト解析のアルゴリズムを説明します。
- 次にエフェクト解析に関してJuliaプログラマが利用可能なアノテーションを紹介します。
- 最後にこのエフェクト解析のさらなる応用可能性について考察したいと思います。

今回の記事はPart.1で、Part.2は来月公開する予定です。

!!! warning 以下のご紹介するコードは、2022年06月25日時点でのnightlyバージョン Version 1.9.0-DEV.848 (2022-06-24) で実行しています。今回取り上げているエフェクト解析およびコンパイラ最適化は現在も細かな修正が加えられており、他のバージョンでは同様の実験結果が得られない場合があります。

Juliaコンパイラにおけるトレードオフ

JuliaはPythonやRubyなどと同じ動的言語に類されるプログラミング言語ですが、同時にC言語やRustなどの静的言語と同じく強力なコンパイラを備えてもいます。

Juliaの実行プロセスにおいては、各関数の型付けは必ずしも定義時に決定される必要はなく、その関数が実行時に呼ばれたタイミングでコンパイルが開始され最適化されます。このJuliaの実行方式は一般にジャストインタイムコンパイル(JIT – Just-In-Time compilation) と呼ばれますが、実はJuliaにおける"JIT"は、コンパイラ技術における一般的な"JIT"とはかなり異なった概念です。つまりJulia処理系はプログラムの実行過程をプロファイリングした結果に基づいてプログラムを最適化しているの ではなく、 実行時直前に 行われる静的な解析によりプログラムを最適化しています。その意味でJuliaプログラムは、コンパイルの開始が実行時に遅延されているという点を除けば、C言語やRustなどの静的型付け言語が行っているアヘッドオブタイムコンパイル(AoT – Ahead-of-Time compilation) と基本的に同じ仕組みでコンパイルされている言えます。³

Julia処理系がわざわざコンパイルの開始を実行時直前にまで遅らせている理由は、究極的にはプログラムのジェネリクス(Polymorphism) を高めるためです。つまり、Juliaプログラムの型はプログラムが書かれたときに決定されている必要がなく、そのことによってプログラムが持ち得る限りのジェネリクスを獲得しているのです。

Juliaはこのようにしてダック・タイピング(duck-typing) されたプログラムを実行時直前にコンパイルすることで、動的言語の持つ簡潔な書き味と、静的言語で得られるようなハイパフォーマンス、そして他の言語では得難いほど高度なジェネリックプログラミングを達成しようとしているわけです。

抽象解釈

Juliaコンパイラが行う静的解析・最適化の中でも、とりわけ抽象解釈と呼ばれるステップは、 Juliaプログラムの型を解決し⁴、その後のさまざまな最適化ステップのベースとなる情報を導出するため非常に重要です。

抽象解釈とは、プログラミング言語の近似的なセマンティクスを用いてプログラムを解析することにより、そのプログラムが実行時に取りうる振る舞いを導出するための静的解析フレームワークです。 …と言っても分かりにくいので、ここでは「プログラムを型レベルで仮想的に実行することで、そのプログラムが実行時に取りうる型を解析する技術」くらいに理解してください。「型レベル」⁵という実際のプログラム実行よりも抽象的なドメインでプログラム実行を考えることにより、どのようなプログラムに対しても ——たとえ実際の実行では終了しない、あるいは異常終了してしまうプログラムでも—— 安全かつ解析の終了が保証された形でプログラムを解析することができるのです。

たとえば、以下のようなプログラムの実行を考えてみます。

julia> function kernel1(n, x)
           out = 0
           while n > 0
               out += sum(sincos(x))
               n -= 1
           end
           return out
       end
kernel1 (generic function with 1 method)
julia> n, x = 42, 1.0;
julia> kernel1(n, x)
58.034478208393544

julia> function kernel1(n, x)

out = 0

while n > 0

out += sum(sincos(x))

n -= 1

end

return out

end

kernel1 (generic function with 1 method)

julia> n, x = 42, 1.0;

julia> kernel1(n, x)

58.034478208393544

このとき、kernel1(n, x) という関数呼び出しはJulia言語処理系によりコンパイルされ最適化されています。 @code_typed マクロを使って、Juliaコンパイラがどのような抽象解釈を行ったのかを確認してみましょう:

julia> @code_typed optimize=false kernel1(n, x)
CodeInfo(
1 ─      (n@_5 = n@_2)::Int64
└──      (out = 0)::Core.Const(0)
2 ┄ %3 = (n@_5 > 0)::Bool
└──      goto #4 if not %3
3 ─ %5 = out::Union{Float64, Int64}
│   %6 = Main.sincos(x)::Tuple{Float64, Float64}
│   %7 = Main.sum(%6)::Float64
│        (out = %5 + %7)::Float64
│        (n@_5 = n@_5 - 1)::Int64
└──      goto #2
4 ─      return out
) => Union{Float64, Int64}

julia> @code_typed optimize=false kernel1(n, x)

CodeInfo(

1 ─ (n@_5 = n@_2)::Int64

└── (out = 0)::Core.Const(0)

2 ┄ %3 = (n@_5 > 0)::Bool

└── goto #4 if not %3

3 ─ %5 = out::Union{Float64, Int64}

│ %6 = Main.sincos(x)::Tuple{Float64, Float64}

│ %7 = Main.sum(%6)::Float64

│ (out = %5 + %7)::Float64

│ (n@_5 = n@_5 - 1)::Int64

└── goto #2

4 ─ return out

) => Union{Float64, Int64}

コンパイラが kernel1(n, x) という関数呼び出しにおける引数型情報 n::Int, x::Float64 を使って kernel1 の実行を「型レベル」で解析することで、kernel1 に含まれる変数や関数呼び出しの型を推論しています。例えば、変数 out は n == 1 のときは out = 0::Int という型を取りますが、それ以外のときは (out = %5 + %7)::Float64 という別の型を取ります。 %5 = out::Union{Float64, Int64} という表示は、 Juliaコンパイラの抽象解釈が、 kernel1 の実行時に out が取りうるこれら２つの可能性を Union{Float64, Int64} という型で近似していることを示しています。

Juliaコンパイラは、このように抽象解釈により推論されたプログラムの型情報を用いて

実行時に呼び出されうるメソッドを解決したり(dispatch devirtualization)
そのメソッドの中身を展開したり(インライン展開)
オブジェクトのアロケーションをスカラー値で置き換えたり(SROA – Scalar-Replacement-Of-Aggregates)

などなど各種の最適化を行っているのです。

さて、この抽象解釈という技術それ自体は別に真新しい技術ではなく、 1970年代後半に Patrick Cousot らによって基礎となる理論が提唱されて以降、実にさまざまな応用が試みられてきた古典的な静的解析技術です。その一方で、すでに完成され確立された技術かと言えるのかというとそんなことはなく、その他多くのコンパイラ技術と同様に、抽象解釈も現実のプログラミング言語に対して実装するのはやはり難しく、加えて解析の 精度とレイテンシのトレードオフ と向き合わなくてはなりません。抽象解釈というジェネラルなフレームワークを現実のプログラミング言語に対してどのように上手く適用し実装するのか、プログラミング言語の研究・開発の現場で今まさに試行錯誤され、発展し続けている技術と言えるでしょう。

言語機能のコアとして抽象解釈を利用しているJuliaにおいては、特に優れた抽象解釈の実装が求められます。最先端の科学計算の要求水準を満たすランタイムパフォーマンスを達成しつつ、インタラクティブな研究開発を支える動的言語としてのコンパイルタイムパフォーマンスを実現するべく、 Julia言語の開発者はこのトレードオフをさらに改善するための試行錯誤を日々試みています。

以降の章では、我々が日々格闘しているこのトレードオフについてもう少し詳しく掘り下げてみます。

関数境界を跨いだ抽象解釈

Juliaコンパイラにおける抽象解釈を理解する上でおそらく最も重要なのは、それが 関数境界を跨いで(inter-proceduralに) 行われているということです。例えば先ほどの @code_typed optimize=false kernel1(n, x) の出力を見ると、 sincos(x)::Tuple{Float64,Float64} や (n@_5 = n@_5 - 1)::Int などの kernel1 内で呼び出されている他の関数の返り値の型も推論されているのが確認できます。このことは、Juliaコンパイラは kernel1(n::Int, x::Float64) という関数呼び出しをコンパイルする上で、 その関数呼び出しに必要な他の関数まで同時に解析し、関数境界を跨いでコンパイルを行っているということを意味しています。 Juliaにおいては sincos や - といった基本的な算術関数もJulia自身で実装されており、型付けが実行時直前に解決されるという意味で、コンパイラからは sincos も - も kernel1 のようなユーザが定義した関数と本質的に同様な見え方をしています。そのため kernel1(n::Int, x::Float64) という呼び出しを最適化する上で、 kernel1 を解析するだけではなく sincos や -、 sincos や - の内部で呼ばれている他の関数… というように再帰的に抽象解釈を走らせて一気にコンパイルしているのです。そのため、例えば sincos の代わりに自前の mysincos 関数を定義しても同様の最適化を得ることができます:

julia> mysincos(x) = (sin(x), cos(x))
mysincos (generic function with 1 method)
julia> function kernel1′(n, x)
           out = 0
           while n > 0
               out += sum(mysincos(x))
               n -= 1
           end
           return out
       end
kernel1′ (generic function with 1 method)
julia> @code_typed optimize=false kernel1′(n, x)
CodeInfo(
1 ─      (n@_5 = n@_2)::Int64
└──      (out = 0)::Core.Const(0)
2 ┄ %3 = (n@_5 > 0)::Bool
└──      goto #4 if not %3
3 ─ %5 = out::Union{Float64, Int64}
│   %6 = Main.mysincos(x)::Tuple{Float64, Float64}
│   %7 = Main.sum(%6)::Float64
│        (out = %5 + %7)::Float64
│        (n@_5 = n@_5 - 1)::Int64
└──      goto #2
4 ─      return out
) => Union{Float64, Int64}

julia> mysincos(x) = (sin(x), cos(x))

mysincos (generic function with 1 method)

julia> function kernel1′(n, x)

out = 0

while n > 0

out += sum(mysincos(x))

n -= 1

end

return out

end

kernel1′ (generic function with 1 method)

julia> @code_typed optimize=false kernel1′(n, x)

CodeInfo(

1 ─ (n@_5 = n@_2)::Int64

└── (out = 0)::Core.Const(0)

2 ┄ %3 = (n@_5 > 0)::Bool

└── goto #4 if not %3

3 ─ %5 = out::Union{Float64, Int64}

│ %6 = Main.mysincos(x)::Tuple{Float64, Float64}

│ %7 = Main.sum(%6)::Float64

│ (out = %5 + %7)::Float64

│ (n@_5 = n@_5 - 1)::Int64

└── goto #2

4 ─ return out

) => Union{Float64, Int64}

こうした関数境界を跨いだ最適化を、コンパイラの文脈では IPO – Inter-Procedural Optimization と呼びます。一般に、１つの関数に対するローカルな最適化に比較して、IPOを適切に実装することは容易ではありません。実行され得るコールグラフ全体を最適化しようとするIPOでは、ランタイムのパフォーマンス(最適化の精度)とコンパイルタイムのパフォーマンス(最適化のレイテンシ) のトレードオフに直面しやすいからです。⁶

Julia設計思想においては特に優れたIPOの実装が重要です。なぜならば、コンパイルのエントリポイントとなる関数呼び出しが受け取った引数の情報を、 inter-proceduralな抽象解釈によりサブルーチンの関数へと次々と伝播させ、実行され得るコールグラフ(call graph)全体を最適化することで初めて、型が明示的に制限されていないジェネリックなコードが組み合わさって構成されたプログラムを、静的型付け言語と同等のレベルで最適化することができるようになるからです。

定数伝播による抽象解釈の精度向上

さて、ここまで抽象解釈をざっくりと「型レベルでプログラムを解析しプログラムの型付けを推論するもの」として説明してきましたが、実は抽象解釈を行うときに何も「型レベル」でプログラムの実行を近似する必然性はありません。抽象解釈が使用する「近似的なセマンティクス」のドメインとしては、対象のプログラミング言語の実行に与えられているセマンティクスを健全に抽象化している限り、どのようなドメインでも使うことができるのです。一般に、ドメインを実際のセマンティクスに近づけてより具体的にすればするほど(抽象化の度合いを下げて抽象解釈の精度を高めるほど)、解析の複雑性が高まり解析時間が肥大化するため、抽象解釈にどの程度具体的なドメインを使うかという選択は抽象解釈の精度とレイテンシのトレードオフを大きく左右します。

実際のところ、Juliaコンパイラは「型レベル」よりも少し具体的なドメインを使って抽象解釈を行っています。プログラム中の変数や関数呼び出しを、それらが実行時に取りうる型に加えて、さまざまな「付随情報」を与えて抽象化しているのです。この「付随情報」にも色々な種類があるのですが、その中でも特に重要なのが定数情報です。つまり、変数や関数呼び出しが実行時にある1つの定数値を取ると分かっている場合を、 Const と呼ばれる特殊な抽象状態で表現しています。例えば先ほどの @code_typed optimize=false kernel1(n, x) の出力にも Const は現れており、 (out = 0)::Core.Const(0) という表示は while ループの前において変数 out は必ず定数値 0 を取るため、「型レベル」の情報 Int で抽象化せず、その定数値そのもので表現していることを意味しています。一方で while ループの内部においては out は必ずしも定数値 0 を取るとは限らないため、 %5 = out::Union{Float64, Int64} という表示においては「型レベル」の情報 Union{Int, Float64} に抽象化されているのです。

このように静的解析においてプログラムの状態を定数値を用いて表現することを、定数畳み込みと呼びます。プログラムを定数値を用いて単純化することにより、本来はランタイムに行われる計算をコンパイル時に行ってしまったり、到達されないコード領域の削除(デッドコード削除) を行ったりできるのです。先ほど確認したように、Juliaコンパイラは抽象解釈時に定数値を伝播させることで、定数畳み込みを行っています。この方式の面白いところは、Juliaコンパイラの抽象解釈が関数を跨いで行われるために、その定数畳み込みも関数境界を跨いで行われるということです。つまりJuliaコンパイラの抽象解釈は、型レベルの情報だけでなく定数情報をもサブルーチンの関数へ伝播させることで非常に強力なIPOを実現しているのです。この抽象解釈におけるinter-proceduralな定数情報の伝播を 定数伝播(constant-propagation) と呼びます。ここでは kernel1′ を第2引数 x を定数値 1.0 で呼び出す kernel2 を定義して定数伝播の様子を確認してみましょう。 Cthulhu.jl というサードパーティパッケージを利用します:

julia> function kernel2(n)
           return kernel1′(n, 1.0)
       end
kernel2 (generic function with 1 method)
julia> using Cthulhu
julia> # おまじない： 説明のため、今回紹介するエフェクト解析を一時無効化する
       function Core.Compiler.concrete_eval_eligible(interp::Cthulhu.CthulhuInterpreter,
           @nospecialize(f), result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)
           return false # disable concrete evaluation for now
       end
julia> @descend optimize=false kernel2(n)
kernel2(n) in Main at none:1
1 ─ %1 = Main.kernel1′(n, 1.0)::Union{Float64, Int64}
└──      return %1
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
Advanced: dump [P]arams cache.
 • %1  = < constprop > kernel1′(::Int64,::Core.Const(1.0))::Union{Float64, Int64}
   ↩
kernel1′(n, x) in Main at none:1
1 ─      (n@_5 = n@_2)::Int64
└──      (out = 0)::Core.Const(0)
2 ┄ %3 = (n@_5 > 0)::Bool
└──      goto #4 if not %3
3 ─ %5 = out::Union{Float64, Int64}
│   %6 = Main.mysincos(x)::Core.Const((0.8414709848078965, 0.5403023058681398))
│   %7 = Main.sum(%6)::Core.Const(1.3817732906760363)
│        (out = %5 + %7)::Float64
│        (n@_5 = n@_5 - 1)::Int64
└──      goto #2
4 ─      return out
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
Advanced: dump [P]arams cache.
 • %3  = >(::Int64,::Int64)::Bool
   %6  = < constprop > mysincos(::Core.Const(1.0))::Core.Const((0.8414709848078965, 0.5403023058681398))
   %7  = < constprop > sum(::Core.Const((0.8414709848078965, 0.5403023058681398)))::Core.Const(1.3817732906760363)
   %8  = call → +(::Union{Float64, Int64},::Float64)::Float64
   %9  = -(::Int64,::Int64)::Int64
   ↩

julia> function kernel2(n)

return kernel1′(n, 1.0)

end

kernel2 (generic function with 1 method)

julia> using Cthulhu

julia> # おまじない：説明のため、今回紹介するエフェクト解析を一時無効化する

function Core.Compiler.concrete_eval_eligible(interp::Cthulhu.CthulhuInterpreter,

@nospecialize(f), result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)

return false # disable concrete evaluation for now

end

julia> @descend optimize=false kernel2(n)

kernel2(n) in Main at none:1

1 ─ %1 = Main.kernel1′(n, 1.0)::Union{Float64, Int64}

└── return %1

Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.

Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.

Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code

Actions: [E]dit source code, [R]evise and redisplay

Advanced: dump [P]arams cache.

• %1 = < constprop > kernel1′(::Int64,::Core.Const(1.0))::Union{Float64, Int64}

↩

kernel1′(n, x) in Main at none:1

1 ─ (n@_5 = n@_2)::Int64

└── (out = 0)::Core.Const(0)

2 ┄ %3 = (n@_5 > 0)::Bool

└── goto #4 if not %3

3 ─ %5 = out::Union{Float64, Int64}

│ %6 = Main.mysincos(x)::Core.Const((0.8414709848078965, 0.5403023058681398))

│ %7 = Main.sum(%6)::Core.Const(1.3817732906760363)

│ (out = %5 + %7)::Float64

│ (n@_5 = n@_5 - 1)::Int64

└── goto #2

4 ─ return out

Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.

Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.

Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code

Actions: [E]dit source code, [R]evise and redisplay

Advanced: dump [P]arams cache.

• %3 = >(::Int64,::Int64)::Bool

%6 = < constprop > mysincos(::Core.Const(1.0))::Core.Const((0.8414709848078965, 0.5403023058681398))

%7 = < constprop > sum(::Core.Const((0.8414709848078965, 0.5403023058681398)))::Core.Const(1.3817732906760363)

%8 = call → +(::Union{Float64, Int64},::Float64)::Float64

%9 = -(::Int64,::Int64)::Int64

↩

kernel2 内における kernel1′ の呼び出しにおいて第2引数 x が Const(1.0) で表現されており、その情報がそのまま kernel1′ の抽象解釈に伝播されてる様子が確認できるかと思います。ここで注目したいのが、 %6 = Main.mysincos(x)::Core.Const((0.8414709848078965, 0.5403023058681398)) と %7 = Main.sum(%6)::Core.Const(1.3817732906760363) において、 mysincos / sum 呼び出しの返り値も定数値で表現されているということです。このことはJuliaコンパイラが x::Core.Const(1.0) という情報を mysincos と sum から構成されるコールグラフ全体に行き渡らせ、本来ならば実行時に行われる sum(mysincos(x)) の計算をまるっと定数値で単純化できたことを意味しています。定数伝播を行わない場合、sum(mysincos(x)) の計算が実行時に n 回だけ繰り返されてしまうことを考慮すると、こうした定数伝播によるIPOがいかに強力か理解できるのではないかと思います。⁷

定数伝播とレイテンシ

一方で、定数情報は抽象解釈の精度を高める代わりに解析にかかる時間を肥大化させてしまいます。 Juliaコンパイラが行う抽象解釈のようなinter-proceduralな解析においては、ある関数呼び出しに対して解析が終わった時にその情報をキャッシュし、その後の解析で同じ呼び出しがあったときにそのキャッシュ情報を再利用することで解析時間を大幅に短縮することができますが、定数情報を用いた解析結果は多くの場合で再利用することができないのです。例えば kernel1 の呼び出しを kernel1(::Int, ::Float64) というふうに「型レベル」まで抽象化して解析した結果は、 kernel1(42, 2.0), kernel1(0, 0.0), kernel1(rand(Int)::Int, rand(Float64)::Float64) のどの呼び出しをコンパイルする時にも使うことができますが、 kernel1(::Int, ::Core.Const(1.0)) というふうに定数情報まで含めて解析した結果は、上のどの呼び出しをコンパイルする時にも使えません。

以上の理由から、Juliaの抽象解釈においては、闇雲に定数情報を伝播させるのはレイテンシ上の懸念から望ましくありません。そのため、Juliaの抽象解釈の実装では、まず関数呼び出しを「型レベル」情報のみで解析し結果をキャッシュした後に、その解析結果から定数伝播による最適化の恩恵を得られそうかをヒューリスティック的に判断し、制限的に定数伝播を行なっています。そのヒューリスティックには、「『型レベル』での解析結果がインライン展開可能な程度にシンプルかどうか」という判断基準が使われています⁸が、多くの場合で期待通りに動作する一方、定数伝播によるレイテンシへの影響を直接考慮している訳ではないため、定数情報が多くのシンプルな関数呼び出しにおいて利用可能な場合に過剰に定数伝播が起こりレイテンシに重大な影響を与えてしまう潜在的な可能性があります。

ここでは先ほどの kernel2(n::Int) のコンパイル時に「型レベル」情報のみの解析と定数情報ありの解析それぞれにおいて、どの程度のプログラムが解析されたかを確認してみましょう:

julia> function profile_absint((interp, mi))
           cnt, locs = 0, Set{Tuple{Symbol,Int32}}()
           cnt_with_const, locs_with_const = 0, Set{Tuple{Symbol,Int32}}()
           for (mi, inferred) in interp.unopt
               for lin in inferred.src.linetable
                   if isa(mi, Core.MethodInstance)
                       # non-constant inference
                       cnt += 1
                       push!(locs, (lin.file, lin.line))
                   else
                       # constant inference
                       cnt_with_const += 1
                       push!(locs_with_const, (lin.file, lin.line))
                   end
               end
           end
           function print_profile_info((cnt, locs))
               linecnt = length(locs)
               filecnt = length(unique(first.(locs)))
               println("    analyzed $cnt calls / $linecnt lines (in $filecnt files)")
           end
           println("Profiling results on: ", mi)
           println("  [non-constant absint]")
           print_profile_info((cnt, locs))
           println("  [constant absint]")
           print_profile_info((cnt_with_const, locs_with_const))
       end
profile_absint (generic function with 1 method)
julia> profile_absint(Cthulhu.@interp kernel1′(n, x))
Profiling results on: MethodInstance for kernel1′(::Int64, ::Float64)
  [non-constant absint]
    analyzed 604 calls / 389 lines (in 22 files)
  [constant absint]
    analyzed 383 calls / 78 lines (in 13 files)
julia> profile_absint(Cthulhu.@interp kernel2(n))
Profiling results on: MethodInstance for kernel2(::Int64)
  [non-constant absint]
    analyzed 605 calls / 389 lines (in 22 files)
  [constant absint]
    analyzed 719 calls / 232 lines (in 16 files)

julia> function profile_absint((interp, mi))

cnt, locs = 0, Set{Tuple{Symbol,Int32}}()

cnt_with_const, locs_with_const = 0, Set{Tuple{Symbol,Int32}}()

for (mi, inferred) in interp.unopt

for lin in inferred.src.linetable

if isa(mi, Core.MethodInstance)

# non-constant inference

cnt += 1

push!(locs, (lin.file, lin.line))

else

# constant inference

cnt_with_const += 1

push!(locs_with_const, (lin.file, lin.line))

end

function print_profile_info((cnt, locs))

linecnt = length(locs)

filecnt = length(unique(first.(locs)))

println(" analyzed $cnt calls / $linecnt lines (in $filecnt files)")

end

println("Profiling results on: ", mi)

println(" [non-constant absint]")

print_profile_info((cnt, locs))

println(" [constant absint]")

print_profile_info((cnt_with_const, locs_with_const))

end

profile_absint (generic function with 1 method)

julia> profile_absint(Cthulhu.@interp kernel1′(n, x))

Profiling results on: MethodInstance for kernel1′(::Int64, ::Float64)

[non-constant absint]

analyzed 604 calls / 389 lines (in 22 files)

[constant absint]

analyzed 383 calls / 78 lines (in 13 files)

julia> profile_absint(Cthulhu.@interp kernel2(n))

Profiling results on: MethodInstance for kernel2(::Int64)

[non-constant absint]

analyzed 605 calls / 389 lines (in 22 files)

[constant absint]

analyzed 719 calls / 232 lines (in 16 files)

期待通り「型レベル」情報のみでの解析(non-constant absint)においては、 kernel1′(n, x) の抽象解釈が604個の関数呼び出しを解析しているのに対して、 kernel1′ の呼び出しを含む kernel2(n) の抽象解釈では kernel1′ の分だけ1つ多い605個の関数呼び出しを解析を行っています。その一方で、定数情報ありでの解析(constant absint)では大きく違い生じているのが確認できると思います。 kernel2(n) の呼び出しで利用可能な x::Core.Const(1.0) という定数情報を kernel1′ のコールグラフ全体に行き渡らせるためには、 719-383 == 336 個もの関数呼び出しを定数情報ありで再解析しなくてはならないのです。

利用可能な定数情報が増えれば当然、定数伝播される呼び出しは増大し、その分だけ解析時間がかかってしまいます:

julia> function kernel3(n)
           kernel1′(n, 1.0), kernel1′(n, 10.0)
       end
kernel3 (generic function with 1 method)
julia> profile_absint(Cthulhu.@interp kernel3(n))
Profiling results on: MethodInstance for kernel3(::Int64)
  [non-constant absint]
    analyzed 605 calls / 389 lines (in 22 files)
  [constant absint]
    analyzed 1114 calls / 268 lines (in 17 files)
julia> using BenchmarkTools
julia> @benchmark Cthulhu.@interp kernel1′(n, x)
BenchmarkTools.Trial: 106 samples with 1 evaluation.
 Range (min … max):  39.912 ms … 68.155 ms  ┊ GC (min … max):  0.00% … 12.90%
 Time  (median):     48.977 ms              ┊ GC (median):    14.32%
 Time  (mean ± σ):   47.258 ms ±  5.013 ms  ┊ GC (mean ± σ):  10.50% ±  8.26%
  ▂ ▂  █                      ▄▂  █▂▆▆▄▂▆
  ██████▆▆███▄▆▁▁▄▁▁▁▁▁▁▁▁▁▄▄▄██▆▆███████▄▆▁▆▆▁▄▁▁▁▁▁▁▁▁▁▁▁▁▆ ▄
  39.9 ms         Histogram: frequency by time        57.6 ms <
 Memory estimate: 26.03 MiB, allocs estimate: 384784.
julia> @benchmark Cthulhu.@interp kernel2(n)
BenchmarkTools.Trial: 87 samples with 1 evaluation.
 Range (min … max):  49.428 ms … 73.439 ms  ┊ GC (min … max):  0.00% … 15.99%
 Time  (median):     59.021 ms              ┊ GC (median):    13.88%
 Time  (mean ± σ):   57.907 ms ±  4.964 ms  ┊ GC (mean ± σ):  11.25% ±  7.02%
    ▂   ▂                       ▄▆ ▂▄ ▂█   ▄
  ▄███▆▆█▆▁▆▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▆█▄██▆██▄██▄▄██▄▆▁▁▄▁▁▆▁▁▁▁▁▁▆▁▄ ▁
  49.4 ms         Histogram: frequency by time        67.2 ms <
 Memory estimate: 31.27 MiB, allocs estimate: 460177.
julia> @benchmark Cthulhu.@interp kernel3(n)
BenchmarkTools.Trial: 72 samples with 1 evaluation.
 Range (min … max):  58.903 ms … 86.339 ms  ┊ GC (min … max):  0.00% … 12.85%
 Time  (median):     69.709 ms              ┊ GC (median):    12.42%
 Time  (mean ± σ):   69.451 ms ±  4.483 ms  ┊ GC (mean ± σ):  11.22% ±  4.97%
                       ▂▂▃   █ ▂
  ▄▄▁▇▄▄▁▄▁▄▁▁▁▁▁▁▁▄▁▅▅▇▅▇███▅▇▅█▇█▁█▅▄▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄ ▁
  58.9 ms         Histogram: frequency by time        82.9 ms <
 Memory estimate: 37.30 MiB, allocs estimate: 550050.

julia> function kernel3(n)

kernel1′(n, 1.0), kernel1′(n, 10.0)

end

kernel3 (generic function with 1 method)

julia> profile_absint(Cthulhu.@interp kernel3(n))

Profiling results on: MethodInstance for kernel3(::Int64)

[non-constant absint]

analyzed 605 calls / 389 lines (in 22 files)

[constant absint]

analyzed 1114 calls / 268 lines (in 17 files)

julia> using BenchmarkTools

julia> @benchmark Cthulhu.@interp kernel1′(n, x)

BenchmarkTools.Trial: 106 samples with 1 evaluation.

Range (min … max): 39.912 ms … 68.155 ms ┊ GC (min … max): 0.00% … 12.90%

Time (median): 48.977 ms ┊ GC (median): 14.32%

Time (mean ± σ): 47.258 ms ± 5.013 ms ┊ GC (mean ± σ): 10.50% ± 8.26%

▂ ▂ █ ▄▂ █▂▆▆▄▂▆

██████▆▆███▄▆▁▁▄▁▁▁▁▁▁▁▁▁▄▄▄██▆▆███████▄▆▁▆▆▁▄▁▁▁▁▁▁▁▁▁▁▁▁▆ ▄

39.9 ms Histogram: frequency by time 57.6 ms <

Memory estimate: 26.03 MiB, allocs estimate: 384784.

julia> @benchmark Cthulhu.@interp kernel2(n)

BenchmarkTools.Trial: 87 samples with 1 evaluation.

Range (min … max): 49.428 ms … 73.439 ms ┊ GC (min … max): 0.00% … 15.99%

Time (median): 59.021 ms ┊ GC (median): 13.88%

Time (mean ± σ): 57.907 ms ± 4.964 ms ┊ GC (mean ± σ): 11.25% ± 7.02%

▂ ▂ ▄▆ ▂▄ ▂█ ▄

▄███▆▆█▆▁▆▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▆█▄██▆██▄██▄▄██▄▆▁▁▄▁▁▆▁▁▁▁▁▁▆▁▄ ▁

49.4 ms Histogram: frequency by time 67.2 ms <

Memory estimate: 31.27 MiB, allocs estimate: 460177.

julia> @benchmark Cthulhu.@interp kernel3(n)

BenchmarkTools.Trial: 72 samples with 1 evaluation.

Range (min … max): 58.903 ms … 86.339 ms ┊ GC (min … max): 0.00% … 12.85%

Time (median): 69.709 ms ┊ GC (median): 12.42%

Time (mean ± σ): 69.451 ms ± 4.483 ms ┊ GC (mean ± σ): 11.22% ± 4.97%

▂▂▃ █ ▂

▄▄▁▇▄▄▁▄▁▄▁▁▁▁▁▁▁▄▁▅▅▇▅▇███▅▇▅█▇█▁█▅▄▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄ ▁

58.9 ms Histogram: frequency by time 82.9 ms <

Memory estimate: 37.30 MiB, allocs estimate: 550050.

エフェクト解析のモチベーション

以上の説明で、定数がたくさん使われている関数をコンパイルする際には、 Juliaコンパイラの抽象解釈が潜在的に持っているレイテンシの問題が顕在化しやすいことが想像いただけたのではないかと思います。普通にJuliaでプログラミングをしている時にはそのような状況はあまり発生しませんが、特にシミュレーションなどの場面で特定のパラメータから自動生成されたプログラムをコンパイルする時などに実際に起こり得ます。次のコード例はかなり人工的ですがそういったシチュエーションで発生するレイテンシの問題をよく理解することができます:

julia> let param = 1000
           ex = Expr(:block)
           var = gensym()
           push!(ex.args, :($var = x))
           for _ = 1:param
               newvar = gensym()
               push!(ex.args, :($newvar = sin($var)))
               var = newvar
           end
           @eval global function compute(x)
               $ex
           end
       end
compute (generic function with 1 method)
julia> function simkernel()
           compute(1.0)
       end
simkernel (generic function with 2 methods)
julia> profile_absint(@time Cthulhu.@interp simkernel()) # 解析に12秒もかかってしまう!
 12.409912 seconds (11.74 M allocations: 791.039 MiB, 6.88% gc time)
Profiling results on: MethodInstance for simkernel()
  [non-constant abstract interpretation]
    analyzed 410 calls / 285 lines (in 18 files)
  [constant abstract interpretation]
    analyzed 45503 calls / 149 lines (in 14 files)

julia> let param = 1000

ex = Expr(:block)

var = gensym()

push!(ex.args, :($var = x))

for _ = 1:param

newvar = gensym()

push!(ex.args, :($newvar = sin($var)))

var = newvar

end

@eval global function compute(x)

$ex

end

compute (generic function with 1 method)

julia> function simkernel()

compute(1.0)

end

simkernel (generic function with 2 methods)

julia> profile_absint(@time Cthulhu.@interp simkernel()) # 解析に12秒もかかってしまう!

12.409912 seconds (11.74 M allocations: 791.039 MiB, 6.88% gc time)

Profiling results on: MethodInstance for simkernel()

[non-constant abstract interpretation]

analyzed 410 calls / 285 lines (in 18 files)

[constant abstract interpretation]

analyzed 45503 calls / 149 lines (in 14 files)

今回我々が開発したエフェクト解析のアイディアは、 Juliaコンパイラの抽象解釈が行うような関数境界を跨いだ定数伝播における精度とレイテンシのトレードオフを一気に改善するための秘策です —— エフェクト解析を用いて関数呼び出しが特定の条件を満たすと証明できる場合に、 定数伝播のプロセスを丸ごと実際のプログラム実行で置き換えてしまうことで、定数伝播にかかるコストを削減しコンパイルタイムレイテンシを大幅に改善し、さらには定数畳み込みの範囲を拡大しランタイムパフォーマンスまで向上させることができるのです。このアイディアで重要なのは、Julia言語処理系が実行時直前に行うコンパイルタイムにおいては、 実際にJuliaプログラムを実行可能なランタイムシステムが利用可能である ということです。つまり、エフェクト解析を用いて、静的な抽象解釈のプロセスに、動的で具体的なプログラム実行を部分的に入れ込むことで、抽象解釈の精度とレイテンシを改善しようというわけです。我々はこのエフェクト解析に基づく実際のプログラム実行による抽象解釈の部分的な具体化を、 "abstract interpretation" と対比させ、 (partial) concrete evaluation と呼んでいます。

実際にこの concrete evaluation を有効化して、 simkernel() 呼び出しに対する抽象解釈のパフォーマンスを確認してみましょう:

julia> # おまじない: 今回紹介するエフェクト解析を有効化する
       function Core.Compiler.concrete_eval_eligible(interp::Cthulhu.CthulhuInterpreter,
           @nospecialize(f), result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)
           return Base.@invoke Core.Compiler.concrete_eval_eligible(interp::Core.Compiler.AbstractInterpreter,
               f::Any, result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState) # enable concrete-evaluation
       end
julia> profile_absint(Cthulhu.@interp simkernel())
Profiling results on: MethodInstance for simkernel()
  [non-constant abstract interpretation]
    analyzed 410 calls / 285 lines (in 18 files)
  [constant abstract interpretation]
    analyzed 217 calls / 43 lines (in 10 files)
julia> @benchmark Cthulhu.@interp simkernel()
BenchmarkTools.Trial: 133 samples with 1 evaluation.
 Range (min … max):  30.529 ms … 55.645 ms  ┊ GC (min … max):  0.00% … 17.02%
 Time  (median):     38.503 ms              ┊ GC (median):    15.34%
 Time  (mean ± σ):   37.783 ms ±  4.941 ms  ┊ GC (mean ± σ):  10.57% ±  9.33%
  ▂▄ ▆▆█▂  ▄▂▂        ▄█▄▂█▂  ▂ ▂▂  ▂▂
  ███████▄▆███▆▄▆▆▁▆▆▄███████▆█▆██▁███▄▄▄▁▁▆▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▄ ▄
  30.5 ms         Histogram: frequency by time        53.1 ms <
 Memory estimate: 23.12 MiB, allocs estimate: 350017.

julia> # おまじない: 今回紹介するエフェクト解析を有効化する

function Core.Compiler.concrete_eval_eligible(interp::Cthulhu.CthulhuInterpreter,

@nospecialize(f), result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)

return Base.@invoke Core.Compiler.concrete_eval_eligible(interp::Core.Compiler.AbstractInterpreter,

f::Any, result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState) # enable concrete-evaluation

end

julia> profile_absint(Cthulhu.@interp simkernel())

Profiling results on: MethodInstance for simkernel()

[non-constant abstract interpretation]

analyzed 410 calls / 285 lines (in 18 files)

[constant abstract interpretation]

analyzed 217 calls / 43 lines (in 10 files)

julia> @benchmark Cthulhu.@interp simkernel()

BenchmarkTools.Trial: 133 samples with 1 evaluation.

Range (min … max): 30.529 ms … 55.645 ms ┊ GC (min … max): 0.00% … 17.02%

Time (median): 38.503 ms ┊ GC (median): 15.34%

Time (mean ± σ): 37.783 ms ± 4.941 ms ┊ GC (mean ± σ): 10.57% ± 9.33%

▂▄ ▆▆█▂ ▄▂▂ ▄█▄▂█▂ ▂ ▂▂ ▂▂

███████▄▆███▆▄▆▆▁▆▆▄███████▆█▆██▁███▄▄▄▁▁▆▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▄ ▄

30.5 ms Histogram: frequency by time 53.1 ms <

Memory estimate: 23.12 MiB, allocs estimate: 350017.

以下のような劇的な改善が確認できますね:

定数伝播された呼び出しの数が大幅に削減された(45503 calls → 217 calls)
抽象解釈のパフォーマンスが劇的に改善された(12.409912 seconds → 37.783 ms)

また、より一般的なケースである kernel1′(n, x), kernel2(n), kernel3(n) においてもパフォーマンスが向上していることも確認できます:

julia> @benchmark Cthulhu.@interp kernel1′(n, x)
BenchmarkTools.Trial: 144 samples with 1 evaluation.
 Range (min … max):  28.577 ms … 45.297 ms  ┊ GC (min … max):  0.00% … 24.93%
 Time  (median):     35.537 ms              ┊ GC (median):     7.94%
 Time  (mean ± σ):   34.772 ms ±  4.419 ms  ┊ GC (mean ± σ):  10.63% ±  9.70%
  █▁ ▂ ▇      ▂               ▁        ▁  ▁
  ██▅█▅█▁▅█▃▆▆█▆▅▆▅█▅▁▃▁▃▁▁▁▃▁█▃▃▆█▆██▆█▃▆██▅▆▁▅▆▅▆▆▆▃▁▃▁▁▃▁▃ ▃
  28.6 ms         Histogram: frequency by time        43.5 ms <
 Memory estimate: 22.33 MiB, allocs estimate: 331793.
julia> @benchmark Cthulhu.@interp kernel2(n)
BenchmarkTools.Trial: 137 samples with 1 evaluation.
 Range (min … max):  29.024 ms … 64.579 ms  ┊ GC (min … max):  0.00% … 25.32%
 Time  (median):     37.076 ms              ┊ GC (median):    15.54%
 Time  (mean ± σ):   36.598 ms ±  5.440 ms  ┊ GC (mean ± σ):  10.70% ±  9.56%
     █▃        ▁     ▁ ▄▂
  ▄▇████▄▄▇▄▆▇▄█▁▁▆▇▇█████▇█▁▆▄▇▆▄▆▃▁▁▃▁▁▃▃▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▃ ▃
  29 ms           Histogram: frequency by time        55.2 ms <
 Memory estimate: 22.78 MiB, allocs estimate: 338744.
julia> @benchmark Cthulhu.@interp kernel3(n)
BenchmarkTools.Trial: 135 samples with 1 evaluation.
 Range (min … max):  29.907 ms … 61.337 ms  ┊ GC (min … max):  0.00% … 12.88%
 Time  (median):     38.004 ms              ┊ GC (median):    15.74%
 Time  (mean ± σ):   37.240 ms ±  5.199 ms  ┊ GC (mean ± σ):  10.54% ±  9.38%
   ▃▄▁▆▄▁  ▄ ▁▄         ▁▁▄   ▁▃▃█ ▁ ▃
  ▇██████▇▆█▄██▁▄▄▄▄▆▆▁▆███▆▇▆████▄█▆█▆▇▇▁▁▄▄▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▄ ▄
  29.9 ms         Histogram: frequency by time        51.5 ms <
 Memory estimate: 23.22 MiB, allocs estimate: 345305.

julia> @benchmark Cthulhu.@interp kernel1′(n, x)

BenchmarkTools.Trial: 144 samples with 1 evaluation.

Range (min … max): 28.577 ms … 45.297 ms ┊ GC (min … max): 0.00% … 24.93%

Time (median): 35.537 ms ┊ GC (median): 7.94%

Time (mean ± σ): 34.772 ms ± 4.419 ms ┊ GC (mean ± σ): 10.63% ± 9.70%

█▁ ▂ ▇ ▂ ▁ ▁ ▁

██▅█▅█▁▅█▃▆▆█▆▅▆▅█▅▁▃▁▃▁▁▁▃▁█▃▃▆█▆██▆█▃▆██▅▆▁▅▆▅▆▆▆▃▁▃▁▁▃▁▃ ▃

28.6 ms Histogram: frequency by time 43.5 ms <

Memory estimate: 22.33 MiB, allocs estimate: 331793.

julia> @benchmark Cthulhu.@interp kernel2(n)

BenchmarkTools.Trial: 137 samples with 1 evaluation.

Range (min … max): 29.024 ms … 64.579 ms ┊ GC (min … max): 0.00% … 25.32%

Time (median): 37.076 ms ┊ GC (median): 15.54%

Time (mean ± σ): 36.598 ms ± 5.440 ms ┊ GC (mean ± σ): 10.70% ± 9.56%

█▃ ▁ ▁ ▄▂

▄▇████▄▄▇▄▆▇▄█▁▁▆▇▇█████▇█▁▆▄▇▆▄▆▃▁▁▃▁▁▃▃▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▃ ▃

29 ms Histogram: frequency by time 55.2 ms <

Memory estimate: 22.78 MiB, allocs estimate: 338744.

julia> @benchmark Cthulhu.@interp kernel3(n)

BenchmarkTools.Trial: 135 samples with 1 evaluation.

Range (min … max): 29.907 ms … 61.337 ms ┊ GC (min … max): 0.00% … 12.88%

Time (median): 38.004 ms ┊ GC (median): 15.74%

Time (mean ± σ): 37.240 ms ± 5.199 ms ┊ GC (mean ± σ): 10.54% ± 9.38%

▃▄▁▆▄▁ ▄ ▁▄ ▁▁▄ ▁▃▃█ ▁ ▃

▇██████▇▆█▄██▁▄▄▄▄▆▆▁▆███▆▇▆████▄█▆█▆▇▇▁▁▄▄▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▄ ▄

29.9 ms Histogram: frequency by time 51.5 ms <

Memory estimate: 23.22 MiB, allocs estimate: 345305.

Part.1 まとめ

この記事では、Juliaコンパイラの設計思想や基本的な動作原理を説明し、特にそのコンパイラの核となっている抽象解釈における精度とレイテンシのトレードオフについて詳しく解説しました。最後に紹介したように、エフェクト解析を利用した concrete evaluation により、このトレードオフを劇的に改善することができるのですが、いよいよ次のPart.2では、そのエフェクト解析の中身について詳しく解説したいと思います。また、Juliaプログラムをさらに最適化する上で利用可能なエフェクトアノテーションについても紹介する予定なので、ぜひ楽しみにお待ちください。

リンク

GitHub: https://github.com/aviatesk
Twitter: https://twitter.com/kdwkshh
Blog (English): https://aviatesk.github.io/

ちなみに"Koka"という名前は、日本語の「効果」にちなんで名付けられているようです。↩︎
この記事で紹介する、エフェクト解析によってJulia言語の最適化を行うというアイディアの基本的な部分は、 Juliaコンパイラの開発者の1人である Keno Fisher さんによるものであることを断っておきます。↩︎
JavaScriptのV8やJVMのHotSpotのようなプロファイリングに基づくJIT (PGO – Profile-Guided-Optimization)は、 Julia言語処理系には現在(2022年6月)のところ実装されていません。 Julia言語処理系は2つのランタイムシステムを有しており、プログラムをコンパイルして実行することも、インタープリターで実行することもどちらもできるため、 PGOを行うためのインフラストラクチャを既に備えています。その一方で我々はJuliaのような言語処理系においては、 PGOによるプログラムの効率化の効果は限定的であると考えています。 PGOよりもJuliaコンパイラが現在行っているようなAoT的なアプローチの方が、より強力でコストパフォーマンスに優れた最適化を実現できるという前提の下、 PGOの実装を急ぐよりも、現行のコンパイラの精度やパフォーマンスを高める方にプライオリティを置いています。↩︎
このJuliaのプログラムの型を解決するプロセスを指して「型推論」と呼ぶこともありますが、このJuliaコンパイラが行っている抽象解釈ベースの静的解析は、 Haskellなどの静的型付け言語で行われている所謂「型推論」とは全く違う技術であることに注意してください。この記事においてはJuliaコンパイラが行う型解析を単に「抽象解釈」と呼びます。↩︎
この記事においては、Juliaプログラムのオブジェクトが実行時に持ちうる Int や String などのオブジェクト型を指して、「型(レベル)」という単語を使います。↩︎
例えば、Julia処理系も利用しているコンパイラバックエンドLLVMも "Attributor" と呼ばれる、関数呼び出しに対するフラグに基づいたIPOのインフラストラクチャを提供していますが、残念ながら現在のところレイテンシがすこぶる悪く、このIPOをJuliaコンパイラで有効化するとコンパイルが終わらなくなってしまいます… 逆にその意味では、Juliaが比較的新しい言語であるのにも関わらず、既に実用言語としての実績を達成できている最大の理由の1つは、そのコンパイラが実用的なIPO能力を保持しているからと言うこともできるかもしれません。↩︎
定数畳み込みを行わない場合、 LICM – Loop-Invariant-Code-Motion と呼ばれる最適化により、 sum(mysincos(x)) の計算をループの外に追いやることで計算量を削減することができます。一方LICMを行ったとしても、最低1度は sum(mysincos(x)) の計算が実行時に発生するため、この場合厳密には定数畳み込みの方が強力な最適化です。また、LICMを行う場合でも、今回紹介するエフェクト解析に類する解析が必要となります。↩︎
なぜいきなり「インライン展開可能かどうか("inlineability")」という、一見すると定数伝播と直接関係なさそうな条件が出てきたのでしょうか。ここでは例として、関数呼び出し f(...) をコンパイル中に、f 内の関数呼び出し g(...) における定数伝播を考えているとします。この時 g(...) を定数情報ありでコンパイルした結果は、上述の理由からキャッシュされません。 Julia言語処理系は実行中に関数呼び出しがあった場合、キャッシュされてるコンパイル結果があるかをまず確認し、ある場合はそのままそのコンパイル結果を利用してその呼び出しを実行し、ない場合は その呼び出しの引数の「型レベル」の情報を用いて 新たにコンパイルを開始します。そのため、 g(...) が f(...) 内にインライン展開されない場合、 g(...) を定数情報ありで解析しコンパイルした結果は無駄になってしまうのです。一方、 g(...) が f(...) 内にインライン展開される場合は、 g に伝播させた定数情報は f 内に埋め込まれるため無駄にはなりません。またg に定数情報を伝播させることで g 内の無駄な条件分岐を削減しすることで、 g のインライン展開をさらに効率的にできる可能性も見込めます。以上のロジックが、現在Julia言語処理系が定数伝播のヒューリスティックに "inlineability" を利用している理由です。↩︎

Recruit Tech Blog

タグから見つける

タグから見つける

職種を選択

事業領域を選択

エフェクト解析による動的言語最適化 Part.1

Juliaコンパイラにおけるトレードオフ

抽象解釈

関数境界を跨いだ抽象解釈

定数伝播による抽象解釈の精度向上

定数伝播とレイテンシ

エフェクト解析のモチベーション

Part.1 まとめ

リンク