Go言語の標準ライブラリに学ぶ関数の最適化

## 標準ライブラリを読もう！

事、コーディングに関して、ごくごく一般的な話であろうとは思いつつ、
改めて自分にはできてなかったなぁ、と学んだ話です。

弊社では、週1の頻度でGo言語の標準ライブラリを読む勉強会を行っています。
現在は[strings](https://golang.org/pkg/strings/)パッケージを輪読中で、まぁ、アセンブラありビット演算ありと、
一筋縄ではいかない現場のコードを日々楽しんでいます。

Go言語の標準ライブラリ輪読に期待している効果は幾つか想定しているつもりですが、
シンプルな言語仕様故に、

* 可読性が高い、読める
* コードゴルフな議論に陥りにくい
  * どんな言語でも通用するような本質的な議論がしやすい
* Go言語自身で書かれている標準ライブラリだって読める
  * 言語を造った人達の気持ちが学べる
  * そんな良質なコードからクンフーが積める
  * 標準ライブラリに精通できる

等の学びを期待しています。
そんな輪読会で個人的に得た学びの中から、印象的なものを幾つか書き残そうと思います。

各関数の挙動についての説明は、リファレンスとソースのコメントに譲ります。
Go言語はソースコードもさることながら、リファレンスも可読性が高いので是非ご一読下さい。

## できるだけなにもしない

[func IndexAny(s, chars string) int](https://github.com/golang/go/blob/master/src/strings/strings.go#L166-L191)

この関数はcharsの文字がsに含まれない場合には-1を返す仕様で、特にcharsが空文字の場合には
-1が返る仕様になっています。

で、シンプルにこんな感じで書かれています。

```go
// IndexAny returns the index of the first instance of any Unicode code point
// from chars in s, or -1 if no Unicode code point from chars is present in s.
func IndexAny(s, chars string) int {
	if chars == "" {
		// Avoid scanning all of s.
		return -1
	}
```

他にも、[func genSplit(s, sep string, sepSave, n int) []string](https://github.com/golang/go/blob/master/src/strings/strings.go#L233-L238)とか、こんな感じで。

```go
// Generic split: splits after each instance of sep,
// including sepSave bytes of sep in the subarrays.
func genSplit(s, sep string, sepSave, n int) []string {
	if n == 0 {
		return nil
	}
```

素朴で当たり前の様に見えますが、<font color="Red">**何もしないということ**</font>がいかに大切か身に沁みます。
<font color="Red">**なにもしなければ、バグもボトルネックも生まれません。**</font>
手を抜かずに、きちんと場合分けをして、なにもせずに済ませたいものです。

## 最適化できる場合を丁寧に選り分ける

[strings](https://golang.org/pkg/strings/)パッケージの中でよく見かけるのが、ASCII文字に対する最適化です。
[strings](https://golang.org/pkg/strings/)パッケージの関数はインターフェースとしてruneを許容するものが多いのですが、
その実装はASCIIだけの場合と、それ以外を分けて書いてある場合がほとんどです。

[func ToUpper(s string) string](https://github.com/golang/go/blob/master/src/strings/strings.go#L552-L579)

```go
// ToUpper returns a copy of the string s with all Unicode letters mapped to their upper case.
func ToUpper(s string) string {

...

	if isASCII { // optimize for ASCII-only strings.
		if !hasLower {
			return s
		}
		b := make([]byte, len(s))
		for i := 0; i < len(s); i++ {
			c := s[i]
			if c >= 'a' && c <= 'z' {
				c -= 'a' - 'A'
			}
			b[i] = c
		}
		return string(b)
	}

...
```

ちょっと[strings](https://golang.org/pkg/strings/)パッケージからは外れていますが・・・
[func ToLower(r rune) rune](https://github.com/golang/go/blob/master/src/unicode/letter.go#L261-L270)

```go
// ToLower maps the rune to lower case.
func ToLower(r rune) rune {
	if r <= MaxASCII {
		if 'A' <= r && r <= 'Z' {
			r += 'a' - 'A'
		}
		return r
	}
	return To(LowerCase, r)
}
```

これも、<font color="Red">**素朴な実装で済むものと、そうでないものが丁寧に分けて**</font>書かれています。
「ぼくがかんがえたさいきょうのアルゴリズム」でゴリ押しするのではなく、
ごく単純に、簡単に処理できるものとそうでないものを分けて処理する・・・という当たり前の実装です。

## 最後の手段として、一般的な場合を処理する

[func ToLower(s string) string](https://github.com/golang/go/blob/master/src/strings/strings.go#L582-L608)
[func Map(mapping func(rune) rune, s string) string](https://github.com/golang/go/blob/master/src/strings/strings.go#L454-L526)

```go
func ToLower(s string) string {
	isASCII, hasUpper := true, false
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= utf8.RuneSelf {
			isASCII = false
			break
		}
		hasUpper = hasUpper || (c >= 'A' && c <= 'Z')
	}

	if isASCII { // optimize for ASCII-only strings.
		if !hasUpper {
			return s
		}
		b := make([]byte, len(s))
		for i := 0; i < len(s); i++ {
			c := s[i]
			if c >= 'A' && c <= 'Z' {
				c += 'a' - 'A'
			}
			b[i] = c
		}
		return string(b)
	}
	return Map(unicode.ToLower, s)
}
```

`s string`を1文字毎にイテレーションするのが`Map`関数で、`unicode.ToLower`が処理の実態になります。
この手前まで、`ASCII-only strings`の場合と、既に全部小文字だった場合に何もしない場合分けが入っていて、<font color="Red">**runeを含む一般的な変換は最悪のケースとして最後に書かれています。**</font>

[func IndexAny(s, chars string) int](https://github.com/golang/go/blob/master/src/strings/strings.go#L166-L191)

```go
// IndexAny returns the index of the first instance of any Unicode code point
// from chars in s, or -1 if no Unicode code point from chars is present in s.
func IndexAny(s, chars string) int {
	if chars == "" {
		// Avoid scanning all of s.
		return -1
	}
	if len(s) > 8 {
		if as, isASCII := makeASCIISet(chars); isASCII {
			for i := 0; i < len(s); i++ {
				if as.contains(s[i]) {
					return i
				}
			}
			return -1
		}
	}
	for i, c := range s {
		for _, m := range chars {
			if c == m {
				return i
			}
		}
	}
	return -1
}
```

これも、`ASCII-only`である場合とそうでない場合を分けて、検索対象がからである場合には何もせずにreturn
しています。最後の`for`ループは総当りの検索になっていて、これをやるのは<font color="Red">**最悪の場合に限られて**</font>います。

## まとめ
* 処理が少なくて済むパターンを丁寧に分ける
* なにもしなくて済む場合には、何もしない
* 最悪のケースは、最後にやる

各々の場合分けも、漏れなく重複無く、イワユルMECEにできるよう気をつけねばなりません。
処理のレイヤーやモジュール構成等、的確に矛盾なくできるよう日頃から意識してないと、
この様な美しい書き方はできないです。少なくとも、一通りの実装ができて、テストも書けて、
リファクタリングがしっかり終わった後でないとこういう最適化はできないと思います。ただ、
これもコーディングのごく常識的な話ですね。

特別、Goに限った話ではない当たり前の事ばかりでしたが、日頃から丁寧にできているかと自問すると、
反省すべき部分が多々あり、クンフーが足りないと感じます。

第一線で活躍するエンジニア達のコードは、当たり前が当たり前にできているコードだと思いました（小並感）。