Halide小ネタ(Halide::undef編)

初投稿です．Halideを触っていて「なんか使えそうだな～いやそうでもないかぁ」って感じの小ネタや，チュートリアルのってない便利機能を紹介していこうとおもいます．今回はその第1弾(いくつ続けられるか...)
## はじめに
[Halide](https://halide-lang.org/)は画像処理に特化したドメイン固有言語です．大きな特徴として処理の本質となるアルゴリズム部分と，高速化に関するスケジューリング部分を独立して記述でき，簡潔な記述ですげぇ速いコードが生成できます．詳細な解説は[こちら](http://nebuta.hatenablog.com/entry/2013/08/04/135932)や[こちら](https://qiita.com/fukushima1981/items/193c4ae03b2ea3b4f98e)でされているので，ここでは省略．[公式チュートリアル](https://halide-lang.org/tutorials/tutorial_introduction.html)が公開されているので，基本的な使い方はここで学べます．

## Pure DefinitionとUpdate Definition
[公式チュートリアル09](https://halide-lang.org/tutorials/tutorial_lesson_09_update_definitions.html)の内容です．既に知っている内容なら飛ばしてください．

HalideのFuncはマルチパスで定義することができます．下のコードがマルチパスFuncの一例で，
`f(x, y) = input(x, y);`と`f(x, 3) = f(x, 0) * f(x, 10);`によって`Func f`が定義されます．前者の定義が**Pure Definition**，後者の定義が**Update Definition**と呼ばれ，本記事ではこれらを**純粋定義**と**更新定義**と呼びます．

```cpp
Halide::Var x("x"), y("y");
Halide::Func f("func");
f(x, y) = input(x, y);
f(x, 3) = f(x, 0) * f(x, 10);
```

純粋定義では画像全体についてどのように処理されるかを記述し，`Var`から`Expr`へのマッピングでないといけないですが，更新定義では画像の一部分に限った処理が許されます．また，純粋定義はただ1つで必須な定義ですが，更新定義はいくつでも任意に定義できます．また，処理される順番は純粋定義のあと更新定義が定義された順番に処理されます．

## undefで初期化スキップ
次のようなHalideコードを見てみましょう．

```cpp
Halide::Var x("x"), y("y");
Halide::RDom r(1, w - 1);
Halide::Func before("before"), after("after");

before(x, y) = input(x, y);
before(r, y) = 0.8f * before(r, y) + 0.2f * before(r - 1, y);
```

上のコードでは，`Func before`が純粋定義で入力`input`をコピーし，更新定義でReduction Domainを使って1つ前の出力と，現在の入力との加重平均をとっています...が．<br>
**...これ純粋定義のいらんくない???<br>はじめから`before(r, y) = 0.8f * input(r, y) + 0.2f * before(r - 1, y);`ってすりゃええ話なのでは??**<br>
ところが，純粋定義の制約上Reduction Domainが使えないし，`befoe`の初期値が分からんといったことからできないのです．こいういときは`Halide::undef`の出番です．

```cpp
Halide::Var x("x"), y("y");
Halide::RDom r(1, w - 1);
Halide::Func after("after");

after(x, y) = Halide::undef(input.type());
after(0, y) = input(0, y); // 初期値がいる
after(r, y) = 0.8f * input(r, y) + 0.2f * after(r - 1, y);
```
このように，純粋定義を`Halide::undef`にすることで，純粋定義の処理を省略することができます．

## undefの説明
Halide.hによると，`Halide::undef`の説明は以下の通りです．
>/** Return an undef value of the given type. Halide skips stores that
 * depend on undef values, so you can use this to mean "do not modify
 * this memory location". This is an escape hatch that can be used for
 * several things:
 *
 * You can define a reduction with no pure step, by setting the pure
 * step to undef. Do this only if you're confident that the update
 * steps are sufficient to correctly fill in the domain.
 *
 * For a tuple-valued reduction, you can write an update step that
 * only updates some tuple elements.
 *
 * You can define single-stage pipeline that only has update steps,
 * and depends on the values already in the output buffer.
 *
 * Use this feature with great caution, as you can use it to load from
 * uninitialized memory.
 */

`Halide::undef`の値に依存するストアはスキップされるそうですね．

## 実験結果
環境はIntel Core i7-8550U CPU @ 1.80GHzです．

```
before : 1.29004ms
after : 1.08038ms
```
画素タッチ一回分くらい速くなりました.

## 最後に
今回は`Halide::undef`を紹介しました．
個人的に結構便利機能だと思うのですがなぜかチュートリアルに載ってないんですよね...~~そもそも公式チュートリアルが不十分すぎる~~
こんな感じの小ネタを今後いくつか紹介できたらなと思います.

## テスト用コード全体

```cpp
void test_undef_initialize(Halide::Buffer<float> input) {
	const int w = input.width(), h = input.height();
	Halide::Var x("x"), y("y");
	Halide::RDom r(1, w - 1);
	Halide::Func before("before"), after("after");
	double result;

	before(x, y) = input(x, y);
	before(r, y) = 0.8f * before(r, y) + 0.2f * before(r - 1, y);
	result = Halide::Tools::benchmark(10, 10, [&]()
		{
			before.realize(w, h);
		}
	);
	cout << "before : " << result * 1e3 << "ms\n";
	
	after(x, y) = Halide::undef(input.type());
	after(0, y) = input(0, y);
	after(r, y) = 0.8f * input(r, y) + 0.2f * after(r - 1, y);
	result = Halide::Tools::benchmark(10, 10, [&]()
		{
			after.realize(w, h);
		}
	);
	cout << "after : " << result * 1e3 << "ms\n";
}
```
</details>