大量のPNG画像を標準パッケージのみで2.4倍高速に処理する

## はじめに
大量のPNG画像を標準パッケージで処理する機会があったのですが、あまりにも遅すぎたので、
どこがボトルネックになっているか調べ、どうすれば標準パッケージの範囲で改善できるか実験してみました！

使用したソースコードや画像、実験結果は[**ココ**](https://github.com/cia-rana/go-benchmarks/tree/master/png)においています。

## 環境
- OS: Ubuntu 16.04 LTS
- Go: go1.11.2 linux/amd64
- Memory: 2GB
- CPU: Intel Core i5-3340M CPU @ 2.70GHz（使用可能なコア数を1に制限）

## 使用する画像
https://github.com/ashleymcnamara/gophers に実験にちょうど良いPNG画像があったのでお借りしました。ありがとうございます:pray:
“Gopher Artwork” by Ashley McNamara is licensed under  Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

使用する画像の枚数は96枚、未処理の画像全体のサイズは約68MBとなっています。

## 改善前のソースコード
ソースコードを全て載せると冗長になるので、重要な箇所のみ載せておきます。ソースコード全体は[こちら](https://github.com/cia-rana/go-png-bench/blob/master/profile.go)をご覧ください。処理としてはオーソドックスなネガポジ反転処理ですね。

画像のカラーモデルは、あらかじめ `color.NRGBAModel` であることが分かっているとします。

```go
for _, path := range GetPathAll() {
	...
	img, err := png.Decode(srcFile)
	...
	imgNRGBA := img.(*image.NRGBA)
	bounds := imgNRGBA.Bounds()
	for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
		for x := bounds.Min.X; x < bounds.Max.X; x++ {
			c := imgNRGBA.At(x, y).(color.NRGBA)
			imgNRGBA.Set(x, y, color.RGBA{
				uint8(255 - c.R),
				uint8(255 - c.G),
				uint8(255 - c.B),
				c.A,
			})
		}
	}
	...
	png.Encode(dstFile, img)
	...
}
```

## 推測するな計測せよ
なにはともあれ、どこがボトルネックになっているかを把握しなければ改善のしようがありません。Goにはどの関数にどれだけの処理時間を費やしているか計測するプロファイリングツールとして pprof があるので、これを使っていきましょう！

以下が計測結果の一部です。

```
Duration: 2.85mins, Total samples = 157.11s (91.76%)
Showing nodes accounting for 152.17s, 96.86% of 157.11s total
Dropped 191 nodes (cum <= 0.79s)
      flat  flat%   sum%        cum   cum%
    23.09s 14.70% 14.70%     35.19s 22.40%  image/png.filter
       16s 10.18% 24.88%        28s 17.82%  runtime.mallocgc
    12.89s  8.20% 33.09%     31.27s 19.90%  compress/flate.(*compressor).deflate
     9.85s  6.27% 39.35%      9.85s  6.27%  compress/flate.matchLen
     9.33s  5.94% 45.29%      9.33s  5.94%  runtime.memmove
     8.29s  5.28% 50.57%     43.39s 27.62%  runtime.convT2Inoptr
     5.59s  3.56% 54.13%      5.59s  3.56%  image/png.abs (inline)
     5.23s  3.33% 57.46%     34.02s 21.65%  image.(*NRGBA).Set
     5.04s  3.21% 60.66%     14.89s  9.48%  compress/flate.(*compressor).findMatch
     4.99s  3.18% 63.84%     76.50s 48.69%  main.ProcessImage
     4.53s  2.88% 66.72%      8.50s  5.41%  image/png.paeth
     4.38s  2.79% 69.51%      5.71s  3.63%  image.(*NRGBA).NRGBAAt
     3.85s  2.45% 71.96%     24.39s 15.52%  image/color.nrgbaModel
     3.60s  2.29% 74.25%      3.60s  2.29%  image/png.abs8 (inline)
     3.10s  1.97% 76.23%      3.10s  1.97%  hash/adler32.update
     3.07s  1.95% 78.18%     23.67s 15.07%  image.(*NRGBA).At
     2.97s  1.89% 80.07%      2.97s  1.89%  image/color.RGBA.RGBA
     2.89s  1.84% 81.91%      5.86s  3.73%  image/color.(*RGBA).RGBA
     2.77s  1.76% 83.67%      4.39s  2.79%  image/png.filterPaeth
     2.76s  1.76% 85.43%     27.15s 17.28%  image/color.(*modelFunc).Convert
     2.75s  1.75% 87.18%      2.75s  1.75%  runtime.nextFreeFast (inline)
     2.38s  1.51% 88.70%      2.38s  1.51%  runtime.acquirem (inline)
     2.37s  1.51% 90.20%      2.37s  1.51%  runtime.releasem (inline)
     1.70s  1.08% 91.29%      1.70s  1.08%  compress/flate.hash4 (inline)
     1.57s     1% 92.29%      1.57s     1%  image.(*NRGBA).PixOffset (inline)
     1.50s  0.95% 93.24%     10.98s  6.99%  image/png.(*decoder).readImagePass
     1.44s  0.92% 94.16%      1.44s  0.92%  runtime.gomcache (inline)
     1.40s  0.89% 95.05%      1.40s  0.89%  image.Point.In (inline)
```

`flat`の列がサンプリングした時間における各関数の純粋な実行時間です。

## 第一の改善: 配列へ直接アクセスする

最も時間がかかっているのは `image/png.filter` で、これはPNG画像をエンコードする際に、画像の行毎にどのようなフィルタ[^1]を用いればよいか選択する関数です。注意していただきたいのは、圧縮する処理ではなく、フィルタの選択に最も時間を費やしている点です[^2]。本来であればこれを改善すれば、大幅な速度向上が期待できるのですが、残念ながら標準パッケージをいじらなければならないため、これを改善するのはあきらめましょう[^3]。

次に目につくのは、`runtime.mallocgc` や `runtime.memmove` などのメモリ管理を行う関数や、`image/color` パッケージの関数です。これらの関数は各画素の読み書きを間接的に行うために多く呼び出されています。実は `image.Image` はインターフェースであり、それを型アサーションした `*image.NRGBA` は各画素の画素値をRGBAの順で `[]uint8` 型の変数 `Pix` に保持しています。この `Pix` はお分かりの通り構造体の外部からアクセス可能ですので、各画素への読み書きを直接行うことができます。よって、以下のように配列から直接読み書きできます。

```go
for _, path := range GetPathAll() {
	...
	img, err := png.Decode(srcFile)
	...
	pix := img.(*image.NRGBA).Pix
	for i := 0; i < len(pix); i += 4 {
		pix[i] = 255 - pix[i]
		pix[i+1] = 255 - pix[i+1]
		pix[i+2] = 255 - pix[i+2]
	}
	...
	png.Encode(dstFile, img)
	...
}
```

さて、処理速度はどうなったでしょうか？ 計測結果を見ていきましょう！

```
Duration: 1.45mins, Total samples = 79.99s (91.86%)
Showing nodes accounting for 78.52s, 98.16% of 79.99s total
Dropped 120 nodes (cum <= 0.40s)
      flat  flat%   sum%        cum   cum%
    22.43s 28.04% 28.04%     34.80s 43.51%  image/png.filter
    12.10s 15.13% 43.17%     30.80s 38.50%  compress/flate.(*compressor).deflate
    10.79s 13.49% 56.66%     10.79s 13.49%  compress/flate.matchLen
     5.98s  7.48% 64.13%      5.98s  7.48%  image/png.abs (inline)
     4.73s  5.91% 70.05%     15.52s 19.40%  compress/flate.(*compressor).findMatch
     4.33s  5.41% 75.46%      8.63s 10.79%  image/png.paeth
     3.74s  4.68% 80.14%      3.74s  4.68%  image/png.abs8 (inline)
     2.94s  3.68% 83.81%      2.94s  3.68%  hash/adler32.update
     2.20s  2.75% 86.56%      3.88s  4.85%  image/png.filterPaeth
     1.53s  1.91% 88.47%      1.53s  1.91%  main.ProcessSlice
     1.46s  1.83% 90.30%      1.46s  1.83%  compress/flate.hash4 (inline)
     1.43s  1.79% 92.09%     10.60s 13.25%  image/png.(*decoder).readImagePass
     1.42s  1.78% 93.86%      1.42s  1.78%  runtime.memmove
```

各関数の処理時間にはそれほど変化はないように見えますが、メモリ管理を行う関数の処理時間が大幅に減り、`image/color` パッケージの関数は皆無となっています。また全体の処理時間を見てみると、2.85分（2分51秒）から1.45分（1分27秒）へと約2倍高速に処理できていることが分かります。

ちなみに、処理後の画像全体のサイズは約67MBになっていました。

## 第二の改善: 適切なエンコーダを使う

今までPNG画像をエンコードするときは、関数 `image/png.Encode`を用いてきました。これはこれで手軽で便利なのですが、圧縮レベルを調節できず、Go言語にいいようにエンコードさせられていました。
そこで `image/png` パッケージをよく見てみると、圧縮レベルを調節するために構造体 `image/png.Encoder` が用意されていることに気づきます[^4]。今回はその中でも圧縮をより速く行えるように、圧縮レベルを `png.BestSpeed` に設定してエンコードしていきます。

```go
encoder := png.Encoder{CompressionLevel: png.BestSpeed}
for _, path := range GetPathAll() {
	...
	img, err := png.Decode(srcFile)
	...
	pix := img.(*image.NRGBA).Pix
	for i := 0; i < len(pix); i += 4 {
		pix[i] = 255 - pix[i]
		pix[i+1] = 255 - pix[i+1]
		pix[i+2] = 255 - pix[i+2]
	}
	...
	encoder.Encode(dstFile, img)
	...
}
```

今までと同じように計測結果を見ていきましょう！

```
Duration: 1.21mins, Total samples = 66.07s (90.69%)
Showing nodes accounting for 63.40s, 95.96% of 66.07s total
Dropped 136 nodes (cum <= 0.33s)
      flat  flat%   sum%        cum   cum%
    25.85s 39.13% 39.13%     39.38s 59.60%  image/png.filter
     6.39s  9.67% 48.80%      6.39s  9.67%  image/png.abs (inline)
     5.06s  7.66% 56.46%      9.73s 14.73%  image/png.paeth
     3.80s  5.75% 62.21%      3.80s  5.75%  image/png.abs8 (inline)
     3.55s  5.37% 67.58%      3.55s  5.37%  hash/adler32.update
     2.75s  4.16% 71.74%      4.47s  6.77%  image/png.filterPaeth
     2.53s  3.83% 75.57%      2.53s  3.83%  compress/flate.(*deflateFast).matchLen
     1.95s  2.95% 78.52%      1.95s  2.95%  runtime.memmove
     1.84s  2.78% 81.31%      1.84s  2.78%  main.ProcessSlice
     1.64s  2.48% 83.79%     12.30s 18.62%  image/png.(*decoder).readImagePass
     1.39s  2.10% 85.89%      1.72s  2.60%  compress/flate.(*huffmanEncoder).bitCounts
     0.99s  1.50% 87.39%      1.34s  2.03%  compress/flate.(*decompressor).huffSym
     0.73s  1.10% 88.50%      3.43s  5.19%  compress/flate.(*decompressor).huffmanBlock
     0.66s     1% 89.50%      3.59s  5.43%  compress/flate.(*deflateFast).encode
```

第一の改善の計測結果とほぼ同じ結果となりましたが、圧縮レベルを `png.BestSpeed` にしたため、圧縮を行う `compress/flate` パッケージで用いる関数が微妙に異なっています。具体的には、関数 `compress/flate.matchLen` が 関数 `compress/flate.(*deflateFast).matchLen` に、関数 `compress/flate.(*compressor).deflate` が 関数 `compress/flate.(*deflateFast).encode` へと、それぞれより高速に圧縮可能な関数を用いるように変更されています。

気になるのは、圧縮処理を速くしたことにより逆に圧縮率が落ちているのではないのか？というところですが、予想通り処理後の画像全体のサイズは約74MBとなりました。これは処理前に比べて約6MBの増加、画像1枚あたりでは約63KB増加したことになります。この増加量を多いと見るか少ないと見るかは、実際にPNG画像を処理するプログラムを運用する環境のリソースなど、コンテキストによるので一概には言えないのですが、今回は目を瞑ることとします。

すると計測結果より、処理全体の実行時間は第一の改善と比較して約1.2倍高速になりました！

## まとめ
- 各画素の読み書きを配列に対して直接行うことで約**2倍**高速化できる
- 適切なエンコーダを使うことでさらに約**1.2倍**高速化できる
- 全体で約**2.4倍**の高速化に成功した

## おわりに
今回は標準パッケージの範囲内でいかに高速に大量のPNG画像を処理できるか実験していきました。
もちろん使用する画像によって処理時間は変わってきます。ですが、上記の方法である程度の高速化は可能だと思います。
このほかに標準パッケージの範囲内でより高速化できる方法をご存知の方は、コメント欄にてご教示お願いします:bow:

## 余談
この記事を書くために `image/png` パッケージのソースコードを眺めていると、無駄な処理を発見してしまったのでちゃっかりコントリビュートしておきました:v:
https://go-review.googlesource.com/c/go/+/164199

[^1]: https://hoshi-sano.hatenablog.com/entry/2013/08/18/113434
[^2]: 圧縮を行う `compress/flate` パッケージの関数の実行時間をかき集めれば、フィルターの選択時間 ＜ 圧縮時間となるようです。
[^3]: [image/png.filter](https://golang.org/src/image/png/writer.go#L206) を読んでいただくと、一見各フィルタの`sum`を計算するたびに同じ行を走査しているためメモリアクセス効率が悪そうですが、実験した限りでは、それよりも`sum`が`best`を超すと即座に処理を中断（break）するほうが、処理速度は速くなる傾向にあるようです。
[^4]: `image/png.Encoder` は圧縮レベルを調節できるだけでなく、エンコードの際に使用するバッファを1つの処理内や複数の画像間で使いまわすためのプールも保持しています。`image/png.Encode` ではこの `image/png.Encoder` を毎回生成しているため、複数枚の画像をエンコードする場合はバッファプールを使いまわせず無駄が生まれることになります。しかし、`image/png.filter` などほかの処理により時間がかかっているため、全体の処理時間に対して、`image/png.Encoder` の生成コストはそれほど高くはありません。