Julia 0.5-dev の Generator に触れてみた。 #Julia

前置き

GW いかがお過ごしでしょうか？
私は、色々あって超暇なのでCNNとかRNNとかいろいろ実験しようと思ってた¹のですが、体調崩して連休の半分くらい寝てました²。

ということでちょっとリハビリに、Julia の HEAD（2016/05/06 13:00 時点の最新 v0.5.0-dev+3922）をインストールして試してみました。
その中で「これ Julia に欲しかった！」が実装されていたので紹介します。

Generator 式

Julia には、Python に類似の リスト内包表記 があります：

julia> ls0 = [i for i in 1:10000]
10000-element Array{Int64,1}:
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
     ⋮
  9992
  9993
  9994
  9995
  9996
  9997
  9998
  9999
 10000

julia>

Python では、この [〜] を (〜) に置き換えると、リスト（配列）ではなく generator オブジェクトが生成されます。これは実際の値をその都度算出するイテレータです。
Julia に、この機能が実装されます（ました）。

julia> it0 = (i for i in 1:10000)
Base.Generator{UnitRange{Int64},##1#2}(#1,1:10000)

julia> take(it0, 10)
Base.Take{Base.Generator{UnitRange{Int64},##1#2}}(Base.Generator{UnitRange{Int64},##1#2}(#1,1:10000),10)

julia> collect(take(it0, 10))
10-element Array{Int64,1}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

julia>

何に使えるのか。
例えば、約半年前に Julia Advent Calendar 2015 で実験した、「たくさんある中からフィルターかけてほんの一部のみ抽出」する場合に、高いパフォーマンスが得られます。

julia> @time collect(take(drop(filter(isprime,1:10000),10),10))
  0.000516 seconds (7.93 k allocations: 143.844 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia> @time collect(take(drop(filter(isprime,it0),10),10))
  0.000051 seconds (128 allocations: 5.313 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia>

これは、通常のRangeオブジェクトが、filter()関数で処理するときに「全要素をチェックして条件を満たしたものを集めたリスト（配列）」を作ってしまう（10000件チェックして要素数1229のリストが作られる）のに対して、Generator オブジェクトを利用した方は「必要な要素のみ処理する仕組み」になっている（結果としてfilter時は71件だけチェックし20件だけ次の処理に渡している）からです³。

ただ注意点として、以下のようにインラインで記述しても、期待したパフォーマンスが得られません。

julia> @time collect(take(drop(filter(isprime,(i for i in 1:10000)),10),10))
  0.142189 seconds (133.55 k allocations: 5.504 MB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia>

これは、(〜for〜in〜) を記述する度に毎回 Generator オブジェクトが生成されるのですが、その型が（型パラメータレベルで）毎回異なるものになるので、イテレーションの基本となる start() next() done() 各関数のJITコンパイルがその都度発生するためです（だと思われます）。
一度変数に入れておいて（且つ一度少しイテレーションを実行するなどして）からでないと（さらにそれを使い回すようにしないと）、最適化された結果を利用出来ない、ということですね⁴。

`Generator` 型

※この節の内容は、現在の Julia-HEAD(v0.5.0-dev+3922) に基づいています。将来的には仕様変更となる可能性があります。

前節を見ていただけると分かる通り、Generator 式で得られるオブジェクトは Generator 型のオブジェクトのようです。


julia> ?Base.Generator
  Generator(f, iter)

  Given a function f and an iterator iter, construct an iterator that yields
  the values of f applied to the elements of iter. The syntax f(x) for x in
  iter is syntax for constructing an instance of this type.

julia>

ソース（オリジナルから抜粋）：

generator.jl

"""
    Generator(f, iter)
Given a function `f` and an iterator `iter`, construct an iterator that yields
the values of `f` applied to the elements of `iter`.
The syntax `f(x) for x in iter` is syntax for constructing an instance of this
type.
"""
immutable Generator{I,F}
    f::F
    iter::I
end

# 《中略》

start(g::Generator) = start(g.iter)
done(g::Generator, s) = done(g.iter, s)
function next(g::Generator, s)
    v, s2 = next(g.iter, s)
    g.f(v), s2
end

# 《後略》

こんな感じの実装です。
先述の実験で書いた、lazy.jl の Lazy 型や LazyComprehension 型と同様、（この辺だけを見れば）至ってシンプルな実装です。

あと、これを直接利用すれば、Generator式を使わなくても Generatorオブジェクトは作れますね。

julia> it1 = Base.Generator(Base.identity, 1:10000)
Base.Generator{UnitRange{Int64},Base.#identity}(identity,1:10000)

julia> collect(take(it1, 10))
10-element Array{Int64,1}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

julia> @time collect(take(drop(filter(isprime,it1),10),10))
  0.000055 seconds (128 allocations: 5.313 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia>

うん、生成されるオブジェクトの型パラメータ以外はまったく同様の結果ですね。
しかも。一度↑を実行すると、Generatorオブジェクトをインラインで生成してもほぼ同等のパフォーマンスが得られます↓。

julia> @time collect(take(drop(filter(isprime,Base.Generator(Base.identity, 1:10000)),10),10))
  0.000064 seconds (130 allocations: 5.375 KB)
10-element Array{Int64,1}:
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

julia>

同じ型パラメータを持つ GeneratorオブジェクトならばJITコンパイルが有効に働いて最適化された結果が利用されるので、期待したパフォーマンスが得られる、というわけですね⁵。

おまけ：関数の型

Julia v0.5 からは、関数（無名関数含む）に個別の型が設定されるようです。

julia> it0.f
(::#1) (generic function with 1 method)

julia> typeof(it0.f)
##1#2

julia> supertype(typeof(it0.f))
Function

julia>

#1 というのが、(i for i in 1:10000) という Generator の関数（の文字列表現）。
##1#2 が、その関数の型（の文字列表現）。その super type⁶ は Function。
ついでに #1 というのは、無名関数につけられた仮の名前のようなものみたいです。

isleaftype(typeof(it0.f)) が true になるので、本当に個別の型のようです。abstract でないので、継承はできません⁷。また関数型言語とかでよくある「引数と戻り値の型で関数の型を表現する」というような仕組みでもない模様です。
ただ無名関数（ラムダ式で定義された関数）にも型が設定される⁸ので、JITコンパイルの対象になるようです。それもパフォーマンス向上の一役を担っているようです。

おまけ2：Julia HEAD のインストールについて

Julia HEAD は、以前にも homebrew-julia でインストールしていました（環境は Mac OSX 10.11.4 です）。
今回も以下の手順でインストールしました。時間がかかった以外は特に難しいことはありませんでした。

$ brew update
$ brew reinstall julia --HEAD --with-accelerate
$ julia --version
julia version 0.5.0-dev
$ julia
               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.5.0-dev+3922 (2016-05-05 18:51 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit e0e93fc* (0 days old master)
|__/                   |  x86_64-apple-darwin15.4.0

julia>

インストール中のログを消してしまったのですが、openblas-julia, suite-sparse-julia, arpack-julia といった依存パッケージが、 El Capitan 用のビルド済バイナリがインストールされたような気がします。
問題が起きたら、この辺をまたソースから入れ直すとかしないとダメかも。今のところは問題なく動いているので様子見です。

参考：

あと勉強会の資料作りとか進捗ダメです。。。 ↩
ちなみに昨日はBlu-rayにダビングしてあった5年前の某アニメを一気見してました。ヴィクトリカかわいー ↩
ほぼ前回記事からのコピペ。 ↩
この辺、将来的にどうにかうまく最適化されるようにならないかな、と淡い期待。 ↩
正式リリース時、あるいは将来的なバージョンアップで、こんな小手先テクニックを使わなくて済むようになることを願います。。。 ↩
ちなみに super type を返す関数も v0.4 までの super() が deprecated になって新しく supertype() という関数になるみたいです。どんどん仕様が変わるー ↩
isleaftype() は、その型が「具象型（abstract でない型）」かどうかを返す関数。Julia では abstract でない型は継承出来ません（＝subtype を作れません＝type tree では必ず leaf になる）。 ↩
それに加えて「全ての関数は generic になる」という仕様変更もあるようです。 ↩

Julia 0.5-dev の Generator に触れてみた。

前置き

Generator 式

Generator 型

おまけ：関数の型

おまけ2：Julia HEAD のインストールについて

参考：

`Generator` 型