世界最速のテンプレートエンジンを作る

# 対象とする読者

- RustでISUCONに出場し優勝したい人
- プログラムの最適化に興味がある人
- プログラムの実行速度に飢えているスピード狂の方々（筆者を含む）

# きっかけ

Rustのテンプレートエンジンの一つである[Askama](https://github.com/djc/askama)の作者がRustの様々なテンプレートエンジンを比較したベンチマーク結果を[公開](https://github.com/djc/template-benchmarks-rs)していました。

このリポジトリの`Big table`というベンチマーク結果を見ると、一番速いライブラリでも1つのテンプレートのレンダリングに264マイクロ秒の時間を要していることが分かります。

1つのテンプレートに264マイクロ秒費やすということは、1秒間でわずか3000〜4000個のテンプレートしかレンダリングできないことを意味します。

しかし[Actix-web](https://github.com/actix/actix-web)は毎秒[60万リクエスト](https://www.techempower.com/benchmarks/#section=data-r19&hw=ph&test=fortune)を捌ける能力を持っており、テンプレートのレンダリングではCPUの待機時間が発生しないことを考えるとこれは大きなオーバーヘッドとなります。

そこで、手元で実験をしながらどこまで高速化できるか試してみてみたところ、結果的にこれらのライブラリよりも優れた速度を達成することができたのでライブラリにして公開することにしました。

# 成果物

https://github.com/kogia-sima/sailfish

詳しい使い方は[User Guide](https://sailfish.netlify.app/en/)に書いてありますが、基本的にテンプレートの文法はERubyやEJSと同じで、`<% %>`で囲まれたブロックにRustのコードを記述するだけです。

```erb
<html>
  <body>
    <% for msg in &messages { %>
      <div><%= msg %></div>
    <% } %>
  </body>
</html>
```

Rustから呼び出す際にはderive macroを使って`TemplateOnce`トレイトを実装します。

```rust
#[derive(TemplateOnce)]
#[template(path = "hello.stpl")]
struct HelloTemplate<'a> {
    messages: &'a [String],
}

fn main() {
    let ctx = HelloTemplate {
        messages: &[String::from("foo"), String::from("bar")];
    }

    println!("{}", ctx.render_once().unwrap());
}
```

`derive(TemplateOnce)`という記述を加えることにより、コンパイル時にテンプレートを読み込み、テンプレートをレンダリングするためのRustのコードを自動生成するという仕組みになっています。

ちなみにSailfishという名前はバショウカジキの英名からきていますが、最近の研究ではバショウカジキはそれほど速くないらしいです（それでもウサイン・ボルトと同じくらい）。[^1] [^2] [^3] [^4]

[^1]: Sagong W, Jeon W-P, Choi H (2013) Hydrodynamic Characteristics of the Sailfish (Istiophorus platypterus) and Swordfish (Xiphias gladius) in Gliding Postures at Their Cruise Speeds. PLoS ONE 8(12): e81323

[^2]: Stefano Marras, Takuji Noda, John F. Steffensen, Morten B. S. Svendsen, Jens Krause, Alexander D. M. Wilson, Ralf H. J. M. Kurvers, James Herbert-Read, Kevin M. Boswell, Paolo Domenici, Not So Fast: Swimming Behavior of Sailfish during Predator–Prey Interactions using High-Speed Video and Accelerometry, Integrative and Comparative Biology, Volume 55, Issue 4, October 2015, Pages 719–727

[^3]: Svendsen, Morten & Domenici, Paolo & Marras, Stefano & Krause, Jens & Boswell, Kevin & Rodriguez-Pinto, Ivan & Wilson, Alexander & Kurvers, Ralf & Viblanc, Paul & Finger, Jean & Steffensen, John. (2016). Maximum swimming speeds of sailfish and three other large marine predatory fish species based on muscle contraction time and stride length: A myth revisited. Biology Open. 5. bio.019919. 10.1242/bio.019919.

[^4]: Iosilevskii, G., & Weihs, D. (2008). Speed limits on swimming of fishes and cetaceans. Journal of the Royal Society, Interface, 5(20), 329–338

# 最適化の軌跡

## `Big table`ベンチマークの概要

行数100, 列数100の行列をHTMLのテーブルとして出力します。Sailfishの文法だとこんな感じになります。

```erb
<table>
<% for r1 in &table { %>
  <tr>
  <% for r2 in r1 { %>
    <td><%= r2 %></td>
  <% } %>
  </tr>
<% } %>
</table>
```

今回はこれをどこまで高速化できるのか試してみました。


## 簡単な最適化

### 1. `std::write!`を使った愚直な実装

```rust
use std::io::Write;

let mut output = Vec::<u8>::new();
write!(&mut output, "<table>").unwrap();
for r1 in &table {
    write!(&mut output, "<tr>\n").unwrap();
    for r2 in r1 {
        write!(&mut output, "<td>{col}</td>", col = r2).unwrap();
    }
    write!(&mut output, "</tr>\n").unwrap();
}
write!(&mut output, "</table>").unwrap();
```

ご存知の方は多いと思いますが、Rustの`write!`マクロは基本的に遅いです。

これは、`write!`が内部的に動的ポリモーフィズムで実装されていることや出力フォーマット指定などを考慮していることに起因します。

### 2. `String::push_str`を使って置き換える

`write!`は遅いので`String::push_str`を直接呼び出して高速化します。

```rust
use std::fmt::Write;

let mut buffer = String::new();
buffer.push_str("<table>");
for r1 in &table {
    buffer.push_str("<tr>");
    for r2 in r1 {
        buffer.push_str("<td>");
        write!(buf, "{}", *r2);
        buffer.push_str("</td>");
    }
    buffer.push_str("</tr>");
}
buffer.push_str("</table>");
```

80%くらい速くなりました。

### 3. `itoa`クレートを使う

まだ`write!`マクロが一箇所残ってしまっているので、[itoa](https://crates.io/crates/itoa)クレートを使って数値を文字列に変換します。

```diff
-         write!(buf, "{}", *r2)?;
+         itoa::fmt(&mut buffer, *r1);
```

さらに80%くらい速くなりました。

### 4. `String::push_str`を再実装する

`String::push_str`は内部的には`Vec::extend_from_slice`を呼び出しているのですが、私の環境ではどうもこの関数の呼び出しが遅いようでした。

そこで（どうしてそういう発想に至ったのかは分からないのですが）`String`型をラップした`Buffer`という構造体を作ることにしました。

```rust
struct Buffer {
    inner: String
}

impl Buffer {
    ...

    #[inline]
    fn push_str(&mut self, data: &str) {
        let size = data.len();
        self.inner.reserve(size);
        unsafe {
            let p = self.inner.as_mut_ptr().add(self.inner.len());
            std::ptr::copy_nonoverlapping(data.as_ptr(), p, size);
            self.inner.set_len(self.inner.len() + size);
        }
    }
}
```

`String`の代わりにこの構造体を使うことで60%ほど速くなりました。

### 5. reserveの呼び出しを制限する

アセンブリ[^5]とFrameGraphを確認したところ、`reserve`関数の呼び出しがインライン化されておらず、またその呼び出しがボトルネックになっていたので、`push_str`の実装を書き換えました。

[^5]: [cargo-asm](https://github.com/gnzlbg/cargo-asm)を使うと便利です

```diff
-        self.inner.reserve(size);
+        if size > self.inner.capacity() - self.inner.len() {
+            self.inner.reserve(size);
+         }
```

なんとこれだけでさらに1.5倍の速度を達成しました。

### 6. レンダリングの文字列の長さを記憶する

上記の変更にも関わらず、`Buffer::reserve`関数の呼び出しが依然としてボトルネックになっていました。

最近のmallocは[速い](https://stackoverflow.com/questions/23591196/are-calloc-malloc-faster-than-operator-new-in-c)ので、多少多めにメモリを確保してしまってもパフォーマンスの劣化はそれほど大きくなりません。

そこで、それまでのレンダリングで出力された文字列の長さの最大値を記憶し、その分だけ予めメモリを確保することにします。

```rust
static CAPACITY_HINT: AtomicUsize = AtomicUsize::new(0);
let capacity_hint = CAPACITY_HINT.load(Ordering::Acquire);

let mut buffer = Buffer::with_capacity(capacity_hint);

buffer.push_str("<table>");
for r1 in &table {
    buffer.push_str("<tr>");
    for r2 in r1 {
        buffer.push_str("<td>");
        buffer.push_int(*r2);
        buffer.push_str("</td>");
    }
    buffer.push_str("</tr>");
}
buffer.push_str("</table>");

let new_capacity_hint = buffer.len();
if new_capacity_hint > capacity_hint {
    CAPACITY_HINT.store(new_capacity_hint, Ordering::Release);
}
```

これでさらに80%ほど高速化しました。

なお、実際には掲示板サイトのようにレンダリングする度に中身が増えていくケースもあるので、最大値よりも少し多めにメモリを確保することでメモリの再確保を防止しています。

ちなみにこの時点で他のライブラリとの比較結果は以下のようになりました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/171615/5d1b7d36-92dc-decc-d405-f6c5afa08b37.png)

### 7. Stringを再実装する

アセンブリを見ると`String::with_capacity`や`String::reserve`がインライン化されておらず、そのために`reserve`が必要がどうかのチェックが無駄に発生していることに気がついたので、思い切って`String`そのものを`std::alloc`モジュールを駆使して再実装しました。[^5]
これによりさらに10%ほど高速化しました。

[^5]: あまりインライン化しすぎると出力されるバイナリが肥大化するため、逆にボトルネックでない部分などに`#[inline(never)]`を付与するなどしてバイナリの肥大化を抑えています。

## 宿敵現る

ここまで実験を終えた段階で、他のライブラリと大きな差が出たので、これらの最適化手法をSailfishというライブラリとして公開することにしました。

しかしこのリポジトリを公開してからわずか1日後、[yarte](https://github.com/botika/yarte)というライブラリが新たに[TemplateFixedTrait](https://docs.rs/yarte/0.10.0/yarte/trait.TemplateFixedTrait.html)というトレイトとそのderive macroを公開しました。これがとても速く、なんと従来の3倍以上の速度を達成していました。[^6]

![image.png](https://raw.githubusercontent.com/Kogia-sima/sailfish/d9a4d8f0195e5b1099de99b1a4ad37d87aef086d/benches/bigtable.png)

[^6]: ちなみにこのトレイトを使用する場合、あらかじめレンダリング後の文字列の長さの最大値を知っておく必要があります。

今回はあくまでも「最速」のテンプレートエンジンを作ることが目標であるため、`yarte`から逃げ切るためにさらに高度な最適化をいくつか施しました。

## 高度な最適化

### 1. ループの先頭と末尾を結合する

先程のコードの最内ループについて考えます。

```rust
for r2 in r1 {
    buffer.push_str("<td>");
    buffer.push_int(*r2);
    buffer.push_str("</td>");
}
```

このループでは、最後に`</td>`を出力し、その後最初に戻って`<td>`を出力しています。この操作を2回に分けるのは明らかに非効率です。

そこで、末尾の文字列を先頭の文字列をくっつけてまとめて出力するようにコードを改変します。

```rust
buffer.push_str("<td>");
for r2 in r1 {
    buffer.push_int(*r2);
    buffer.push_str("</td><td>");
}
buffer.truncate(buffer.len() - 4);
```

これにより15%ほど速度を改善しました。

### 2. 数値の書き込みを高速化する

この時点でボトルネックとなっていたのは、数値を書き込む部分、つまり`push_int`を呼び出している部分でした。

これまでは`itoa`クレートを使って数値をバッファに書き込んでいました。しかし`itoa`クレートでは、予め用意された固定長のメモリ配列に**後ろから**数値を書き込み、その結果をバッファにコピーします。

もしこれを**先頭から**書き込めるようにすれば、固定長の配列ではなくバッファそのものに直接書き込むことができます。

これを速く行う方法を探していたところ、[itoa-benchmark](https://github.com/miloyip/itoa-benchmark)というリポジトリを見つけました。

桁数が小さい数値のほうが出現頻度が高いと考えられるので、5桁までの整数で最も優れたパフォーマンスを発揮している`branchlut`という実装をRustに移植しました。これにより、さらに約20%の高速化を実現しました。

## ベンチマーク結果

ここまでの最適化を施した結果、以下のようなベンチマーク結果が得られました。

![image.png](https://raw.githubusercontent.com/Kogia-sima/sailfish/02380994ddfa5e06d961a341f61436a58b928f13/benches/bigtable.png)

私の知る限り、Rustのライブラリの中では一番速いと思います。

とりあえずは`std::write!`の約10倍の速度を達成することができたので、区切りが良いために一度記事にまとめて投稿することにしました。
sailfishで用いられている最適化手法が読者のお役に立てれば幸いです。

# 今後について

しばらく速度ばかりに焦点を当てていて機能面が疎かになっているので、今後は機能面を充実させていく予定です。

ただし最適化の余地はまだ[いくつか残っている](https://github.com/Kogia-sima/sailfish/issues?q=is%3Aissue+is%3Aopen+label%3A%22Type%3A+Performance%22)ので、パフォーマンスが改善でき次第、最新のベンチマーク結果を[こちら](https://github.com/Kogia-sima/sailfish/tree/master/benches)にて更新していきます。

# 追記（2020/1/24）

「世界最速」と謳っていますが、今回の目的はあくまでBig table benchmarkをどこまで最適化出来るかを試すものであり、他のライブラリを貶したり、あるいは特定のライブラリが他より優れていることを示すためのものではありません。また他のベンチマークにおいても最速であることを保証するものでもありません。

ちなみに現在では他のライブラリのパフォーマンスもかなり上昇してきており、必ずしもsailfishが最速であるとは言えない状況になっています。

https://github.com/djc/template-benchmarks-rs