2021.11.07

インライン展開入門

門脇宗平

こんにちは。ATL客員研究員の門脇です。普段はMITのJuliaLabという組織のResearch Programmerとしてプログラミング言語Juliaのコンパイラの開発に携わっています。

今回はJulia言語がサポートするインライン展開についてのご紹介したいと思います。「インライン展開」や「インライン最適化」といった言葉はよく聞きますが、その中身についてはあまり知らない方も多いかもしれません。この記事では、そもそもインライン展開とはなにかそしてなんのために行われるのかといったところから説明し、インライン展開によりパフォーマンスが改善される例や、Juliaプログラマが利用可能なインライン展開に関するアノテーション、そしてJuliaコンパイラのインラインコストモデルについて簡単に説明します。

Note: English version of this post is available at Inlining 101.

インライン展開とは

インライン展開とはプログラム最適化の一般的なテクニックの1つです。プログラム中に含まれる関数呼び出しについて、関数の中身を呼び出し元で展開することで、以下のようなパフォーマンス上の恩恵が得られる場合があります:

関数呼び出しにかかるオーバヘッドの削減
インライン展開によりその他の最適化のチャンスが増える

一般的には最近の強力なCPU上では 1. の関数呼び出しにかかるコスト自体はかなり低く、多くの場合で他の計算コストと比較した場合に無視できるほど小さいことが多いそうです ¹ 。ただヘビーなループ内で呼び出されている関数呼び出しがインライン展開されていない場合、関数呼び出しのオーバーヘッドが累積し顕在化する場合もあります。また、呼び出される関数が非常にシンプルで小さくかつ高頻度で呼ばれる場合は、その関数の計算本体に比して関数呼び出しのコストの割合が大きくなるため、そうした関数をインライン展開することにより相対的なパフォーマンスゲインを得ることができるでしょう。

一方インライン展開の有無は多くの場合で後続のプログラムの最適化機会を大きく変えるため、 2. の効果はより広い文脈でプログラムのパフォーマンスに影響を与えます。一般に、プログラム解析は 関数呼び出しを跨ぐ解析 inter-procedural analysis よりも、ローカルなスコープに限った解析 intra-procedural analysis の方が容易です。インライン展開は、本来関数呼び出しを跨がなければ解析できないルーチン達をひとまとめにしてくれるため、プログラム最適化の視点からすれば、難しい最適化問題を易しい最適化問題に変換してくれているようなものなのです。また、こうした理由から、インライン展開は通常プログラム最適化のパイプラインの初めの方の段階で行われた方が効果的です。

具体例で見てみるインライン展開

現代的なコンパイラは様々な最適化を行うため、インライン展開によって具体的にどのような最適化が可能になるのか一概に語るのは難しいのですが、ここでは簡単なJuliaプログラムについて、インライン展開によってメモリアロケーションまで削減できてしまう例を見てみましょう。

こんなJuliaプログラムを考えます ²:

julia> struct Point
           x::Float64
           y::Float64
       end
julia> a::Point +ₚ b::Point = Point(a.x+b.x, a.y+b.y)
+ₚ (generic function with 1 method)
julia> function compute(n)
           a = Point(1.5, 2.5) 
           b = Point(2.25, 4.75)
           for i in 0:(n-1)
               a = (a +ₚ b) +ₚ b
           end
           return a.x, a.y 
       end
compute (generic function with 1 method)

julia> struct Point

x::Float64

y::Float64

end

julia> a::Point +ₚ b::Point = Point(a.x+b.x, a.y+b.y)

+ₚ (generic function with 1 method)

julia> function compute(n)

a = Point(1.5, 2.5)

b = Point(2.25, 4.75)

for i in 0:(n-1)

a = (a +ₚ b) +ₚ b

end

return a.x, a.y

end

compute (generic function with 1 method)

compute(n::Int) という呼び出しは、まず a と b という2つの Point 構造体をアロケーションします。次にループの中で使用されている ::Point +ₚ ::Point 呼び出しは、 Point 型の引数を受け取り、新たな Point 構造体をアロケーションし返します。ループは引数 n の回数だけ繰り返されるので、このままでは n の値によってはかなり多くのアロケーションが発生してしまうことになります。

何とか Point のアロケーションを防ぐことはできないでしょうか？

+ₚ がインラインされない場合、 +ₚ の引数として渡されるために Point 型オブジェクトがメモリ上に存在する必要があるため、アロケーションを避けることはできません。

では、 +ₚ を compute 内にインライン展開した場合はどうでしょう？コンパイラがインライン展開を行なった後の compute は以下のようなプログラムと同等になります:

function compute(n)
    a = Point(1.5, 2.5)
    b = Point(2.25, 4.75)
    for i in 0:(n-1)
        tmp = Point(a.x+b.x,   a.y+b.y)   # the expanded body of `a +ₚ b`
        a   = Point(tmp.x+b.x, tmp.y+b.y) # the expanded body of `tmp +ₚ b`
    end
    return a.x, a.y
end

function compute(n)

a = Point(1.5, 2.5)

b = Point(2.25, 4.75)

for i in 0:(n-1)

tmp = Point(a.x+b.x, a.y+b.y) # the expanded body of `a +ₚ b`

a = Point(tmp.x+b.x, tmp.y+b.y) # the expanded body of `tmp +ₚ b`

end

return a.x, a.y

end

よく目を凝らすと、上のプログラムは Point をスカラー値で置き換えた次のプログラムと同等であることがわかるかと思います:

function compute(n)
    ax, ay = 1.5, 2.5   # replaced `Point(1.5, 2.5)`
    bx, by = 2.25, 4.75 # replaced `Point(2.25, 4.75)`
    for i in 0:(n-1)
        tmpx, tmpy = ax+bx,   ay+by   # replaced `Point(a.x+b.x,   a.y+b.y)`
        ax,   ay   = tmpx+bx, tmpy+by # replaced `Point(tmp.x+b.x, tmp.y+b.y)`
    end
    return ax, ay
end

function compute(n)

ax, ay = 1.5, 2.5 # replaced `Point(1.5, 2.5)`

bx, by = 2.25, 4.75 # replaced `Point(2.25, 4.75)`

for i in 0:(n-1)

tmpx, tmpy = ax+bx, ay+by # replaced `Point(a.x+b.x, a.y+b.y)`

ax, ay = tmpx+bx, tmpy+by # replaced `Point(tmp.x+b.x, tmp.y+b.y)`

end

return ax, ay

end

なんとインライン展開を行うことで、元のプログラムのセマンティクスを保ったまま Point のアロケーションを完全に取り除くことができました。

ここでは説明のため元のプログラムに対してマニュアルでインライン展開しアロケーションを取り除きましたが、こうした処理をコンパイラは全て自動で行います。そのためプログラマは基本的にこうした最適化を自分で行う必要はありませんし、もしあるとしたらそうした必要はコンパイラの発展によって解決されていくべきです。

実際、Julia処理系はこうしたインライン展開とアロケーション最適化³を実装しており、関数呼び出し compute(100_000_000) に伴うアロケーションを完全に取り除くことができます。 @code_typed compute(100_000_000) の出力を確認することで以上で説明した最適化が確かに行われているのを確認できます:

julia> @code_typed compute(100_000_000) # fully inlined
CodeInfo(
1 ── %1  = Base.sle_int(1, n)::Bool
└───       goto #3 if not %1
2 ──       goto #4
3 ──       goto #4
4 ┄─ %5  = φ (#2 => _2, #3 => 0)::Int64
└───       goto #5
5 ──       goto #6
6 ── %8  = Base.slt_int(%5, 1)::Bool
└───       goto #8 if not %8
7 ──       Base.nothing::Nothing
└───       goto #9
8 ──       goto #9
9 ┄─ %13 = φ (#7 => true, #8 => false)::Bool
│    %14 = φ (#8 => 1)::Int64
│    %15 = Base.not_int(%13)::Bool
└───       goto #15 if not %15
10 ┄ %17 = φ (#9 => %14, #14 => %30)::Int64
│    %18 = φ (#9 => 1.5, #14 => %22)::Float64
│    %19 = φ (#9 => 2.5, #14 => %23)::Float64
│    %20 = Base.add_float(%18, 2.25)::Float64
│    %21 = Base.add_float(%19, 4.75)::Float64
│    %22 = Base.add_float(%20, 2.25)::Float64
│    %23 = Base.add_float(%21, 4.75)::Float64
│    %24 = (%17 === %5)::Bool
└───       goto #12 if not %24
11 ─       Base.nothing::Nothing
└───       goto #13
12 ─ %28 = Base.add_int(%17, 1)::Int64
└───       goto #13
13 ┄ %30 = φ (#12 => %28)::Int64
│    %31 = φ (#11 => true, #12 => false)::Bool
│    %32 = Base.not_int(%31)::Bool
└───       goto #15 if not %32
14 ─       goto #10
15 ┄ %35 = φ (#13 => %22, #9 => 1.5)::Float64
│    %36 = φ (#13 => %23, #9 => 2.5)::Float64
│    %37 = Core.tuple(%35, %36)::Tuple{Float64, Float64}
└───       return %37
) => Tuple{Float64, Float64}

julia> @code_typed compute(100_000_000) # fully inlined

CodeInfo(

1 ── %1 = Base.sle_int(1, n)::Bool

└─── goto #3 if not %1

2 ── goto #4

3 ── goto #4

4 ┄─ %5 = φ (#2 => _2, #3 => 0)::Int64

└─── goto #5

5 ── goto #6

6 ── %8 = Base.slt_int(%5, 1)::Bool

└─── goto #8 if not %8

7 ── Base.nothing::Nothing

└─── goto #9

8 ── goto #9

9 ┄─ %13 = φ (#7 => true, #8 => false)::Bool

│ %14 = φ (#8 => 1)::Int64

│ %15 = Base.not_int(%13)::Bool

└─── goto #15 if not %15

10 ┄ %17 = φ (#9 => %14, #14 => %30)::Int64

│ %18 = φ (#9 => 1.5, #14 => %22)::Float64

│ %19 = φ (#9 => 2.5, #14 => %23)::Float64

│ %20 = Base.add_float(%18, 2.25)::Float64

│ %21 = Base.add_float(%19, 4.75)::Float64

│ %22 = Base.add_float(%20, 2.25)::Float64

│ %23 = Base.add_float(%21, 4.75)::Float64

│ %24 = (%17 === %5)::Bool

└─── goto #12 if not %24

11 ─ Base.nothing::Nothing

└─── goto #13

12 ─ %28 = Base.add_int(%17, 1)::Int64

└─── goto #13

13 ┄ %30 = φ (#12 => %28)::Int64

│ %31 = φ (#11 => true, #12 => false)::Bool

│ %32 = Base.not_int(%31)::Bool

└─── goto #15 if not %32

14 ─ goto #10

15 ┄ %35 = φ (#13 => %22, #9 => 1.5)::Float64

│ %36 = φ (#13 => %23, #9 => 2.5)::Float64

│ %37 = Core.tuple(%35, %36)::Tuple{Float64, Float64}

└─── return %37

) => Tuple{Float64, Float64}

どこにもPoint型のオブジェクトがなく、アロケーションが完全に取り除かれているのが確認できると思います。

インラインコストモデル

一方で、インライン展開は常にやればいいのかというと、そういうわけでもありません。過度なインライン展開は以下のような理由によって、逆にパフォーマンスを劣化させてしまう場合があるのです:

実行時のコスト:
- コンパイルされたネイティブコードのサイズが大きくなり、それ自体がメモリを逼迫してしまう
- コードサイズが大きくなることで、メモリアクセスの局所参照性が悪くなりキャッシュミスが起こりやすくなってしまう
- コードが複雑になることで、投機的実行による最適化が難しくなってしまう
コンパイル時のオーバヘッド: 中間プログラム表現(IR)のサイズが大きくなり複雑になってしまうことで後続の最適化パスにより多くの時間がかかってしまう

そのため、コンパイラはある関数をインライン展開するかしないかについて何らかのコストモデルを定義し、それに従ってインライン展開の是非を決定します。このコストモデルは多くの場合ヒューリスティック的に定義されます。ヒューリスティクスには次のような判断基準が用いられているようです:

関数がシンプルか否か
関数のコールサイトの数 (静的な関数呼び出し回数)
実行時に関数が呼ばれた回数 (動的な関数呼び出し回数)
引数がエスケープしないかどうか ⁴

いずれにせよ絶対的な正解がない問題であるので、機械学習によるコストモデルの使用など、他にも色々と可能性が考えられるテーマです。インライン展開のアイディア自体は非常にシンプルですが、実はかなり奥が深いのです。

Juliaプログラマが利用可能なインラインアノテーション

Juliaコンパイラも独自のインラインコストモデルを持っています。 Juliaのインラインコストモデルは上で説明した判断基準のうち 1. 関数がシンプルか否か に基づいてインライン展開の有無を決定します。

このコストモデルはとてもシンプルですが、多くの場合でリーズナブルな判断を下します。そのためJuliaプログラマは基本的にはインライン展開のことを考える必要はありません。

一方で、プログラムのパフォーマンスを追求するために、 code_typed や Cthulhu.jl を利用してプログラムを調べているときに、コンパイラが期待通りにインライン展開を行なってくれていない時があるかもしれません。

例えば、上記のプログラムを少しいじった以下のプログラムを考えてみましょう。インラインコストモデルを騙すため、わざと /ₚ の中で不自然なエラーチェックを行なっています(その理由は最後の章で説明しています):

julia> struct Point
           x::Float64
           y::Float64
       end
julia> a::Point +ₚ b::Point = Point(a.x+b.x, a.y+b.y)
+ₚ (generic function with 1 method)
julia> a::Point /ₚ b::Point = begin
           # error pass
           if false
               @label diverror
               error("/ₚ: division error detected !")
           end
           # do some error checks
           iszero(a.y) && @goto diverror
           iszero(b.y) && @goto diverror
           # do the main computation
           Point(a.x/a.y, b.x/b.y)
       end
/ₚ (generic function with 1 method)
julia> function compute(n)
           a = Point(1.5, 2.5)
           b = Point(2.25, 4.75)
           for i in 0:(n-1)
               a = (a +ₚ b) /ₚ b
           end
           return a.x, a.y
       end
compute (generic function with 1 method)

julia> struct Point

x::Float64

y::Float64

end

julia> a::Point +ₚ b::Point = Point(a.x+b.x, a.y+b.y)

+ₚ (generic function with 1 method)

julia> a::Point /ₚ b::Point = begin

# error pass

if false

@label diverror

error("/ₚ: division error detected !")

end

# do some error checks

iszero(a.y) && @goto diverror

iszero(b.y) && @goto diverror

# do the main computation

Point(a.x/a.y, b.x/b.y)

end

/ₚ (generic function with 1 method)

julia> function compute(n)

a = Point(1.5, 2.5)

b = Point(2.25, 4.75)

for i in 0:(n-1)

a = (a +ₚ b) /ₚ b

end

return a.x, a.y

end

compute (generic function with 1 method)

比較のため、一旦この時点でのベンチマークを取ってみましょう:

julia> using BenchmarkTools
julia> @benchmark compute(100_000_000)
BenchmarkTools.Trial: 6 samples with 1 evaluation.
 Range (min … max):  935.022 ms … 976.323 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     938.966 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   944.493 ms ±  15.848 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%
  ███      ██                                                 █
  ███▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  935 ms           Histogram: frequency by time          976 ms <
 Memory estimate: 0 bytes, allocs estimate: 0.

julia> using BenchmarkTools

julia> @benchmark compute(100_000_000)

BenchmarkTools.Trial: 6 samples with 1 evaluation.

Range (min … max): 935.022 ms … 976.323 ms ┊ GC (min … max): 0.00% … 0.00%

Time (median): 938.966 ms ┊ GC (median): 0.00%

Time (mean ± σ): 944.493 ms ± 15.848 ms ┊ GC (mean ± σ): 0.00% ± 0.00%

███ ██ █

███▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁

935 ms Histogram: frequency by time 976 ms <

Memory estimate: 0 bytes, allocs estimate: 0.

1億回のループ計算が1秒以下で行われているのでパフォーマンスは既にすこぶる良いですが、まだ早くできるでしょうか。 Juliaプログラムを最適化する第一歩は @code_typed の出力を見てみることです:

julia> @code_typed compute(100_000_000)
CodeInfo(
1 ── %1  = Base.sub_int(n, 1)::Int64
│    %2  = Base.sle_int(0, %1)::Bool
└───       goto #3 if not %2
2 ──       goto #4
3 ──       goto #4
4 ┄─ %6  = φ (#2 => %1, #3 => -1)::Int64
└───       goto #5
5 ──       goto #6
6 ── %9  = Base.slt_int(%6, 0)::Bool
└───       goto #8 if not %9
7 ──       Base.nothing::Nothing
└───       goto #9
8 ──       goto #9
9 ┄─ %14 = φ (#7 => true, #8 => false)::Bool
│    %15 = φ (#8 => 0)::Int64
│    %16 = Base.not_int(%14)::Bool
└───       goto #15 if not %16
10 ┄ %18 = φ (#9 => %15, #14 => %32)::Int64
│    %19 = φ (#9 => $(QuoteNode(Point(1.5, 2.5))), #14 => %25)::Point
│    %20 = Base.getfield(%19, :x)::Float64
│    %21 = Base.add_float(%20, 2.25)::Float64
│    %22 = Base.getfield(%19, :y)::Float64
│    %23 = Base.add_float(%22, 4.75)::Float64
│    %24 = %new(Main.Point, %21, %23)::Point
│    %25 = invoke Main.:/ₚ(%24::Point, $(QuoteNode(Point(2.25, 4.75)))::Point)::Point
│    %26 = (%18 === %6)::Bool
└───       goto #12 if not %26
11 ─       Base.nothing::Nothing
└───       goto #13
12 ─ %30 = Base.add_int(%18, 1)::Int64
└───       goto #13
13 ┄ %32 = φ (#12 => %30)::Int64
│    %33 = φ (#11 => true, #12 => false)::Bool
│    %34 = Base.not_int(%33)::Bool
└───       goto #15 if not %34
14 ─       goto #10
15 ┄ %37 = φ (#13 => %25, #9 => $(QuoteNode(Point(1.5, 2.5))))::Point
│    %38 = Base.getfield(%37, :x)::Float64
│    %39 = Base.getfield(%37, :y)::Float64
│    %40 = Core.tuple(%38, %39)::Tuple{Float64, Float64}
└───       return %40
) => Tuple{Float64, Float64}

julia> @code_typed compute(100_000_000)

CodeInfo(

1 ── %1 = Base.sub_int(n, 1)::Int64

│ %2 = Base.sle_int(0, %1)::Bool

└─── goto #3 if not %2

2 ── goto #4

3 ── goto #4

4 ┄─ %6 = φ (#2 => %1, #3 => -1)::Int64

└─── goto #5

5 ── goto #6

6 ── %9 = Base.slt_int(%6, 0)::Bool

└─── goto #8 if not %9

7 ── Base.nothing::Nothing

└─── goto #9

8 ── goto #9

9 ┄─ %14 = φ (#7 => true, #8 => false)::Bool

│ %15 = φ (#8 => 0)::Int64

│ %16 = Base.not_int(%14)::Bool

└─── goto #15 if not %16

10 ┄ %18 = φ (#9 => %15, #14 => %32)::Int64

│ %19 = φ (#9 => $(QuoteNode(Point(1.5, 2.5))), #14 => %25)::Point

│ %20 = Base.getfield(%19, :x)::Float64

│ %21 = Base.add_float(%20, 2.25)::Float64

│ %22 = Base.getfield(%19, :y)::Float64

│ %23 = Base.add_float(%22, 4.75)::Float64

│ %24 = %new(Main.Point, %21, %23)::Point

│ %25 = invoke Main.:/ₚ(%24::Point, $(QuoteNode(Point(2.25, 4.75)))::Point)::Point

│ %26 = (%18 === %6)::Bool

└─── goto #12 if not %26

11 ─ Base.nothing::Nothing

└─── goto #13

12 ─ %30 = Base.add_int(%18, 1)::Int64

└─── goto #13

13 ┄ %32 = φ (#12 => %30)::Int64

│ %33 = φ (#11 => true, #12 => false)::Bool

│ %34 = Base.not_int(%33)::Bool

└─── goto #15 if not %34

14 ─ goto #10

15 ┄ %37 = φ (#13 => %25, #9 => $(QuoteNode(Point(1.5, 2.5))))::Point

│ %38 = Base.getfield(%37, :x)::Float64

│ %39 = Base.getfield(%37, :y)::Float64

│ %40 = Core.tuple(%38, %39)::Tuple{Float64, Float64}

└─── return %40

) => Tuple{Float64, Float64}

この出力から以下の２点が確認できます:

%25 = invoke Main.:/ₚ(%24::Point, $(QuoteNode(Point(2.25, 4.75)))::Point)::Point は /ₚ の関数呼び出しを表していて、つまり /ₚ がインライン展開されていないことを示しています。
また %24 = %new(Main.Point, %21, %23)::Point は Point 型オブジェクトの「アロケーション」⁵ が発生していることを意味しています。

この場合、以下のような理由からインライン展開を行なった方が有益だと考えられます:

ループの回数 n が大きい場合、 /ₚ の呼び出しにかかるコストが累積してしまう
/ₚ をインライン展開することによって、 %24 = %new(Main.Point, %21, %23)::Point と /ₚ 内でのアロケーションを取り除けそう

こんなとき、どうすれば良いでしょうか？ Juliaプログラマは以下の方法を用いてコンパイラにインライン展開を促すことができます:

定義もとアノテーション definition-site annotation
呼び出しもとアノテーション call-site annotation

定義もとアノテーション definition-site annotation

今回の /ₚ のように、インライン展開されていない関数を私たちが「所有」している場合、定義もとアノテーションが利用可能です。使い方は簡単で、 @inline あるいは @noinline マクロをインライン展開したい関数の定義にアノテーションするだけです。

今回は /ₚ をインライン展開したいので、 @inline マクロを利用します:

julia> @inline a::Point /ₚ b::Point = begin
           # error pass
           if false
               @label diverror
               error("/ₚ: division error detected !")
           end
           # do some error checks
           iszero(a.y) && @goto diverror
           iszero(b.y) && @goto diverror
           # do the main computation
           Point(a.x/a.y, b.x/b.y)
       end
/ₚ (generic function with 1 method)

julia> @inline a::Point /ₚ b::Point = begin

# error pass

if false

@label diverror

error("/ₚ: division error detected !")

end

# do some error checks

iszero(a.y) && @goto diverror

iszero(b.y) && @goto diverror

# do the main computation

Point(a.x/a.y, b.x/b.y)

end

/ₚ (generic function with 1 method)

するとどうでしょう、 @inline アノテーションを施すことで、compute(100_000_000) がおよそ35%ほど高速化されました:

# 参考: `@inline`を付けなかった場合
# julia> @benchmark compute(100_000_000)
# BenchmarkTools.Trial: 6 samples with 1 evaluation.
#  Range (min … max):  935.022 ms … 976.323 ms  ┊ GC (min … max): 0.00% … 0.00%
#  Time  (median):     938.966 ms               ┊ GC (median):    0.00%
#  Time  (mean ± σ):   944.493 ms ±  15.848 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%
#
#   ███      ██                                                 █
#   ███▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
#   935 ms           Histogram: frequency by time          976 ms <
#
#  Memory estimate: 0 bytes, allocs estimate: 0.
# `@inline`を付けた場合
julia> @benchmark compute(100_000_000)
BenchmarkTools.Trial: 9 samples with 1 evaluation.
 Range (min … max):  592.375 ms … 623.956 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     599.874 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   601.041 ms ±   9.692 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%
  ▁ ▁▁       ▁  ▁█            ▁                               ▁
  █▁██▁▁▁▁▁▁▁█▁▁██▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  592 ms           Histogram: frequency by time          624 ms <
 Memory estimate: 0 bytes, allocs estimate: 0.

# 参考: `@inline`を付けなかった場合

# julia> @benchmark compute(100_000_000)

# BenchmarkTools.Trial: 6 samples with 1 evaluation.

# Range (min … max): 935.022 ms … 976.323 ms ┊ GC (min … max): 0.00% … 0.00%

# Time (median): 938.966 ms ┊ GC (median): 0.00%

# Time (mean ± σ): 944.493 ms ± 15.848 ms ┊ GC (mean ± σ): 0.00% ± 0.00%

# ███ ██ █

# ███▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁

# 935 ms Histogram: frequency by time 976 ms <

# Memory estimate: 0 bytes, allocs estimate: 0.

# `@inline`を付けた場合

julia> @benchmark compute(100_000_000)

BenchmarkTools.Trial: 9 samples with 1 evaluation.

Range (min … max): 592.375 ms … 623.956 ms ┊ GC (min … max): 0.00% … 0.00%

Time (median): 599.874 ms ┊ GC (median): 0.00%

Time (mean ± σ): 601.041 ms ± 9.692 ms ┊ GC (mean ± σ): 0.00% ± 0.00%

▁ ▁▁ ▁ ▁█ ▁ ▁

█▁██▁▁▁▁▁▁▁█▁▁██▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁

592 ms Histogram: frequency by time 624 ms <

Memory estimate: 0 bytes, allocs estimate: 0.

呼び出しもとアノテーション call-site annotation

次に、インライン展開したい関数を私たちが「所有」していない場合を考えてみましょう。例えば、今回の例でいうと Point や +ₚ 、 /ₚ が自分の管理していないライブラリから提供されており、私たちはそのライブラリのユーザであるような場合がそういった状況に該当します。アルゴリズムを全て一から組み上げるような場面はそうそうないので、むしろそういった状況の方が多いかもしれません。

そのような状況では、先ほどの定義もとアノテーションを利用するのは好ましくありません。 Julia では実行時に関数定義を上書きすることができる⁶ので不可能ではありませんが、あまり行儀が良くなくエラーの元になりやすい他、Julia においてはすでにコンパイル済みのキャッシュを無効化してしまう(俗に "method invalidation" と呼ばれる現象です)ため、余計なオーバヘッドが発生してしまいます。

そんな時は、次の次の安定版である Julia 1.8 で追加される予定の、呼び出しもとアノテーションが利用できます。呼び出しもとアノテーションには、定義もとアノテーションと同じ @inline/@noinline マクロを使いますが、マクロは関数定義に対してではなく関数呼び出しに対してアノテーションされます。呼び出しもとアノテーションを使うために関数定義を上書きする必要はないので、先程のモンキーパッチに付随する問題を気にする必要はありません。

この呼び出しもとアノテーションはJulia言語にもつい最近追加されたものですし、あまり他の言語では聞かない機能なので、まだ馴染みのない人が多いかもしれません。呼び出しもとアノテーションのドキュメントはここで読めますが、簡単に説明すると次のような設計で実装されています:

呼び出しもとアノテーションは、適用されたブロック内の全ての関数呼び出しに対して影響する
呼び出しもとアノテーションは、常に定義もとアノテーションよりも優先される
呼び出しもとアノテーションがネストしている場合、最も内側のアノテーションが優先される

今回であれば、 compute 内で以下のように使ってみます:

julia> function compute(n)
           a = Point(1.5, 2.5)
           b = Point(2.25, 4.75)
           for i in 0:(n-1)
               a = @inline (a +ₚ b) /ₚ b
           end
           return a.x, a.y
       end
compute (generic function with 1 method)

julia> function compute(n)

a = Point(1.5, 2.5)

b = Point(2.25, 4.75)

for i in 0:(n-1)

a = @inline (a +ₚ b) /ₚ b

end

return a.x, a.y

end

compute (generic function with 1 method)

呼び出しもとアノテーションを施すことで、定義もとアノテーションの時と同じ高速化が実現できました:

# 参考: `@inline`を付けなかった場合
# julia> @benchmark compute(100_000_000)
# BenchmarkTools.Trial: 6 samples with 1 evaluation.
#  Range (min … max):  935.022 ms … 976.323 ms  ┊ GC (min … max): 0.00% … 0.00%
#  Time  (median):     938.966 ms               ┊ GC (median):    0.00%
#  Time  (mean ± σ):   944.493 ms ±  15.848 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%
#
#   ███      ██                                                 █
#   ███▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
#   935 ms           Histogram: frequency by time          976 ms <
#
#  Memory estimate: 0 bytes, allocs estimate: 0.
# `@inline`を付けた場合
julia> @benchmark compute(100_000_000)
BenchmarkTools.Trial: 9 samples with 1 evaluation.
 Range (min … max):  592.266 ms … 627.780 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     598.643 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   600.103 ms ±  10.860 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%
  ███  █    ██ ██                                             █
  ███▁▁█▁▁▁▁██▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  592 ms           Histogram: frequency by time          628 ms <
 Memory estimate: 0 bytes, allocs estimate: 0.

# 参考: `@inline`を付けなかった場合

# julia> @benchmark compute(100_000_000)

# BenchmarkTools.Trial: 6 samples with 1 evaluation.

# Range (min … max): 935.022 ms … 976.323 ms ┊ GC (min … max): 0.00% … 0.00%

# Time (median): 938.966 ms ┊ GC (median): 0.00%

# Time (mean ± σ): 944.493 ms ± 15.848 ms ┊ GC (mean ± σ): 0.00% ± 0.00%

# ███ ██ █

# ███▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁

# 935 ms Histogram: frequency by time 976 ms <

# Memory estimate: 0 bytes, allocs estimate: 0.

# `@inline`を付けた場合

julia> @benchmark compute(100_000_000)

BenchmarkTools.Trial: 9 samples with 1 evaluation.

Range (min … max): 592.266 ms … 627.780 ms ┊ GC (min … max): 0.00% … 0.00%

Time (median): 598.643 ms ┊ GC (median): 0.00%

Time (mean ± σ): 600.103 ms ± 10.860 ms ┊ GC (mean ± σ): 0.00% ± 0.00%

███ █ ██ ██ █

███▁▁█▁▁▁▁██▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁

592 ms Histogram: frequency by time 628 ms <

Memory estimate: 0 bytes, allocs estimate: 0.

どんなときにアノテーションを考えるべきか

最後に、こうしたアノテーションがどのような場面で有効なのか、まとめてみたいと思います:

@inline を試してみる: ループの中で何度も呼び出されるシンプルな関数がインライン展開されていないとき
@noinline を試してみる: 滅多に呼び出されない複雑な関数がインライン展開されているとき
@inline アノテーションを無くしてみる: @inline だらけのコードベースのコンパイルがやけに遅いとき

とはいえ、大前提として、プログラマがこうしたアノテーションを与える必要がない方が理想的です。つまり、インライン展開されるべき関数がインライン展開されていない、あるいはインライン展開されるべきでない関数がインライン展開されている場合、それはつまりコンパイラのコストモデルに改善の余地があるということです。

そのため、もしそういった場面に遭遇したら積極的に JuliaLang/julia レポジトリのissue として挙げていただけるとJuliaコンパイラの改善に繋がるかもしれません。つい最近にも、僕の同僚の方がインライン展開の失敗を報告したことで、 Juliaコンパイラの改善に繋がった出来事がありました。

おまけ: Juliaコンパイラのインラインコストモデルを覗いてみる

Cthulhu.jl というパッケージを用いることで、 Juliaコンパイラのインラインコストモデルを覗くことができます。ここではなぜ /ₚ がインライン展開されなかったかを見てみましょう:

julia> using Cthulhu
julia> descend(/ₚ, (Point,Point); inline_cost=true)
/ₚ(a::Point, b::Point) in Main at untitled-e25fcb34ce5237c6bb8376cca04cf1b2:24
│ ─ %-1 = invoke /ₚ(::Point,::Point)::Point
26 1 ─  0       goto #3                                       │
28 2 ┄  0       invoke Main.error("/ₚ: division error detected !"::String)::Union{}
   └──  0       unreachable                                   │
31 3 ─  0 %4  = Base.getfield(_2, :y)::Float64                │╻  getproperty
   │    2 %5  = Base.eq_float(%4, 0.0)::Bool                  ││╻  ==
   └──  0       goto #5 if not %5                             │
   4 ─ 40       goto #2                                       │
32 5 ─  0 %8  = Base.getfield(_3, :y)::Float64                │╻  getproperty
   │    2 %9  = Base.eq_float(%8, 0.0)::Bool                  ││╻  ==
   └──  0       goto #7 if not %9                             │
   6 ─ 40       goto #2                                       │
34 7 ─  0 %12 = Base.getfield(_2, :x)::Float64                │╻  getproperty
   │    0 %13 = Base.getfield(_2, :y)::Float64                ││
   │   20 %14 = Base.div_float(%12, %13)::Float64             │╻  /
   │    0 %15 = Base.getfield(_3, :x)::Float64                │╻  getproperty
   │    0 %16 = Base.getfield(_3, :y)::Float64                ││
   │   20 %17 = Base.div_float(%15, %16)::Float64             │╻  /
   │    0 %18 = %new(Main.Point, %14, %17)::Point             │╻  Point
   └──  0       return %18                                    │
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, [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.
 • %2 = invoke error(::String)::Union{}
   ↩

julia> using Cthulhu

julia> descend(/ₚ, (Point,Point); inline_cost=true)

/ₚ(a::Point, b::Point) in Main at untitled-e25fcb34ce5237c6bb8376cca04cf1b2:24

│ ─ %-1 = invoke /ₚ(::Point,::Point)::Point

26 1 ─ 0 goto #3 │

28 2 ┄ 0 invoke Main.error("/ₚ: division error detected !"::String)::Union{}

└── 0 unreachable │

31 3 ─ 0 %4 = Base.getfield(_2, :y)::Float64 │╻ getproperty

│ 2 %5 = Base.eq_float(%4, 0.0)::Bool ││╻ ==

└── 0 goto #5 if not %5 │

4 ─ 40 goto #2 │

32 5 ─ 0 %8 = Base.getfield(_3, :y)::Float64 │╻ getproperty

│ 2 %9 = Base.eq_float(%8, 0.0)::Bool ││╻ ==

└── 0 goto #7 if not %9 │

6 ─ 40 goto #2 │

34 7 ─ 0 %12 = Base.getfield(_2, :x)::Float64 │╻ getproperty

│ 0 %13 = Base.getfield(_2, :y)::Float64 ││

│ 20 %14 = Base.div_float(%12, %13)::Float64 │╻ /

│ 0 %15 = Base.getfield(_3, :x)::Float64 │╻ getproperty

│ 0 %16 = Base.getfield(_3, :y)::Float64 ││

│ 20 %17 = Base.div_float(%15, %16)::Float64 │╻ /

│ 0 %18 = %new(Main.Point, %14, %17)::Point │╻ Point

└── 0 return %18 │

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, [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.

• %2 = invoke error(::String)::Union{}

↩

Juliaコンパイラが扱う中間表現としての /ₚ が表示されています。ここで、左から3列目の 0/2/40 といった数字の列が各SSAステートメントに対応するインラインコストを表しています。アノテーションが与えられていない場合、Juliaコンパイラはこれらのインラインコストの総和が 100 以下の関数呼び出しをインライン展開し、それ以外の場合はインライン展開を行いません。今回は総和が 124 になってしまっているので、 /ₚ はインライン展開されなかったわけですね。

もう少し細かくみてみましょう。よくみてみると、 goto #2 という2つの goto 文にそれぞれ 40 という高いインラインコストが割り当てられているのがわかると思います。この2つの goto #2 は元のプログラム中の @goto diverror に対応します。それらの goto はコントロールフローに対して逆方向に向かうジャンプ命令です。こうした逆方向ジャンプは通常ループの存在を意味しますが、ループは多くの場合で「複雑な」計算をするので高いインラインコストが割り当てられており、その結果として /ₚ はインライン展開されなかったというわけです。

Juliaコンパイラのインラインコストモデルのロジックは base/compiler/optimizer.jl に記述されており、各ビルトイン関数のコストは base/compiler/tfuncs.jl で定義されています。特に上で紹介した逆方向ジャンプ命令に関するヒューリスティックは具体的にはここに記述されているロジックに対応しています。

Cthulhu.jl を用いながら色々なコードに対してインラインコストモデルがどのように振る舞うかを調べてみると他にも面白い発見があるかもしれません。

まとめ

この記事では、インラインとは何かというところから、Juliaプログラマが利用可能なインラインアノテーション、そしてJuliaコンパイラのインラインコストモデルの簡単な中身をご紹介しました。

他にも、Juliaコンパイラの実装という観点ではインライン展開の可否は定数伝播と密接に関わっているなど、まだまだ興味深いトピックは尽きないのですが、今回は入門編ということでここで切り上げようと思います。以下に簡単なおさらいをまとめてこの記事を締めさせていただきます:

インライン展開は奥が深い: 多くのコンパイラはお手製のコストモデルでインライン展開の是非を決定している
インライン展開の挙動を変えたい時は、アノテーションが使える
- 対象の関数を「所有」している場合は、定義もとアノテーションを使う
- 対象の関数を「所有」していない場合、Julia v1.8以上であれば、呼び出しもとアノテーションを使うことができる
期待通りにインライン展開がされていない場面に遭遇したら、積極的にissueを上げるとコンパイラの発展につながるかもしれないので是非

リンク

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

以下のページを参照:
- https://stackoverflow.com/questions/1932311/when-to-use-inline-function-and-when-not-to-use-it
- https://softwareengineering.stackexchange.com/questions/357084/when-do-function-call-costs-still-matter-in-modern-compilers
↩︎
このコードはこの LuaJIT コンパイラのドキュメントから着想を得て作成しました。↩︎
こうして構造体をスカラー値で置き換えることでアロケーションを削減する最適化技術を SROA – Scalar Replacement of Aggregates と呼びます。↩︎
JVMコンパイラの多くは優れたエスケープ解析を実装しています。その中にはより効果的なSROAを行うために、関数呼び出しの引数がエスケープするかしないかによってコストモデルを調整しているものもあるそうです: https://www.usenix.org/legacy/events/vee05/full_papers/p111-kotzmann.pdf ↩︎
@benchmark compute(100_000_000) がアロケーションを報告してないことに気がついたかもしれません (Memory estimate: 0 bytes, allocs estimate: 0.)。これは @benchmark や @allocated が意図的にスタックアロケーションを報告していないためです。 Point はイミュータブルな形として定義されているため、Juliaコンパイラは Point 型のオブジェクトをヒープ領域ではなくスタック領域にアロケーションする最適化を行います。つまり、 Point 型オブジェクトに確保されたメモリ領域は関数呼び出しが終わってすぐに解放され、そのため GC が後からそのメモリ領域を解放する必要はありません。 /ₚ がインラインされない場合、 Point 型オブジェクトはメモリ上のどこかには存在しないといけないため、依然としてスタックメモリ領域にデータを読み書きする必要はありますが、そうした計算はヒープ領域へのアロケーションと比べた時に非常にチープです。以上が compute(100_000_000) が後で紹介するインライン展開による最適化がなくても、それなりに良好なパフォーマンスを示していた理由です。
賢明な読者の方はここで、 Point をミュータブルなオブジェクトとして定義したらどうなるのか気になったかもしれません。現在のところJuliaはミュータブルなオブジェクトをスタック領域にアロケーションすることはできません。また、たとえ /ₚ がインラインされ、 SROA が Point オブジェクトを取り除ける可能性があったとしても、現在のところJuliaコンパイラのハイレベル最適化パス及びLLVMのいずれもうまくそうしたミュータブルなアロケーションを取り除くことはできません。この場合 Point オブジェクトのアロケーションはネストしているため、こうしたケースを最適化するためには、Juliaコンパイラのハイレベル最適化パイプラインのいずれかの段階で何らかのエイリアス解析が必要なのです。
また現在我々はそうしたより発展的なメモリ最適化を目指すプロジェクトに取り組んでいます。もし興味のある方は以下の HackMD ドキュメントを見てみてください:
- Julia Escape Analysis Project
- Intensive Prior Research on Escape Analysis
またウィークリーでミーティングを行っていますので、もし参加してみたい方がいらっしゃいましたらお気軽に Julia Slack にてご連絡ください。↩︎

いわゆるモンキーパッチと呼ばれるテクニックです。モンキーパッチの具体的な方法は言語やフレームワークに依存し様々です。 Juliaの場合、 Core.eval を利用することで、定義ずみのモジュールのコンテクストでコード実行を行うことができるため、それを用いてモンキーパッチすることができます。今回であれば、モジュール A が /ₚ を定義しているとき、以下のようにすれば定義もとアノテーション @inline とともに新しい /ₚ の定義を上書きできます:

Core.eval(A, quote
    @inline a::Point /ₚ b::Point = begin
        # error pass
        if false
            @label diverror
            error("/ₚ: division error detected !")
        end
        # do some error checks
        iszero(a.y) && @goto diverror
        iszero(b.y) && @goto diverror
        # do the main computation
        Point(a.x/a.y, b.x/b.y)
    end
end)

Core.eval(A, quote

@inline a::Point /ₚ b::Point = begin

# error pass

if false

@label diverror

error("/ₚ: division error detected !")

end

# do some error checks

iszero(a.y) && @goto diverror

iszero(b.y) && @goto diverror

# do the main computation

Point(a.x/a.y, b.x/b.y)

end

end)

↩︎

Recruit Tech Blog

タグから見つける

タグから見つける

職種を選択

事業領域を選択

インライン展開入門

インライン展開とは

具体例で見てみるインライン展開

インラインコストモデル

Juliaプログラマが利用可能なインラインアノテーション

定義もとアノテーション definition-site annotation

呼び出しもとアノテーション call-site annotation

どんなときにアノテーションを考えるべきか

おまけ: Juliaコンパイラのインラインコストモデルを覗いてみる

まとめ

リンク