日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

より清浄な Stream Fusion
小林 友明

Oleg Kiselyov

昨今，データを中心としたプログラミングパラダイムの影響力が高まっている．ストリーム処理はその一例であり，高水準かつ高性能なストリームライブラリを実現することは重要な課題である．strymonas はステージ化によってこの課題に取り組むライブラリであり，map，ﬁlter，fold 等のコンビネータからなるパイプラインに stream fusionなどの最適化を施し，命令型の高効率なストリーム処理のコードを生成する．特に，これによって生成されるコードが手動で最適に記述されるものと遜色ないことは注目に値する．しかしながら，strymonas には，コード生成に用いる中間言語の汎用性や拡張性が低いことと，ﬂat map 後に zip するパイプラインに対して例外的に低品質のコードを生成してしまうことの問題があった．本研究ではこれらの問題を解決し，高水準かつ高性能なストリームライブ
ラリの基盤を再建した．

の Seq のような関数型のストリームライブラリも存

1 はじめに在する．このようなライブラリによる処理は，map，昨今の情報処理では人工知能や IoT のブームに起

ﬁlter，fold(reduce) などの演算子 (コンビネータ) を因して，データを中心としたプログラミングパラダイ

組み合わせて記述される．そのため，処理が複雑にムが大きな役割を担っている．ストリーム処理はそのなっても記述や読解は比較的容易なままであるが，サようなパラダイムの 1 つであり，ストリームという有ンクを代表とした抽象化のオーバーヘッドを多分に含限長あるいは無限長の系列データを逐次的に処理すんでしまうため，一般に命令型のストリームライブラることを意味する [1]．逐次的な処理であるストリー

リよりも効率が悪いという問題をもつ．

ム処理は万能ではないが，該当する場合には低レイテ

このようなジレンマの解決方法として，関数型のスンシでワーキングメモリが定数サイズ (コンスタント

トリームライブラリに stream fusion を施すことが効

メモリ) の効率的な処理が期待でき，これらの特性か果的であると知られている [1]．広義の stream fusion

ら組込みシステムや IoT などでよく利用されている．

は，中間データ構造を使わないような計算にストリー

その汎用性や実用性の高さから，ストリーム処理

ム処理を変換する最適化であり [8]，Haskell の stream-のライブラリは様々なプログラミング言語で提供さ

fusion [4] [3]，OCaml の streaming [5]，Java SE 8 のれており，その多くは命令型か関数型の API を持つ．

Streams API(Java 8 streams) などで利用されている．

例えば命令型のストリームライブラリとしては，C

しかしながら，このような stream fusion を備えたラの FILE や C++の input iterator などを挙げられる．

イブラリでも，タプルやオプション型の値といった入このようなライブラリによる処理は命令的で効率的だ

力データによらずサイズが固定の中間データ構造やクが，処理が複雑な場合の記述や読解が困難という問題

ロージャによるオーバーヘッドは含むため，依然としてをもつ．その一方で，Haskell の Data.List や OCaml

効率に改善の余地がある．strymonas [7] [8] は，ステージ化を用いた部分評価でこの問題に取り組むストリー

Highly Purifying Stream Fusion.
Tomoaki Kobayashi, Oleg Kiselyov, 東北大学, Tohoku
University.

ムライブラリであり，zip や ﬂat map(concatMap) な
どの高機能な演算子を API に含みながらも殆どのパイプラインであらゆる中間データ構造やクロージャな他のもので代替 (第 4. 2 節)

しのストリーム処理ができるように stream fusion を

2.2. コードを破壊しない安全なクロージャ変換と行い，人間が効率的になるよう慎重に記述した命令型

クロージャ周りの関数をインライン展開する

ストリーム処理と同等の性能を達成する．その原理

正規化のフェーズを追加 (第 4. 3 節)

は，関数型ストリーム処理のパイプラインを部分評価

本研究の貢献は，strymonas の抱えていた上述のして最適化されたストリーム処理のコードを生成す問題を系統的に解決し，以下の事項を実現したことでることにあり，生成されるコードがコンパイラによらある．

ず良い効率をもつことや安全であることは静的に保証される．

• zip と ﬂat map を含んだ複雑なパイプラインでも生成されるコードは型安全かつ手書きの命令

このように strymonas は真に高水準かつ高性能な的なコードと同等の性能を発揮し，効率の良いストリームライブラリと呼ぶに相応しいものの，次のOCaml のストリームライブラリ streaming [5] の問題を抱えていた．

約 5 - 25 倍の性能をベンチマークで達成

1. コード生成に用いる中間言語の汎用性や拡張性が低い

2. ﬂat map されたストリームの対に zip を行うパ
イプラインから生成されるコードが，以下の 2 つを含んでしまう2.1. 固定サイズの中間データ構造
2.2. クロージャ問題 1. は，より高度な最適化や新しい規則に基づい• API で表現可能な任意のパイプラインをあらゆる中間データ構造なしに実現: 省メモリ・コンス
タントメモリ・GC 未要求なストリーム処理• 元 の strymonas の API を 拡 張: map accum，
drop，drop while，etc．
• 中間言語や最適化機能をコード生成機能から分
離: OCaml や Scala だけではなく，C や LLVMなどのコード生成も視野にたコード生成などの機能追加を困難にする．問題 2.

これ以降，本研究の問題解決による改善がなされは，該当する場合の生成コードに対して例外的に box

る前の strymonas を strymonas v1，なされた後の化・自動メモリ管理 (GC)，クロージャの生成・呼び

strymonas を strymonas v2 と呼称する．

出しなどからなるオーバーヘッドを付加したり，低水

本論文の構成は以下のとおりである．第 2 節では，準な言語を対象としたコード生成を困難にしたりす

strymonas の概要と基本的な使用方法，また応用的る．なお，ストリーム処理で ﬂat map が使用されるなストリーム処理の記述例について解説する．第 3 節

場面はそれほど多くないように思えるが，strymonas

では，本研究の改善によってもたらされた一部のストの ﬁlter は ﬂat map によって表現されていたため，リーム処理に対する strymonas の生成コードの変化

zip (stream1 |> filter pred1 )(stream2 |> filter pred2 )|> . . .
...
| > fold f zと，種々のベンチマークをとった結果を示す．第 4 節
では，strymonas v2 の実装について，中間言語の洗練化，残留した固定サイズの中間データ構造の除去，
クロージャの除去の観点から説明する．第 5 節では，のような実用性の高いと考えられるパイプラインも，関連研究を紹介する．第 6 節では，本研究のまとめ

この対象となってしまっていた．

と今後の課題を議論する．

そこで，我々はこれらの問題を解決するのために，それぞれに対して次のような手段をとった．

2 strymonas の概要

1. ストリーム処理の基本構造を再確認し，中間言語

本節では，strymonas の概要とその使い方を説明を再設計 (第 4. 1 節)

する．strymonas の実体は，BER MetaOCaml [6] や

2. ﬁlter を ﬂat map の表現から分離し (第 4. 1 節)，

LMS(Lightweight Modular Staging [12]) を利用した

2.1. 要求される固定サイズの中間データ構造を

Scala などのメタ言語にライブラリとして埋め込まれ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

type 'a stream
type +'a cde (* 抽象型 *)type 'a emit = ('a → unit cde) → unit cde(* 生 産 者 *)val of_arr : 'a array cde → 'a stream
val iota: int cde
→ int stream
val from_to : ?step:int → int cde → int cde → int stream
val unfold : ('z cde → unit cde → ('a cde) emit) → 'z cde → 'a stream(* 変 換 者 *)val map
val flat_map
val filter
val takeval map_accum

val drop
val drop_while
val zip_with: ('a cde → 'b cde)→ 'a stream → 'b stream: ('a cde → 'b stream) → 'a stream → 'b stream: ('a cde → bool cde) → 'a stream → 'a stream: int cde → 'a stream → 'a stream: ('z cde → 'a cde →('z cde → 'b cde → unit cde) → unit cde) →'z cde → 'a stream → 'b stream: int cde → 'a stream → 'a stream: ('a cde → bool cde) → 'a stream → 'a stream: ('a cde → 'b cde → 'c cde) →('a stream → 'b stream → 'c stream)(* 消 費 者 *)val fold: ('z cde → 'a cde → 'z cde) → 'z cde → 'a stream → 'z cde
val iter: ('a cde → unit cde)→ 'a stream → unit cde

図1

strymonas のユーザー用高水準 API

た DSL(Embedded DSL，EDSL) である．元々採用る．例えば，引数で指定された配列に対してその配列されていたメタ言語は上述の 2 言語のみであったが，のストリームを生産する of arr(6 行目) や，ストリー

現在 Idris，Agda，C#などに広がってきている．

ムの生産で汎用的に用いられる unfold(9 行目) など

strymonas v2 の実装が完了しているのは本論文執が該当する．

筆時点で BER MetaOCaml によるもののみであり，変換者とは，受け取ったストリームを異なるスト

本論文では簡単のため，これ以降特に断らない限り

リームに変換する関数のことであり，パイプラインのメタ言語を BER MetaOCaml，対象言語を OCaml

中間で用いられる．これには，引数で与えられる関数とした，(BER Meta)OCaml 版 strymonas についてを使ってストリームの各要素から計算された値を新説明する．なお，メタ言語が BER MetaOCaml のたなストリームの要素とするよう変換を行う map(12strymonas で生成対象となるのは基本的に OCaml の行目) や，ストリームから指定条件を満たす要素のみ

コードであるが，C のような低水準の言語を対象とを抽出する ﬁlter(14 行目) などが当てはまる．

したコード生成にも対応し始めている．

消費者とは，与えられたストリームを処理して結果の値を返す関数のことであり，パイプラインの末尾で

2. 1 基本用いられる．特に，strymonas の消費者は，結果の値

図 1 に，strymonas の API を示す．strymonas が自体ではなく結果の値を計算するコードを返す．これAPI で提供する演算子は一般の高水準ストリームラには，ストリームの各要素を用いた反復的な計算のイブラリと同様に生産者，変換者，消費者の 3 種類

コードを生成する iter(foreach，26 行目) や，逐次処に分類される．

理のコード生成に対して汎用的に用いられる fold(25生産者とは，引数の値を用いてストリームを生産する関数のことであり，パイプラインの先頭で用いられ行目) などがある．
変換者や消費者の多くは高階関数であり，そのよう

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

val letl : 'a cde → (('a cde → 'w cde) → 'w cde) (* 局 所 let *)val glet : 'a cde → 'a cde(* 大 域 let(let 挿入) *)val seq : unit cde → 'a cde → 'a cde
val unit : unit cde
val cond : bool cde → 'a cde → 'a cde → 'a cde(* if−then−else *)(* Booleans *)val bool : bool → bool cde
val not : bool cde → bool cdeval (&&) : bool cde → bool cde → bool cdeval ( | | ) : bool cde → bool cde → bool cde(* Integers *)val int: int → int cde
val imin : int cde → int cde → int cdeval (mod) : int cde → int cde → int cdeval (+) : int cde → int cde → int cdeval (−) : int cde → int cde → int cde...
val (<) : int cde → int cde → bool cdeval (>) : int cde → int cde → bool cdeval (=) : int cde → int cde → bool cdeval (≤) : int cde → int cde → bool cdeval (≥) : int cde → int cde → bool cde...
(* Floating points *)val float: float → float cdeval truncate : float cde → int cdeval (+.): float cde → float cde → float cdeval (−.): float cde → float cde → float cde...
(* Others *)val pair : 'a cde → 'b cde → ('a * 'b) cde
val int_array:
int array → int array cde
val float_array : float array → float array cde...

図2

演算子の引数記述用 EDSL

な場合にはユーザーがストリームの変換・消費方法を

コードを生成し，生成されたコードを処理系に渡す引数の関数で指定することになる．この引数の関数

ことで実際のストリーム処理が実行される．パイプ

は，ストリームの要素が取り出される毎にそれを引数ラインを構築する演算子の引数には，図 1 の 2 行目として発火される処理を表すため，Yacc などのパー

記載の cde 型の値やその上の演算を与えることにな

サージェネレータに倣いセマンティックアクションとる．cde 型は対象言語のコードを表現する抽象型であ呼ぶことにする 1 ．

り，この型の値やその上の汎用的な演算は，図 2 に示

ユーザーが図 1 の演算子を組み合わせてパイプラ

す専用の EDSL を用いて記述される．次に，図 1 のインを作ると，strymonas はそれを評価することでAPI と図 2 の EDSL を利用した，基本的なパイプラ

stream fusion を代表とする種々の最適化が施された

インの記述例と生成コードを示す．

iota を用いて 1 以上の整数からなる無限ストリー
1 パーサージェネレータにおけるセマンティックアク
ションは，定義された構文の規則に対応して構文解析
時に呼び出される関数のことである．

ムを生産し，map によってその各要素が 2 倍された
正の偶数のストリームに変換し，さらに take を用い

て始めの 10 個の要素のみからなるストリームに変換

プラインを簡潔に記述するため，図 1 の API で抽象

し，最後に fold によって要素を加算して消費するパ化されている cde 型を

イプラインは，
iota (int 1)| > map (fun e → int 2 * e)
| > take (int 10)| > fold (+) (int 0)

type 'a cde= 'a codeと具体化して，. <> . や . ∼ といった BER MetaO-

Caml のステージ化注釈を部分的に直接扱う．. <> .
は OCaml の型付きコードテンプレートを生成すると記述できる．このパイプラインは演算子の引数が演算子で，. ∼ は新しいコードテンプレートの一部に

図 2 の EDSL で記述されているため，通常の OCaml

既存のコードテンプレートを展開する演算子であり，のストリームライブラリによって記述されているパイ

OCaml のコードテンプレートに付与される型が code

プラインと見かけ上ほとんど区別がつかない．次に，型である．

このパイプラインから生成されるコードを示す．
let lv_1 = ref 0 in
let lv_2 = ref 1 inlet lv_3 = ref 0 in
while (! lv_3) ≤ 9 doincr lv_3;
let lv_4 = ! lv_2 inincr lv_2;
let lv_5 = 2 * lv_4 in
lv_1 := ((! lv_1) + lv_5)
done;! lv_1

この生成コードは抽象化によるオーバーヘッドがあるような処理を含まず，手書きで高効率になるように記述されたストリーム処理と遜色ない．

ここでは典型的なストリーム処理の例として，与えられたログファイルに grep のような検索をかけ，指定されたキーワードを含む行のみ行番号を添えて出力する処理を取り上げる．この処理をストリーム処理として表現するには，与えられたログファイルの各行を要素とするストリームを生産し，指定語句を含む要
素で ﬁlter することを考えればよい．
まずは，ファイル名を受け取ってそのファイルの各行を要素とするストリームを生産する関数 of ﬁleval of_file : string → string streamを用意する．この関数は strymonas の API では提以上のように演算子の引数を図 2 の EDSL を利用供されていないが，次のように unfold を用いて容易して記述すると，ユーザーに BER MetaOCaml 特有に実装できる．なお，of ﬁle は種々の副作用を扱ってのステージ化注釈の存在を隠蔽したままコード生成がいるがこれは対象コード上での話であり，of ﬁle 自体できるようになったり，生成コードに部分静的なデーは純粋な関数である．

タを利用した高度な最適化をかけられるようになる
といった恩恵を受けられる．ただし，外部ライブラリを利用した OCaml 特有の処理を行うコードを生成する場合などには，図 2 の EDSL は BER MetaOCamlのステージ化注釈を完全に隠蔽することはできない．
第 2. 2 節ではそのような場合のパイプラインの記述について記述する．

2. 2 応用

let of_file filename =let step ch ondone = fun k → .<try
let line = input_line .∼ch in.∼(k .<line>.)with End_of_file →(close_in .∼ch; .∼ondone)>. in
let z = .<open_in filename>. in
unfold step z

一般に，unfold とは状態遷移関数 step と初期状態

本節では，前節で紹介した strymonas の機能を用

z の順序対 (step, z) で表現されるストリームを生産

いて，より実用的なストリーム処理を行うパイプライ

する関数のことである．このような順序対による表現

ンの記述方法について説明する．ただし，OCaml のは数学的なストリームの定義で用いられ，各々次のよライブラリを利用した処理のコードを生成するパイ

うなインターフェースを持つ．

ているかどうか判定する関数をステージ化した関数
val step : 'z → ('a * 'z) optionvalz : 'zcontainval contain : string cde → string → bool cde

ここで，’a はストリームから取り出される要素のを用意する．部分文字列の判定処理には OCaml の型に相当し，step は現在の状態 zi を与えらえると，

標準的なライブラリで提供される Str モジュールの関そのときの要素 xi と次の状態 zi+1 を返すことでス数を使えるため，この関数は次のように書ける．

トリームを状態遷移させ，要素がなくなった場合はNone を返して停止させる．
しかしながら，strymonas の unfold には，生産されるストリームの状態遷移関数 step を命令的かつCPS で表現し，これと初期状態 z をステージ化したものが与えられる．これらは次のインターフェースをもつ．
val step : 'z cde → unit cde → ('a cde) emitvalz : 'z cde

let contain s1 s2 = .<let re = Str.regexp_string s2 intry
ignore (Str.search_forwardre .∼s1 0);
true
with
| Not_found → false>.

以上で定義した of ﬁle 関数と contain 関数に加え，読み込み対象となるログファイルの名前 f ilename とunfold の第 1 引数となるのが step であり，上記のコードにおける step は，ファイルとしてのストリー
ムの状態を表す入力チャネルのコード ch と，停止時に起こなう終了処理の付随的な一部を表すコード

ondone を受け取って，継続 k を引数にもつ CPS の関数 (図 1 の 3 行目記載の emit 型の値) を返す関数
である．この継続 k はパイプラインで後続する変換
者と消費者のセマンティックアクションを合成したセマンティックアクションをステージ化したものである
ため，of ﬁle の生産するストリームの step 関数が返指定語句 keyword を用いて，上述のストリーム処理は次のように書くことができる．
zip_with pair(iota (int 1))(of_file f ilename)| > filter (fun e →contain .<snd .∼e>. keyword)| > take (int 10)| > iter (fun e →.<Printf.printf "%d: %s\n"(fst .∼e) (snd .∼e)>.)iota でファイルの行数を表現する 1 以上の数値のス

す CPS の関数は，input line によって ch が保持するトリームを生成し，これを of ﬁle で生成されたファ

入力チャネルからの 1 行分の読み込みと読み込み位

イルのストリームと zip with によって組み合わせる

置の更新に挑戦し，成功した場合には読み込まれたことでタプルのストリームを生成し，keyword の条

値 line を用いて引数の k が保持する処理を行い，失件を満たしている要素のみ ﬁlter で抽出し，それらを敗 (ファイル終端に到達) した場合にはチャネルを閉

iter に渡して標準出力に書き出すことで全体の処理はじたり ondone による付随的な終了処理を行うコード構成されている．ただし，あまりにも大量の行が出を生成するように定義されている．

力されると不便なので，take によって出力行数が最また，unfold の第 2 引数となるのが z であり，上大 10 件となるように制限した．このパイプラインに記のコードでは，of ﬁle の引数で指定されたファイル

よって生成されるコードを次に示す．

の先頭を指している入力チャネルを表すコードとして

let lv_1 = 10 − 1 inlet lv_2 = ref 1 inlet lv_3 = open_in f ilename inlet lv_4 = ref true inlet lv_5 = ref 0 in

定義されている．これが step 関数に ch として渡され利用される．
次に，第 1 引数中に第 2 引数の文字列が含まれﬁlter raw，map raw’，fold raw という関数を利用す
while ((! lv_5) ≤ lv_1) && (! lv_4) do
let lv_6 = ! lv_2 inincr lv_2;(try
let line_7 = input_line lv_3 in
if
let re_8 = Str.regexp_string
keyword intry
ignore (Str.search_forward
re_8 (snd (lv_6, line_7)) 0);
true
with
| Not_found → falsethen(incr lv_5;
Printf.printf "%d: %s\n"(fst (lv_6, line_7))(snd (lv_6, line_7)))
else ()
with| End_of_file → (close_in lv_3;
lv_4 := false))
done

このコードの品質はそれほど悪くないものの，主に次の 2 点で大きな改善の余地をもつ．

1 つ目は，ループの度に keyword から毎回同じ正規表現 Str.regexp string keyword を生成していることである．これは正規表現の生成と let 束縛を大域的な位置で行うように移動することで解決でき，そのためには図 2 の EDSL で提供されている glet(2 行目)が利用できる．glet を用いて，contain 関数は次のよ
うに書き換えられる．
let contain s1 s2 =let re = glet .<Str.regexp_string s2>. in.<try
ignore (Str.search_forward.∼re .∼s1 0);
true
with
| Not_found → false>.

ることになる．
以上に基づいた新しいパイプラインは，殆ど上記のパイプラインと同様に，
zip_raw(iota (int 1))(of_file f ilename)| > filter_raw (fun (_, e2) →contain e2 keyword)| > zip_raw (from_to (int 1) (int 10))| > map_raw' snd| > fold_raw (fun (e1, e2) →.<Printf.printf "%d: %s\n".∼e1 .∼e2>.)と記述される．このパイプラインによって生成されるコードを次に示す．
let lv_8 = Str.regexp_string keyword inlet lv_1 = ref 1 inlet lv_2 = ref 1 inlet lv_3 = open_in f ilename inlet lv_4 = ref true inwhile ((! lv_1) ≤ 10) && (! lv_4) do
let lv_5 = ! lv_2 inincr lv_2;(try
let line_6 = input_line lv_3 in
if
try
ignore (Str.search_forward
lv_8 line_6 0);
true
with
| Not_found → false
then
let lv_7 = ! lv_1 in(incr lv_1;
Printf.printf "%d: %s\n" lv_5 line_6)
else ()
with| End_of_file → (close_in lv_3;
lv_4 := false))
done

このコードは上記の 2 点の改善だけではなく 10 −1 が 9 に丸め込まれる最適化が行われていたりするな
ど，手書きで高効率になるように記述されたストリー

2 つ目は，zip with のセマンティックアクションがム処理とそれほど遜色ない品質に改善されている. 唯

タプルを固定サイズの中間データ構造として用いる

一無駄な lv 4 という変数が除去されていないが，こように指定していることである．これを解決するにはれを解決するためには unfold を低水準の API で置き

現状 strymonas が提供する低水準の API(第 4 節，図換える必要があり，本論文では割愛する．

7) を直接利用する必要があり，具体的には zip raw，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

let s_3= ref 0in let arr_4 = arr1
in let i_5 = ref 0 in
let curr_6 = ref None in let nadv_7 = ref None in
let adv_16 () =curr_6 := None;
while ((! curr_6) = None) && (((! nadv_7) ̸= None) || ((! i_5) ≤ ((Array.length arr_4) − 1))) domatch ! nadv_7 with| Some adv_8 → adv_8 ()| None →let el_9 = arr_4.(! i_5) inincr i_5;
let arr_10 = arr2 in
let i_11 = ref 0 in
let old_adv_12 = ! nadv_7 in
let adv1_15 () =if (! i_11) ≤ ((Array.length arr_10) − 1) thenlet el_13 = arr_10.(! i_11) in
let t_14 = el_9 * el_13 in(incr i_11; curr_6 := (Some t_14))
else nadv_7 := old_adv_12 in
nadv_7 := (Some adv1_15); adv1_15 ()done inadv_16 ();let arr_17 = arr2 in
let i_18 = ref 0 in
let term1r_19 = ref ((! curr_6) ̸= None) in
let nr_20 = ref 20000000 inwhile ((! nr_20) > 0) && ((! term1r_19) && ((! i_18) ≤ ((Array.length arr_17) − 1))) dolet el_21 = arr_17.(! i_18) inincr i_18;
let arr_22 = arr1 in
let i_23 = ref 0 in
while ((! nr_20) > 0) && ((! term1r_19) && ((! i_23) ≤ ((Array.length arr_22) − 1))) dolet el_24 = arr_22.(! i_23) in
let t_25 = el_21 − el_24 inincr i_23;
match ! curr_6 with| Some el_26 →(adv_16 (); term1r_19 := ((! curr_6) ̸= None);decr nr_20; s_3 := ((! s_3) + (el_26 + t_25)))
done
done;
! s_3

図3

zip ﬂat ﬂat v1(arr1，arr2 が引数の関数)

間の平均値を計測した．また，各コードの実行前には

3 実験

GC を強制的に実行した．各パイプラインの入力には

本研究では，次の実験環境を用いて strymonas v2

以下の配列を利用したが，これらはコードの実行前にの性能を実際に評価した．
実験環境: 1.8 GHz デュアルコア Intel Core i5，8 GB

1600 MHz DDR3，macOS Catalina 10.15.4，BER
MetaOCaml N107 (native backend)
実験では ocamlopt -O2 -unsafe -nodynlink でコンパイルされたコードを 30 回実行し，実行に要した時確保しておくことで計測の時間には含めなかった．
let v= Array.init
100_000_000 (fun i → i mod 10)
let vHi = Array.init
10_000_000 (fun i → i mod 10)
let vLo = Array.init 10 (fun i → i mod 10)
let vFaZ = Array.init
10_000 (fun i → i)let vZaF = Array.init 10_000_000 (fun i → i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

let lv_11 = (Array.length arr1) − 1 in let lv_3 = (Array.length arr2) − 1 inlet lv_17 = (Array.length arr2) − 1 in let lv_4 = (Array.length arr1) − 1 inlet lv_7 = ref 0 in let lv_8 = ref 0 in let lv_9 = ref false in
let lv_10 = ref (Obj.obj (Obj.new_block 0 0)) in let lv_12 = ref (Obj.obj (Obj.new_block 0 0)) in
let lv_13 = ref 0 in let i_14 = ref 0 in
while ((! i_14) ≤ lv_4) && ((! lv_13) ≤ 19999999) && ((! lv_9) || ((! lv_8) ≤ lv_3)) do
let iv_15 = ! i_14 inincr i_14;
let el_16 = Array.get arr1 iv_15 in
let i_18 = ref 0 in
while ((! i_18) ≤ lv_17) && ((! lv_13) ≤ 19999999) && ((! lv_9) || ((! lv_8) ≤ lv_3)) do
let iv_19 = ! i_18 inincr i_18;
let el_20 = Array.get arr2 iv_19 in
let lv_21 = el_16 * el_20 inlet lv_22 = ref true inwhile (! lv_22) && ((! lv_9) || ((! lv_8) ≤ lv_3)) do
if not (! lv_9) then(let el_25 = Array.get arr2 (! lv_8) inincr lv_8; lv_10 := el_25; (); lv_12 := 0; lv_9 := true);
if ! lv_9 then(if (! lv_12) ≤ lv_11 thenlet el_23 = Array.get arr1 (! lv_12) in
let lv_24 = (! lv_10) − el_23 inincr lv_12; lv_22 := false; incr lv_13; lv_7 := ((! lv_7) + (lv_21 + lv_24))
else lv_9 := false)
done
done
done;
! lv_7

図4

zip ﬂat ﬂat v2(arr1，arr2 が引数の関数)

3. 1 コード生成の改善(Obj.new block 0 0) は第 4. 2 節を参照)．図 4 のコー

まずは，strymonas v1 において固定サイズの中間

ドには，図 3 の 2 行目で定義されている cuur 6 や

データ構造とクロージャを含むコードが生成されてしnadv 7 のような参照セル内で扱われる option 型の値

まうパイプラインの 1 つ zip ﬂat ﬂat(第 3. 2 節参照)

(固定サイズの中間データ構造) と，14 - 19 行目で定

zip_with (+)(of_arr (int_array arr1)| > flat_map (fun x →of_arr (int_array arr2)| > map (fun y → x * y)))(of_arr (int_array arr2)| > flat_map (fun x →of_arr (int_array arr1)| > map (fun y → x − y)))| > take (int 20_000_000)| > fold (+) (int 0)

義されているクロージャadv1 15 が存在していないた
め，第 1 節の問題 2. が解決されていることが分かる．
次に，これらのコードに対する実験の結果を図 5 に示す 2 ．縦軸は計測された実行時間の平均値を表して
おり，バーが低いほど高性能である．実験において，
パイプラインの入力値となる arr1 と arr2 にはそれ
ぞれ v と vLo を用い，第 1 節の問題 2. の解決がどの程度パフォーマンスに影響するのか測定した．実行を取り上げ，strymonas v2 によってこのパイプライ

結果を比較すると，zip ﬂat ﬂat に対する strymonas

ンから生成されるコードが改善されていることを確認

v2 の生成コードは v1 のものより 5 倍程度高速化さする．strymonas v1 と v2 の各々が zip ﬂat ﬂat から生成するコード zip ﬂat ﬂat v1 及び zip ﬂat ﬂat v2を，図 3 と図 4 に示す (図 4 の 4 行目記載の Obj.obj

2 strymonas v1 は BER MetaOCaml N104 でしかサポートされていないが，N104 で生成したコードをN107 で実行した．

zip with (+)

600

v1
v2

Time (ms)500• zip ﬂat ﬂat: ﬂat map さ れ た 2 つ の 配 列 の
zip with (+)，第 3. 1 節のパイプライン

400

これらのベンチマークは [8] で用いられているものと，

300[11] の zip ﬁlter ﬁlter と zip ﬂat ﬂat に由来する．
本実験では上記のベンチマークに対し，strymonas

200

v2 による生成コード (staged)，手書きで記述された効100

率的なコード (baseline)，streaming [5] という OCamlのストリームライブラリを用いたコード (source) を0
zip_flat_flat
図5

用意して，これら 3 つのコードの実行速度を測定しstrymonas v1, v2 のパフォーマンス比較:

た．streaming [5] は，pull と push という 2 つのモデルに基づいたストリーム処理をそれぞれ提供するが，エラーバーは 95%信頼区間

ここでは pull 式のストリーム処理が実装されている
れており，問題の解決によって実際にパフォーマンス

Source モジュールを用いた 3 ．ただし ﬂat map がが向上するという結果を得られた．

実装されていないため，Source モジュールでいくつかのベンチマークは実行できなかった．入力に関しては，各々のベンチマークについて次のように設定
した．

3. 2 ベンチマーク
本研究では，次のベンチマークを用いて strymonas• sum: v

v2 による生成コードの性能を測る実験を行った．

• sumOfSquares: v• sum:• sumOfSquaresEven: v∑

xi ，配列の要素 (int 型) の和i∑

xi ，配列の要素の二乗和• maps: v• sumOfSquaresEven: 配列の偶数要素のみの• ﬁlters: v• sumOfSquares:

2

i

二乗和

• maps: 配列に自然数倍する複数の map をかけるパイプライン• ﬁlters: 配列に自然数と比較する複数の ﬁlter をかけるパイプライン• cart:∑∑ixi yj ，xi を 要 素 と す る 配 列 に

ﬂat map を利用• dotProduct: 2 つの配列のドット積，zip with• ﬂatMap after zipWith:• dotProduct: vHi と vHi• ﬂatMap after zipWith: vFaZ と vFaZ
• zipWith after ﬂatMap: vZaf と vZaf
• ﬂat map take: v と Vlo• zip ﬁlter ﬁlter: v と VHi• zip ﬂat ﬂat: v と Vloj(×) を利用• cart: vHi と Vlo∑∑i(xi + xi )yj ，

j

zip with (+) 後に ﬂat map• zipWith after ﬂatMap: 変換されない配列と実験結果を図 6 に示す．縦軸は計測された実行時間の平均値を表しており，バーが低いほど高性能である．strymonas v2 と手書きのコードはおおよそ同程度のパフォーマンスとなり，これらは streaming よりも約 5 - 25 倍速く処理を終えるという結果が得られた．

ﬂat map された配列の zip with (+)• ﬂat map take: ﬂat map 後に take するパイプライン• zip ﬁlter ﬁlter: ﬁlter さ れ た 2 つ の 配 列 の

3 最新の streaming 全体は BER MetaOCaml N107
ではサポートされていないので，Source モジュールだけを取り出して利用した．

1200
1100
1000

Time (ms)900stagedbaselinesource

800
700
600
500
400
300
200
100
0 s
um sum sum map filte cart dotP flatM zipW flat_ zip_ zip_
Of Of s rs
rod ap ith ma filte flat
Sq Sq
uc _af _af p_t r_f _flaua uat
ter ter ak ilte t
res resr_z _fl e
Ev
ipW atMen
ith ap図6

strymonas v2(staged)，手書き (baseline)，streaming(source) のパフォーマンス比較: エラーバーは95%信頼区間，source の sumOfSquaresEven，maps，ﬁlters にかかった時間はそれぞれ約 1.5，5.0，3.8 秒

4. 1 中間言語

4 実装

strymonas におけるストリームは’a stream 型の第 2. 1 節ではユーザ向けの高水準な API(図 1) を値であるが，その実体はコード生成に用いられる中紹介したが，これらはより低水準な API によって実間言語のコードである．この中間言語は GADT の装されている．strymonas が提供する低水準の API

st stream という型で定義され，メタ言語に埋め込まを図 7 に示す．低水準 API はより一般的な表現の関れている．ここで，strymonas v2 の中間言語を図 8数を提供するため，高水準 API よりも提供する演算に示す．12 行目の Init は変数の初期化・宣言文であり，子が少ないなどの特徴を持つ．例えば，take に対応

13 行目の Lin が主に生産直後のストリーム，14 - 17

した take raw のような関数は低水準 API には存在

行目の Filtered/Stuttered，Break，Nested は各々順

せず，高水準 API の take は番に，continue 文を含んだループ，break 文を含んだ
ループ，多重のネストしたループによって要素が取りtake n s= map_raw' snd (zip_raw (from_to (int 1) n) s)

出されるように変換がかけられたストリームを定義する構文である．Filtered/Stuttered，Break，Nestedという恒等式を利用して実装されている．このようは低水準 API の ﬁlter raw，zip raw，ﬂat map rawに実装された take は zip( raw) を用いた定義の見かに各々対応する．

けに反し，タプルのような中間データ構造を生成コー

strymonas v1 で は ，Init，Filtered/Stuttered，

ドに含まない (例: 第 2. 2 節の最後の生成コード)．

Break に対応する明示的な構文が存在しない未洗練の中間言語を利用していたために，第 1 節で述べ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

type 'a st_stream
type goon = bool cde(* 生 産 者 *)val pull_array: int cde → (int cde → 'a emit)→ 'a st_stream
val initializing: 'z cde → ('z cde → 'a st_stream)→ 'a st_stream
val initializing_ref : 'z cde → ('z ref cde → 'a st_stream) → 'a st_stream
val initializing_arr : 'z cde array → ('z array cde → 'a st_stream) →'a st_stream
val infinite : 'a emit → 'a st_stream
val guard: goon → 'a st_stream → 'a st_stream(* 変 換 者 *)val map_raw: ('a → ('b → unit cde) → unit cde) →'a st_stream → 'b st_stream
val map_raw': ('a → 'b)→ 'a st_stream → 'b st_stream
val filter_raw: ('a → bool cde) → 'a st_stream → 'a st_stream
val flat_map_raw : ('a cde → 'b st_stream) → 'a cde st_stream →'b st_stream
val zip_raw: 'a st_stream→ 'b st_stream → ('a * 'b) st_stream(* 消 費 者 *)val fold_raw : ('a → unit cde) → 'a st_stream → unit cde

図7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

strymonas の低水準 API

type 'a pull_array = {upb: int cde;
index: int cde → 'a emit}
type 'a init =| Ilet : 'a cde → 'a cde init
| Iref : 'a cde → 'a ref cde init
type 'a producer =| For: 'a pull_array → 'a producer| Unfold: 'a emit→ 'a producer
and _ st_stream =| Init: 's init * ('s → 'a st_stream)→ 'a st_stream| Lin: 'a producer→ 'a st_stream| Filtered : ('a → bool cde) * 'a producer→ 'a st_stream| Stuttered : 'a option producer→ 'a st_stream| Nested: 'b cde st_stream * ('b cde → 'a st_stream) → 'a st_stream| Break: goon * 'a st_stream→ 'a st_stream
and 'a stream = 'a cde st_stream

図8

strymonas の中間言語

た問題 1. が発生していた．strymonas v2 では，ルー

理しやすい）といった中間言語の洗練化がなされた．

プの構造へ影響を持たない入力パラメータの変数や

ただし，Filtered/Stuttered や Break はそれぞれ

continue 文，break 文，ネストしたループという全くcontinue 文や break 文に対応して値が取り出される異なる構造のループで要素が取り出されるストリーム

ように変換されたストリームを表現するため，これを図 8 のように各々独立した構文で表現できるようらから OCaml のように continue 文や break 文を持にすることで，表現力の向上やコード生成で代数的にたない言語のコードを生成する場合には少し工夫が扱いやすくなる（パターンマッチングや再帰関数で処必要である．次に命令的な擬似コードを使ってその例を示す．例えば Filtered/Stuttered で表されるスト

かって未初期化のミュータブル変数を実現する必要がリームを作ってから消費するパイプラインある．OCaml を対象言語とする場合は図 4 で見られ

stream |> filter g |> fold f z

たが，の場合には，
ref (Obj.obj (Obj.new_block 0 0))
accum = z;
for ei in stream {if g(ei ) {accum = f (accum, ei );}}return accum;というように，Obj モジュールで生成した値を未初期化時に参照する表現で，option 型の値を用いず未初期化のミュータブル変数を表すことができる．

のように，g を満たさないかを確認して continue で

4. 3 クロージャの除去

処理を飛ばす場合とは逆に，g を満たすかを確認して

strymonas では，Filtered/Stuttered や Nested の処理を続けるようにすることで，continue 文付きのストリーム同士を zip する際に，前処理として片方のループを模倣できる．また，Break で表されるストストリームに線形化と呼ばれる，ストリームの表現がリームを作ってから消費するパイプライン

Lin となるよう変換する正規化の処理を行う必要があ

stream |> take n |> fold f z

る．Nested は ﬂat map( raw) によって生成されるスの場合では，
accum = z;goon = true;for (ei in stream) && goon {if i ≥ n {goon = false;} else {accum = f (accum, ei );}}return accum;

トリームであり，コード生成にクロージャが関係してくるのはストリームが Nested の場合である．したがって，本節では Nested の線形化について説明する．
今，サイズ N で i 番目の要素が ei のストリームを[e1 , e2 , . . ., eN ] のように表記すると，例えば[x1 , x2 , . . ., xN ]| > flat_map (fun x →[x+y1 , x+y2 , . . ., x+yN ′ ])のように，goon のような補助変数をループ継続判定という演算から生成されるストリームは，のガードに用いることで，break 文付きのループを模[x1 +y1 , x1 +y2 , . . ., x1 +yN ′ ,x2 +y1 , x2 +y2 , . . ., x2 +yN ′ ,. . .,
xN +y1 , xN +y2 , . . ., xN +yN ′ ]倣できる．

4. 2 固定サイズの中間データ構造の除去となる．ここで [x1 , x2 , . . ., xN ] のように，ﬂat map

第 1 節の問題 2. の原因となるのは，ﬂat map されの対象となるストリームを外側のストリームと呼ぶたストリーム (Nested) の対を zip するパイプラインことにし，外側のストリームの要素が x のときにのコード生成を行う場合に，生成するコードで未初期

ﬂat map のセマンティックアクションによって生成化のミュータブル変数を利用しなければならないこすることができる [x+y1 , x+y2 , . . ., x+yN ′ ] のようとである．関数型言語ではこれを ref None のようになストリームを内側のストリームと呼ぶことにする．

option 型の値への参照として表現する方法が自然でNested を線形化する場合，外側のストリームの現在

あり，strymonas v1 はこの方式を採用していたための要素 x などを自由変数として含む内側のストリー

option 型の値という固定サイズの中間データ構造がムの状態遷移を担う関数を生成するコードに用いざ

生成コードに含まれてしまっていた (図 3 の curr やるを得ない．strymonas v1 ではこのような状態遷移nadv)．

の関数を生成する対象コードにクロージャとしてそのこのような固定サイズの中間データ構造の使用をまま埋め込んでいたため (例: 図 3 の adv1 15)，第 1

避けるためには，対象言語のより低水準な機能をつ

節の問題 2.2. が起きていた．これを避けるためには，

strymonas で状態遷移の関数にクロージャ変換を行るのが Java 8 streams である．オブジェクト指向言う必要があり，以下ではその概要を説明する．

語における stream fusion の研究において，Java 8

クロージャ変換の基本は，自由変数を含む関数に対してその自由変数を引数として束縛させる変換を

streams はその題材として盛んに取り上げられており，そのような研究には [2] などがある．

かけ，その関数が定義されたときの自由変数の値を呼Weld IR [10] は TensorFlow，Apache Spark，

び出し時に参照できるよう保存しておくことである．

NumPy，Pandas といったデータ分析ライブラリを

strymonas v2 のクロージャ変換は，大域的な位置に跨いでクロスプラットフォームなバッチ処理の最適化

let 束縛された参照セル内に自由変数となる外側のスを実現する中間表現であり，Kroll ら [9] は Weld IR

トリームの現在の要素 x などを保存するようにしてにストリーム処理の表現能力を加えて拡張した Arc(例: 図 4 の lv 10 と lv 12)，内側のストリームの状という中間表現を提案している．

態遷移の関数が任意の位置から x などを参照できるようにすることである 4 ．この参照セルは x などの6 まとめと今後の課題

値を保存する以前から割り当てられるので未初期化

本研究では，当初の strymonas が抱えていた中間のミュータブル変数として表現する必要があり，そこ

言語や例外的に残留する固定サイズの中間データ構で第 4. 2 節の造とクロージャに関する問題を解決するため，中間言語の再設計や生成コードに対するより高度な最適ref (Obj.obj (Obj.new_block 0 0))化の実装を行った．この改善が施された strymonasが利用される．

は実験的にその性能の高さが証明されており，zip と以上のような処理に加え種々の関数をインライン展

ﬂat map を含むような複雑なものを含め API で表現開するなどして，全体のクロージャ除去の処理が果た

可能な任意のパイプラインに対し，中間データ構造される．ここで行われるクロージャ除去の処理は安全やクロージャを用いないストリーム処理を行う安全であり，すなわち strymonas が保証する安全なコーなコードを生成できるようになった．これによって，ドの生成が厳格に守られる．

高水準かつ高性能なストリームライブラリの基盤となるストリーム処理のコード生成器が実現された．

5 関連研究今後の課題としては 3 つが考えられる．1 つ目は，

streaming [5] はコンスタントメモリ，高パフォーマ

strymonas で window 処理をサポートすることであンス，安全なリソース管理などが特徴のストリーム

る．window 処理とは，入力ストリームを複数の有限処理を提供する OCaml のライブラリである．これら

データ列 (ウインドウ) に分割し，並行なバッチ処理

は stream fusion の利用によって実現されているもの

によってそれらを処理する機能である．window 処理の，streaming では strymonas のようなステージ化は実用的な高機能ストリームライブラリの中核となを用いた高度な最適化などは行われないため，タプル

る機能であり，特定の対象言語に依存しない高性能でや option 型の値などの固定サイズの中間データ構造

安全な window 処理のコードの生成器を実現するこやクロージャなどに起因した種々のオーバーヘッドがとは大きな課題である．2 つ目は，strymonas の中間存在する．

言語を C/LLVM へコンパイルすることである．コー

stream fusion が施されたストリームライブラリのド生成の対象が OCaml のような高水準言語となる

うち，オブジェクト指向言語で関数型のストリーム

場合，言語機能の問題で達成できるストリーム処理処理を実現する実用的なライブラリとして有名であの性能に限界がある．例えば OCaml は break 文を

4 ある内側のストリームの状態遷移の関数のクロージャ
は同時には１つまでしか存在しないため，各自由変数に対して 1 つずつ参照セルを導入すればよい．

サポートしないため，take を行うストリーム処理のコードでは第 4. 1 節の最後で紹介したように補助変数のガードを利用して break の挙動を模倣することになる．そこで，C や LLVM のような低水準の計算が行える言語であればこのような制約を受けず，より効率の良いストリーム処理を実現できるはずである．
幸い strymonas v2 ではコード生成の対象言語を cde型によって抽象化するようになったため，図 2 のイン
ターフェースを満たす C/LLVM 向けの EDSL を実装すればこれを実現できる．3 つ目は，TensorFlowなどのデータ分析フレームワークを strymonas の立場から考えることである．生成するストリーム処理のコードの安全性やコンパイラによらない効率性を保証する strymonas の最適化は有用であり，このアプ
ローチがバッチ処理の方面に応用されることは大変望ましい．

参 考 文 献[ 1 ] Biboudis, A.: Expressive and Eﬃcient Streaming Libraries, PhD Thesis, University of Athens,
Athens, March 2017.
[ 2 ] Biboudis, A., Palladinos, N., Fourtounis, G.,
and Smaragdakis, Y.: Streams a la carte: Extensible Pipelines with Object Algebras, 29th European Conference on Object-Oriented Programming(ECOOP 2015), Vol. 37, 2015, pp. 591–613.
[ 3 ] Coutts, D., Leshchinskiy, R., and Stewart, D.:
Stream Fusion: From Lists to Streams to Nothing at All, Proceedings of the 12th ACM SIGPLAN
International Conference on Functional Programming, ICFP ’07, New York, NY, USA, ACM, 2007,
pp. 315–326.
[ 4 ] Coutts, D. and Stewart, D.: stream-fusion:
Faster Haskell lists using stream fusion, https://hackage.haskell.org/package/stream-fusion.

[ 5 ] I, R.: odis-labs/streaming: Fast, safe and composable streaming abstractions., https://github.
com/odis-labs/streaming.
[ 6 ] Kiselyov, O.: The Design and Implementation of
BER MetaOCaml, Functional and Logic Programming, Springer, 2014, pp. 86–102.
[ 7 ] Kiselyov, O., Biboudis, A., Palladinos, N., andSmaragdakis, Y.: Strymonas Streams: stream fusion, to completeness, https://strymonas.github.
io/.
[ 8 ] Kiselyov, O., Biboudis, A., Palladinos, N., andSmaragdakis, Y.: Stream fusion, to completeness,
POPL ’17: Conference Record of the Annual ACM
Symposium on Principles of Programming Languages, New York, ACM Press, January 2017,
pp. 285–299.
[ 9 ] Kroll, L., Segeljakt, K., Carbone, P., Schulte, C.,
and Haridi, S.: Arc: An IR for Batch and Stream
Programming, Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages, DBPL 2019, New York, NY,
USA, Association for Computing Machinery, 2019,
pp. 53–58.
[10] Palkar, S., Thomas, J. J., Shanbhag, A.,
Narayanan, D., Pirk, H., Schwarzkopf, M., Amarasinghe, S., and Zaharia, M.: Weld: A Common Runtime for High Performance Data Analytics, The biennial Conference on Innovative Data Systems Research, CIDR ’17, Jan 2017.
[11] Parreaux, L., Shaikhha, A., and Koch, C.:
Quoted Staged Rewriting: A Practical Approach to
Library-Deﬁned Optimizations, Proceedings of 16th
ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences(GPCE 17), (2017), pp. 15.
[12] Rompf, T. and Odersky, M.: Lightweight Modular Staging: A Pragmatic Approach to Runtime
Code Generation and Compiled DSLs, Commun.
ACM, Vol. 55, No. 6(2012), pp. 121–130.