項書き換えマクロで最適化

Nimの特徴的な機能である項書き換えマクロ(English: term rewriting macro)についてです。

項書き換えマクロとは

項書き換えマクロについては知らない方も多いかと思います。
他の言語にはあまり見られない機能で、自分が確認している言語はNim以外ではCommon Lisp(コンパイラマクロ)とScheme(一部の処理系)ぐらいしかありません。(この言語にも項書き換えマクロあるよ！という方はコメントで教えてもらえると嬉しいです。)
項書き換えマクロは、項を書き換えるマクロで、項とは式などの構成要素を指す言葉です。
すなわち、私の解釈では項書き換えマクロはプログラムの構成要素自体を書き換えてしまうマクロになります。
なんでこんな機能があるの？と思われる方も多いかもしれませんが、これが特定の領域になると力を発揮します。
その特定の領域とは最適化です。

Nimの項書き換えマクロの基本的な使い方としては、複数の呼び出しを１つの呼び出しとしてまとめたり、引数によってそもそも呼び出す関数を書き換えたりする際に使います。
こういった最適化は通常コンパイラが行うものではありますが、Nimではこれをユーザーレベルで行うことが可能です。

実例

まず、分かりやすい例として、引数が定数である場合に最適化を施してみます。
以下のコードは公式にある部分評価のコードを参考にしました。(http://nim-lang.org/docs/manual.html#term-rewriting-macros)

proc p(x, y: int, cond: bool): int =
  result = if cond: x + y else: x - y

上記の関数は、引数がtrueであった場合に加算、falseであった場合に減算するという関数です。
非常にシンプルな関数でこれ以上最適化の余地がないように思えますが、特定のケースにおいて大きな無駄が発生します。
その特定のケースとは引数のcondが定数の場合です。condが定数の場合、ifによる場合分けはコンパイル時に解決できるはずですが、この関数では愚直に実行時にいちいちifによる分岐が発生しています。
今回はこの関数を項書き換えマクロを使って最適化してみます。

template optP1{p(x, y, true)}(x, y: untyped): untyped = x + y
template optP2{p(x, y, false)}(x, y: untyped): untyped = x - y

上記のコードが項書き換えマクロの一例です。テンプレート名の後の波括弧でASTベースのマッチングを行い、一致する場合テンプレートで置き換えるということをしています。
この例では、上記の関数pの引数condが定数であった場合にif文を除去するということをしています。

ベンチマーク

最適化を実感するために上記の関数pを最適化した場合と最適化していない場合のベンチマークをしてみました。
時間の計測にはNimの標準ライブラリにあるtimesモジュールを使用しています。

# not optimized
import times

proc p(x, y: int, cond: bool): int =
  result = if cond: x + y else: x - y

let starttime = epochTime()
for i in 0..<100000000:
  discard p(10, 20, true)
let endtime = epochTime()
echo endtime - starttime

# optimized
import times

proc p(x, y: int, cond: bool): int =
  result = if cond: x + y else: x - y

template optP1{p(x, y, true)}(x, y: untyped): untyped = x + y
template optP2{p(x, y, false)}(x, y: untyped): untyped = x - y

let starttime = epochTime()
for i in 0..<100000000:
  discard p(10, 20, true)
let endtime = epochTime()
echo endtime - starttime

筆者の環境

Type	Name
OS	Windows 10 Home
CPU	Intel Core i7-6700
GPU	AMD Radeon RX480
マザーボード	ASUSTek H170-PRO
メモリ	DDR4 8x2=16GB
Nim version	0.15.2

一応念のためGPUも書きました。

結果は以下の通りになりました。

Type	Second
not optimized	1.8s
optimized	0.63s

多少分散はするものの、自分の環境ではおおむね上記のようになりました。

まとめ

Nimの項書き換えマクロはコンパイル時実行と合わせて非常に強力になっています。
ASTベースオーバーロードと組み合わせて、引数がリテラルもしくは定数の場合にのみ最適化するといったことも可能です。

Nimはこういった自動で最適化したり、自動でボイラープレートを生成するといった、プログラム自体を自動で扱うといったことが得意な言語と感じます。
基本的な機能にしぼって考えれば使用感は割とGoに似ていると感じますが(deferなど)、Goがシンプルでソースコードそのままに動くということを哲学にしているのに対して、Nimは自動最適化などプログラムを速度、そして自動化で無駄を省くなど最大限まで効率化するということを哲学にしているように感じます。

非常に面白い言語だと思うので、気になった方は是非試してみてください。