標準ライブラリの動向とイテレータのパフォーマンス

Goのイテレータ深堀Night
https://findy.connpass.com/event/328543/

Transcript

1. 標準ライブラリの動向と イテレータのパフォーマンス Goのイテレータ深堀りNight
2. 自己紹介 • 牧内大輔 ◦ MakKi ◦ https://makiuchi-d.github.io/ • KLab株式会社 ◦ スマホゲームとかつくってます ◦ オンライン対戦の中継サーバを Goで書いたり ▪ github.com/KLab/WSNet2 いつのまにかGo歴10年…… @makki_d makiuchi-d
3. 標準ライブラリの動向
4. 見ておくべきプロポーザル • iter: new package for iterators #61897 ◦ iterパッケージを追加する提案（実装済み） ◦ 関連プロポーザルのリンクもまとまっている
5. Go 1.23.0 で使えるようになったもの • iter #61897 ◦ Seq[V], Seq2[K, V] ◦ Pull, Pull2 • maps #61900 ◦ All, Keys, Values, Insert, Collect • slices #61899, #53987 ◦ All, Backward, Values, AppendSeq, Collect, Sorted, SortedFunc, SortedStableFunc, Chunk
6. これから使えるようになりそうなもの • bytes, strings: add iterator forms of existing functions #61901 ◦ 分割後のスライスを構築することなく反復処理 ◦ Accepted, masterブランチにマージ済み ◦ Lines, SplitSeq, SplitAfterSeq, FieldsSeq, FieldsFuncSeq • regexp: add iterator forms of matching methods #61902 ◦ FindAllなどのように複数のマッチ結果をスライスで返すもののイテレータ版 ◦ All, AllIndex, AllString, AllStringIndex, AllStringSubmatch, AllStringSubmatchIndex, AllSubmatch, AllSubmatchIndex
7. 準標準パッケージ • golang.org/x/exp/xiter: new package with iterator adapters #61898 ◦ イテレータを介してシーケンスに対する汎用処理を提供 ▪ slicesパッケージに対してプロポーザルが出されていた機能を含む • slices.Allなどの存在価値はここにありそう ▪ 今後iterパッケージに移す可能性も ◦ Concat, Concat2, Equal, Equal2, EqualFunc, EqualFunc2, Filter, Filter2, Map, Map2, Merge, Merge2, MergeFunc, MergeFunc2, Reduce, Reduce2, Zip, Zip2
8. 命名規約（Allメソッド） • 全要素を反復するイテレータのメソッド名は慣習的に「All」とする ◦ ただし標準パッケージでの実装はまだ進んでいなさそう • サードパーティライブラリも「All」として実装するとよい # Naming Conventions Iterator functions and methods are named for the sequence being walked: // All returns an iterator over all elements in s. func (s *Set[V]) All() iter.Seq[V] The iterator method on a collection type is conventionally named All, because it iterates a sequence of all the values in the collection. src/iter/iter.go のコメント
9. まとめ 1 • イテレータを扱う機能はこれからも増えていきそう ◦ 既に使える iter, slices, maps ◦ このあと入りそう bytes, strings, regexp ◦ 注目の準標準パッケージ golang.org/x/exp/xiter ◦ 様々な型にイテレータを返すメソッドが増えそう
10. イテレータのパフォーマンス
11. 題材: github.com/makiuchi-d/linq • C#のLINQをGoの型パラメータを使って実装 ◦ コレクションに対してクエリ操作をするライブラリ ◦ 詳しくはGo Conference 2022 Springの発表にて ▪ 型パラメータが使えるようになったので LINQを実装してみた • ただし発表後v2になったため一部異なります src := []int{3, 8, 2, 1, 5, 7, 4, 6} e1 := linq.FromSlice(src) e2 := linq.Where(e1, func(n int) (bool, error) { return n%2 == 0, nil }) e3 := linq.OrderBy(e2, func(n int) (int, error) { return n, nil }) s, _ := linq.Aggregate(e3, "", func(s string, n int) (string, error) { return fmt.Sprintf("%s%d,", s, n), nil }) fmt.Println(s) // "2,4,6,8,"
12. イテレータの実装 • Allメソッドを定義 ◦ Enumerator[T].Next()で1要素ずつ取り出しyieldに渡す ▪ errorを渡すため、引数2個のyield ◦ linq.ForEach(...)とほぼ一緒 func (e Enumerable[T]) All() iter.Seq2[T, error] { return func(yield func(T, error) bool) { er := e() // GetEnumerator for { v, err := er.Next() if err != nil { if isEOC(err) { return } yield(v, err) return } if !yield(v, nil) { return } } } } func ForEach[T any, E IEnumerable[T]](src E, f func(T) error) error { e := src() // GetEnumerator for { v, err := e.Next() if err != nil { if isEOC(err) { return nil } return err } err = f(v) if err != nil { return err } } }
13. ベンチマークコード • 3種類の方法を比較 ◦ forループでNextを呼ぶ ◦ linq.ForEach関数 ◦ イテレータでfor range var src = linq.Range(0, 100000) func BenchmarkFor(b *testing.B) { for range b.N { e := src() for { _, err := e.Next() if err != nil { if errors.Is(err, linq.EOC) { break } } } } } func BenchmarkForEach(b *testing.B) { for range b.N { linq.ForEach(src, func(n int) error { return nil }) } } func BenchmarkIterator(b *testing.B) { for range b.N { for _, _ = range src.All() { } } } 余談：ベンチマークに range over intが便利
14. ベンチマーク結果 • 単純なforループが最速 • イテレータ遅い…… ◦ yield関数呼び出しオーバーヘッド ▪ アセンブリ出力でもCALL命令 ◦ linq.ForEach よりなぜか遅い BenchmarkFor-8 28212 213164 ns/op 24 B/op 1 allocs/op BenchmarkForEach-8 18822 319507 ns/op 24 B/op 1 allocs/op BenchmarkIterator-8 15828 377198 ns/op 24 B/op 1 allocs/op
15. 微修正したらパフォーマンス改善？ • e()呼び出しをイテレータ関数の外に移動 • パフォーマンスがForEach相当に…… なぜ? func (e Enumerable[T]) All() iter.Seq2[T, error] { er := e() return func(yield func(T, error) bool) { er := e() for { v, err := er.Next() if err != nil { if isEOC(err) { return } yield(v, err) return } if !yield(v, nil) { return } } } }
16. まとめ 2 • イテレータはやや遅いかも ◦ yield関数呼び出しオーバーヘッドは避けられなさそう ◦ わずかなコードの違いでパフォーマンスがさらに下がることも ◦ 今後の最適化に期待