owned this note
owned this note
Published
Linked with GitHub
###### tags: `blog`
# blurhash を実装した話
blurhash を go で実装、性能改善まで行いました。
性能改善した際の Tips や実装時に意識したこと、していることを共有します。
## はじめに
blurhash を実装し他の go での実装と比較して高速・省メモリを実現しました。
https://github.com/orisano/blurhash
```
goos: darwin
goarch: amd64
pkg: github.com/orisano/blurhash
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkEncode/orisano/png_204x204-8 1014 1164426 ns/op 16 B/op 1 allocs/op
BenchmarkEncode/orisano/png_316x178-8 760 1571802 ns/op 16 B/op 1 allocs/op
BenchmarkEncode/orisano/jpg_400x400-8 232 5108363 ns/op 24 B/op 1 allocs/op
BenchmarkEncode/orisano/jpg_2048x1365-8 13 84390556 ns/op 26 B/op 1 allocs/op
BenchmarkEncode/buckket/png_204x204-8 456 2666660 ns/op 179537 B/op 41641 allocs/op
BenchmarkEncode/buckket/png_316x178-8 330 3644907 ns/op 240887 B/op 56273 allocs/op
BenchmarkEncode/buckket/jpg_400x400-8 100 11628087 ns/op 534930 B/op 160025 allocs/op
BenchmarkEncode/buckket/jpg_2048x1365-8 6 197668054 ns/op 9048648 B/op 2795545 allocs/op
BenchmarkEncode/bbrks/png_204x204-8 9 124451622 ns/op 1998170 B/op 499441 allocs/op
BenchmarkEncode/bbrks/png_316x178-8 6 173214653 ns/op 2700549 B/op 675025 allocs/op
BenchmarkEncode/bbrks/jpg_400x400-8 3 462509202 ns/op 15360717 B/op 3840050 allocs/op
BenchmarkEncode/bbrks/jpg_2048x1365-8 1 7936703749 ns/op 268371664 B/op 67092533 allocs/op
PASS
ok github.com/orisano/blurhash 27.758s
```
### blurhash とは
@kawasy さんの記事に詳しいことが書かれています。
https://www.wantedly.com/companies/wantedly/post_articles/306561
Wolt というフードデリバリーアプリを作っている会社が作ったアルゴリズムで強くぼかしをかけた画像を短いバイト数で表現できるようにするものです。
強くぼかしがかかった画像でも表示されているだけで読み込んでいる感をあたえユーザーの体験を良くするのでそのために用いられます。
https://blurha.sh/
画像を 6 ~ 166 バイトの文字列表現に変換します、推奨されているのは 28 バイトになるようなパラメーターです。
アルゴリズムの概要は https://github.com/woltapp/blurhash/blob/master/Algorithm.md に書いてあります。
1. チャンネルごとに分離しR、G、Bそれぞれ独立に処理する。
3. sRGB 色空間から独自の空間に写す。$f(x) = {\frac{x+0.055}{1.055}}^{2.4}$
3. 2次元離散コサイン変換する。画像全体を $r$ 行 $c$ 列の周波数領域表現に写す。$(1 <= r, c <= 9)$
図：16 x 16 のときの 2次元離散コサイン変換の基底関数
図：各基底関数ごとの係数、白に近いほど大きい
図: JPEG で用いられる Zig-Zag Scan の順序で復元した過程のアニメーション
4. 交流成分を量子化する
5. 83 進数にエンコードして出力
* 1 バイト目: $r$ と $c$ を 2 桁の 9 進数表現したもの
* 2 バイト目: 量子化されたR、G、Bの交流成分の最大値
* 3~6 バイト目: R、G、Bの直流成分
* 7 バイト以降: 量子化されたR、G、Bの交流成分。1 つごとに 2 バイト、全体で $2(rc - 1)$ バイト
## 実装
目的は blurhash をよく理解するために車輪を再発明をすること。
実装する上で自ら課した制約は与えられた画像に比例したメモリ使用量にしない。（なにか制約があると面白いので）
まずはインターフェースを決めて実装を移植していきます。
個人的にインターフェースを決める時点で気にしているのはメモリの確保を極力使う側に委ねられるようにすることです。
```go=
func Encode(img image.Image, w, h int) string {}
```
よりも
```go=
func Append(dst []byte, img image.Image, w, h int) []byte {}
```
を選択することが多いです。 `Append` があれば `Encode` も提供できます。
```go=
func Encode(img image.Image, w, h int) string {
return string(Append(nil, img, w, h))
}
```
毎回メモリを確保して良いなら `Encode` を使えますし、メモリを使いまわしたいという要件なら `Append` が使えます。
実装が正しいか自分で確認するためにテストを書きます。
今回は参照実装が用意されているのでその出力と等しいかどうかを検証するだけで良いです。
性能を測定するためにベンチマークを書きます。go はテストと同じ感覚でベンチマークがかけるのでぜひ書きましょう。
標準の testing.B を使ってベンチマークを書くと付随して cpu profile を取る仕組みや memory profile を取る仕組みもついてくるのでお得です。
ベンチマークの結果はそれだけでは数値ですが、プロファイルなどを用いて分析した結果と合わせることで再利用可能なものになります。
ベンチマーク結果だけがあり、追加の分析を行っていないベンチマークは間違っていることが非常に多いです。
ベンチマークの落とし穴にはまらないようにアクティブベンチマークをしましょう。
http://www.brendangregg.com/activebenchmarking.html
go の testing.B は間違った使われ方をしているケースも見ます。
```go=
func BenchmarkFoo(b *testing.B) {
for i := 0; i < b.N; i++ {
// DO!
}
}
```
1. b.N 回ベンチマーク対象の関数を呼び出してください。
2. b.N を関数の入力に用いないでください。
この２つのルールは最低限守りましょう。
https://github.com/orisano/blurhash/tree/71aa27ac39018cd7fd3edaf0c49fcd6964a65a10
ベンチマークを書き、実行しました。
```
$ go test -bench . -benchmem -cpuprofile=cpu.pb.gz
goos: darwin
goarch: amd64
pkg: github.com/orisano/blurhash
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkEncode/orisano/png_204x204-8 9 117394702 ns/op 2000216 B/op 499392 allocs/op
BenchmarkEncode/orisano/png_316x178-8 7 160984328 ns/op 2702578 B/op 674976 allocs/op
BenchmarkEncode/orisano/jpg_400x400-8 3 401187533 ns/op 6149738 B/op 1920003 allocs/op
BenchmarkEncode/orisano/jpg_2048x1365-8 1 6773156296 ns/op 107402080 B/op 33546249 allocs/op
PASS
ok github.com/orisano/blurhash 13.700s
```
比較対象がいないので遅いのか速いのかわかりません。
ベンチマークをしたときは常に何故 2 倍速くできないのかを分析する必要があります。
```
32 . . for i := 0; i < h; i++ {
33 . . for j := 0; j < w; j++ {
34 . . var r, g, b float64
35 . . for y := 0; y < imgH; y++ {
36 . . for x := 0; x < imgW; x++ {
37 170ms 800ms basis := math.Cos(piW*float64(j*x)) * math.Cos(piH*float64(i*y))
38 90ms 1.14s pR, pG, pB, _ := img.At(x, y).RGBA()
39 110ms 3.65s r += basis * sRGB((pR>>8)&0xff).linear()
40 70ms 2.45s g += basis * sRGB((pG>>8)&0xff).linear()
41 60ms 2.03s b += basis * sRGB((pB>>8)&0xff).linear()
42 . . }
43 . . }
44 . . factors = append(factors, factor{
45 . . r: r,
46 . . g: g,
47 . . b: b,
48 . . })
49 . . }
50 . . }
```
どうやら sRBG 空間から独自の空間へ写す処理が重いことがわかりました。
これは解決策は非常にシンプルで sRBG 空間への入力は 256 パターンしかないので予め計算しておくだけで良いです。
https://github.com/orisano/blurhash/commit/47eeacd66fd19a3dc5ebfbc635332c8e6d152122#diff-4acdccd4f42f174e4532419bb2878b73daa65ccffa9f5d6aae103a2686d744f4
解決策が実装できたら効果の検証をする必要があります。
go には benchmark の出力結果からどれだけ影響があるか、統計的有意差はあるか確認する benchstat, benchcmp というツールがあります。
go test で指定できる count を使って複数回ベンチマークを行い検証します。
```
go test -bench . -benchmem -count=5 | tee old.txt
git checkout improved
go test -bench . -benchmem -count=5 | tee new.txt
benchstat old.txt new.txt
```
今回の変更では以下のような結果となりました。
```
name old time/op new time/op delta
Encode/orisano/png_204x204-8 115ms ± 1% 25ms ± 0% -78.08% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 157ms ± 1% 34ms ± 1% -78.11% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 393ms ± 2% 112ms ± 0% -71.62% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 6.63s ± 1% 1.87s ± 1% -71.78% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Encode/orisano/png_204x204-8 2.00MB ± 0% 2.00MB ± 0% ~ (p=0.952 n=5+5)
Encode/orisano/png_316x178-8 2.70MB ± 0% 2.70MB ± 0% ~ (p=0.913 n=5+5)
Encode/orisano/jpg_400x400-8 6.14MB ± 0% 6.14MB ± 0% ~ (p=0.897 n=5+5)
Encode/orisano/jpg_2048x1365-8 107MB ± 0% 107MB ± 0% ~ (p=0.841 n=5+5)
name old allocs/op new allocs/op delta
Encode/orisano/png_204x204-8 499k ± 0% 499k ± 0% ~ (all equal)
Encode/orisano/png_316x178-8 675k ± 0% 675k ± 0% ~ (all equal)
Encode/orisano/jpg_400x400-8 1.92M ± 0% 1.92M ± 0% ~ (all equal)
Encode/orisano/jpg_2048x1365-8 33.5M ± 0% 33.5M ± 0% ~ (p=0.730 n=5+4)
```
p値が一定以下にならないと delta は表示されないようになっています。
改善した後ももちろん何故 2 倍速くできないのかを分析する必要があります。
`math.cos` が律速になっています。4 重ループの中で計算されていますが無駄な計算が多いです。
テーブルを作ってキャッシュしましょう。
https://github.com/orisano/blurhash/commit/6abcf03cb605e17fb94f7fe2b0f85d8ef0d4f428#diff-4acdccd4f42f174e4532419bb2878b73daa65ccffa9f5d6aae103a2686d744f4
```
name old time/op new time/op delta
Encode/orisano/png_204x204-8 25.2ms ± 0% 11.9ms ± 1% -52.77% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 34.3ms ± 1% 16.2ms ± 1% -52.91% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 112ms ± 0% 56ms ± 2% -49.40% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 1.87s ± 1% 0.90s ± 1% -51.77% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Encode/orisano/png_204x204-8 2.00MB ± 0% 2.00MB ± 0% +0.18% (p=0.016 n=5+4)
Encode/orisano/png_316x178-8 2.70MB ± 0% 2.70MB ± 0% +0.16% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 6.14MB ± 0% 6.15MB ± 0% +0.10% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 107MB ± 0% 107MB ± 0% +0.03% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Encode/orisano/png_204x204-8 499k ± 0% 499k ± 0% +0.00% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 675k ± 0% 675k ± 0% +0.00% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 1.92M ± 0% 1.92M ± 0% +0.00% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 33.5M ± 0% 33.5M ± 0% -0.00% (p=0.016 n=4+5)
```
改善した後ももちろん何故 2 倍速くできないのかを分析する必要があります。
見てみると image.Image.At が重いことがわかります。画像形式によって image.Image を実装している型が異なることがあります。
jpeg は image.YCbCr, png は image.NRGBA です。その双方から使われている runtime.convT2Inoptr ですがこれはポインタ型でない値を interface に変換したときに内部で呼ばれます。malloc し値を memcpy してそのアドレスを inteface の内部データ構造の中に格納します。
image.Image.At は基本的に呼び出すたびにメモリ確保が発生してしまいます。
go の image が遅くなる原因はだいたいここにあります。
type switch でやってしまいがちですが重いループの中で頻繁に type switch するのは避けたいです。
アクセスのたびに type switch を書かないと行けないのも保守性の観点からも避けたいです。
今回はそれをうまく回避できる方法を発見しました。
ファクトリー関数を作り内部で type switch し image.Color を経由せずに RGBA を取得する方法です。
https://github.com/orisano/blurhash/commit/2482f3b95088506aa8860b3eb6f623203aaaf5f0#diff-4acdccd4f42f174e4532419bb2878b73daa65ccffa9f5d6aae103a2686d744f4
```
name old time/op new time/op delta
Encode/orisano/png_204x204-8 11.9ms ± 1% 4.6ms ± 2% -61.69% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 16.2ms ± 1% 6.2ms ± 3% -61.37% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 56.5ms ± 2% 41.0ms ± 5% -27.36% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 902ms ± 1% 655ms ± 1% -27.39% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Encode/orisano/png_204x204-8 2.00MB ± 0% 0.00MB ± 0% -99.82% (p=0.000 n=4+5)
Encode/orisano/png_316x178-8 2.70MB ± 0% 0.00MB ± 0% -99.84% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 6.15MB ± 0% 0.01MB ± 0% -99.90% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 107MB ± 0% 0MB ± 0% -99.97% (p=0.008 n=5+5)
name old allocs/op new allocs/op delta
Encode/orisano/png_204x204-8 499k ± 0% 0k ± 0% -100.00% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 675k ± 0% 0k ± 0% -100.00% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 1.92M ± 0% 0.00M ± 0% -100.00% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 33.5M ± 0% 0.0M ± 0% -100.00% (p=0.008 n=5+5)
```
改善した後ももちろん何故 2 倍速くできないのかを分析する必要があります。
RGBA が重いことがわかります。内部表現から RGBA に変換する処理が毎回実行されているので重くなっています。
これは前もって内部表現を image.RGBA に変換することで対応できますが追加のメモリ領域が必要になるので負けた気持ちになります。
ループの順序を変えることでピクセルに対するアクセスを減らすことができます。
https://github.com/orisano/blurhash/commit/132f6e4f0bad994d7d8991eae9b4e84d0a88c42b#diff-4acdccd4f42f174e4532419bb2878b73daa65ccffa9f5d6aae103a2686d744f4
```
name old time/op new time/op delta
Encode/orisano/png_204x204-8 4.57ms ± 2% 3.18ms ± 1% -30.39% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 6.24ms ± 3% 4.31ms ± 1% -31.00% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 41.0ms ± 5% 15.0ms ± 1% -63.57% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 655ms ± 1% 251ms ± 1% -61.65% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Encode/orisano/png_204x204-8 3.60kB ± 0% 0.07kB ± 0% -98.00% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 4.24kB ± 0% 0.07kB ± 0% -98.30% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 6.42kB ± 0% 0.07kB ± 0% -98.88% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 28.7kB ± 0% 0.1kB ± 0% -99.72% (p=0.000 n=5+4)
name old allocs/op new allocs/op delta
Encode/orisano/png_204x204-8 3.00 ± 0% 3.00 ± 0% ~ (all equal)
Encode/orisano/png_316x178-8 3.00 ± 0% 3.00 ± 0% ~ (all equal)
Encode/orisano/jpg_400x400-8 3.00 ± 0% 3.00 ± 0% ~ (all equal)
Encode/orisano/jpg_2048x1365-8 3.00 ± 0% 3.00 ± 0% ~ (all equal)
```
改善した後ももちろん何故 2 倍速くできないのかを分析する必要があります。
ループ順を逆にしたことによって cos のキャッシュが小さくなってしまったのでこれによってまた cos が律速になってしまいました。
どうにかして cos の回数を減らしたいと考えたときに過去のキャッシュを用いる方法が使えることに気が付きました。
過去の cos の値と次に必要になる cos の値に関係があり、加法定理を用いることで求めることができます。
https://github.com/orisano/blurhash/commit/e202db88dad10c4aaa409579de16a5f50daf2f01
```
name old time/op new time/op delta
Encode/orisano/png_204x204-8 3.18ms ± 1% 1.26ms ± 2% -60.26% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 4.31ms ± 1% 1.69ms ± 2% -60.83% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 15.0ms ± 1% 6.1ms ± 2% -59.30% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 251ms ± 1% 102ms ± 1% -59.54% (p=0.008 n=5+5)
name old alloc/op new alloc/op delta
Encode/orisano/png_204x204-8 72.0B ± 0% 240.0B ± 0% +233.33% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 72.0B ± 0% 240.0B ± 0% +233.33% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 72.0B ± 0% 240.0B ± 0% +233.33% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 80.0B ± 0% 242.6B ± 0% +203.25% (p=0.016 n=4+5)
name old allocs/op new allocs/op delta
Encode/orisano/png_204x204-8 3.00 ± 0% 9.00 ± 0% +200.00% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 3.00 ± 0% 9.00 ± 0% +200.00% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 3.00 ± 0% 9.00 ± 0% +200.00% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 3.00 ± 0% 9.00 ± 0% +200.00% (p=0.008 n=5+5)
```
加法定理を使うために必要なメモリが増えていることがわかります。
改善した後ももちろん何故 2 倍速くできないのかを分析する必要があります。
Append そのものが重くなっています。line by line で分析しましょう。
```
63 130ms 140ms for j := range xCos {
64 60ms 60ms if x == 0 || j == 0 {
65 30ms 30ms xSin[j], xCos[j] = 0, 1
66 . . } else {
67 210ms 310ms xSin[j], xCos[j] = rotate(xSin[j], xCos[j], xRotSin[j], xRotCos[j])
68 . . }
69 . . }
70 140ms 1.73s pR, pG, pB, _ := fastAt(x, y)
71 20ms 20ms r := sRGB((pR >> 8) & 0xff).linear()
72 70ms 70ms g := sRGB((pG >> 8) & 0xff).linear()
73 20ms 20ms b := sRGB((pB >> 8) & 0xff).linear()
74 110ms 110ms for i := 0; i < h; i++ {
75 190ms 190ms for j := 0; j < w; j++ {
76 110ms 110ms basis := yCos[i] * xCos[j]
77 1.13s 1.13s factors[i*w+j].r += basis * r
78 480ms 480ms factors[i*w+j].g += basis * g
79 280ms 280ms factors[i*w+j].b += basis * b
80 . . }
81 . . }
```
ピクセルへのアクセス、係数を求めるための浮動小数演算が重いことがわかりました。
浮動小数演算の箇所は SIMD を使うことで高速化できそうですが go で気軽に使える手段ではありません。
ピクセルへのアクセスの YCbCr から RBGA への変換のコードは改善できる余地はなさそうでした。
メモリ使用量についての改善ですが、速度の改善を行っているうちにいくつかの問題は解決されました。
最後は小手先のテクニックで改善を行います。
スライスの長さが小さいとわかっているときに使える malloc を回避する手法です。
```go=
a = make([]int, w)
```
とするのではなく, w の上限値がわかっている場合に (例では9)
```go=
a = make([]int, 9)[:w]
```
とすることでスタックに配置される可能性が出てきます。コンパイラは上限値について知らないのでこのような最適化は現時点ではできず、ヒープにアロケーションしてしまいます。
https://github.com/orisano/blurhash/commit/a9348c7ae56e0ce6e66048b67bc6e719f5822f0c
```
name old time/op new time/op delta
Encode/orisano/png_204x204-8 1.26ms ± 2% 1.21ms ± 3% -4.56% (p=0.016 n=5+5)
Encode/orisano/png_316x178-8 1.69ms ± 2% 1.65ms ± 1% -2.18% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 6.09ms ± 2% 6.14ms ± 1% ~ (p=0.151 n=5+5)
Encode/orisano/jpg_2048x1365-8 102ms ± 1% 100ms ± 0% -1.36% (p=0.016 n=5+5)
name old alloc/op new alloc/op delta
Encode/orisano/png_204x204-8 240B ± 0% 16B ± 0% -93.33% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 240B ± 0% 16B ± 0% -93.33% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 240B ± 0% 16B ± 0% -93.33% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 243B ± 0% 18B ± 0% -92.58% (p=0.000 n=5+4)
name old allocs/op new allocs/op delta
Encode/orisano/png_204x204-8 9.00 ± 0% 1.00 ± 0% -88.89% (p=0.008 n=5+5)
Encode/orisano/png_316x178-8 9.00 ± 0% 1.00 ± 0% -88.89% (p=0.008 n=5+5)
Encode/orisano/jpg_400x400-8 9.00 ± 0% 1.00 ± 0% -88.89% (p=0.008 n=5+5)
Encode/orisano/jpg_2048x1365-8 9.00 ± 0% 1.00 ± 0% -88.89% (p=0.008 n=5+5)
```
この変更でメモリ確保の量が 240B から 16B に、回数が 9 回から 1 回になりました。
残りの 1 回はファクトリ関数が返す関数オブジェクトのものでこれは削れなさそうです。
これで今回の性能改善を終わりとしました。
これ以上速くしたい場合は2次元離散コサイン変換を高速コサイン変換にするなどが考えられます。
Wolt のリポジトリではリサイズした後に画像に対して blurhash を適用するので高速である必要がないと書いてあります。
でも高速だと嬉しいのでやりました。後悔はしていません。
Sign in with Wallet
