Goエンジニアに、おれはなる！

突然ですがGoエンジニアになろうと思いまして、Goの勉強を始めました。

GoはC/C++のように高速で動作し、Pythonのような高い生産性を持つ言語だそうです。強い(確信)。特別なランタイムを必要とせず、OSのライブラリを直接参照するため、実行環境がプラットフォームに依存しないというのも大きな特徴のようです。

Goは学習環境も充実している

Goはオンラインのドキュメントや学習教材がたくさんあり、簡単に入門することができます。私はまずA Tour of Goというドキュメントから入門しました。こちらは日本語にも翻訳されています。

go-tour-jp.appspot.com

今回のお話は、上のドキュメントで学習中に頭を抱えた内容です。

ゴルーチンに関する演習問題

ゴルーチン(Goroutines)とは、Goで並列処理を実現するための軽量スレッドです。スレッド間でデータを送受信したり同期したりするためにチャネルという便利な機能があるのですが、きちんと理解しておかないと私のようにハマります。

Goの言語仕様をきちんと理解されているエンジニアの方には何言ってんだという内容でしょうが、私自身の学習記録といて残しておきます。

問題設定

二分木(binary tree)に関する問題です。ふたつの二分木が与えられた時に、その二分木が同一の構造であることを判定しなさい、という問題です。

ここで使用している木構造は次のように定義されています。

type Tree struct {
    Left *Tree
    Value int
    Right *Tree
}

問題は、二分木が同一か判定するSame関数と、そこで二分木の中を走査するWalk関数を実装するというものです。それぞれ次のように定義が指定されています。

func Walk(t *tree.Tree, ch chan int)
func Same(t1, t2 *tree.Tree) bool

Walk関数の実装

二分木構造は自身の左側の葉には自身より小さい値が接続されていることが保証されているので、自身の左側→自身→自身の右側と走査していって、順に値をチャネルに突っ込んでいけば良いです。素直に実装すると次のようになると思います。

func Walk(t *tree.Tree, ch chan int) {
    if t.Left != nil {
        Walk(t.Left, ch)
    }

    ch <- t.Value

    if t.Right != nil {
        Walk(t.Right, ch)
    }
}

うん、たしかに左側→自身→右側と走査して値をチャネルに突っ込んでいる。これでうまくいくと思うじゃないですか。私は思いました。

実行するとデッドロックに陥る

とりあえずこれを実行するために呼び出し側を書いてみます。

func main() {
    ch := make(chan int)
    go Walk(tree.New(1), ch)

    // get value from channel
    for {
        v, ok := <-ch
        if !ok {
            break
        }
        fmt.Println(v)
    }
}

Walk関数の実行をゴルーチンに投げて、その結果をチャネルから順次受け取って表示します。 tree.New(k)は値が{k, 2k, 3k, ..., 10k}となるようなサイズ10の二分木を生成する関数です。

ちゃんとGoを理解されている方から見れば当然ですが、この実装だと全ての値を出力した後にデッドロックが発生して落ちます。

1
2
3
4
5
6
7
8
9
10

fatal error: all goroutines are asleep - deadlock!

何がだめなのか？

チャネルは明示的に閉じないと読み書きのタイミングでロックされる

チャネルから値を取り出そうとしたとき、チャネルが空の場合は新しい値が入ってくるまで処理待ちとなります。先ほどの例の場合、Walk関数によりchには10個の値が入りますが、受け取り側の　for文は無限ループになっているのでchが空になった11回目でも値を待ち受けてしまいます。

for {
    v, ok := <-ch  // ここで無限の待ち時間が発生する
    if !ok {
        break
    }
    fmt.Println(v)
}

安全に待ち受けるには、明示的にチャネルを閉じる

このような無限ループを抜けるために、チャネルを明示的に閉じる必要があります。チャネルを閉じるにはclose関数を使います。

close(ch)

上のfor文で何気なく実装していますが、チャネルから値を取り出す時、受け取る変数を2つ指定できます。この2つ目の戻り値はチャネルが空で、かつチャネルが閉じている場合にのみfalseとなります。

for {
    v, ok := <-ch
    if !ok {  // チャネルが空で閉じられているとfalseになる
        break
    }
    fmt.Println(v)
}

チャネルはどこで閉じる？

チャネルは木全体の走査とチャネルへの送信が終わったタイミングで閉じるべきです。先ほどのWalkの実装では再帰呼び出しをしているので、この関数内に処理を入れると木の走査途中でチャネルが閉じられてしまいます。タイミングとしては木のルートを引数とするWalkの後に閉じるべきです。現状の実装でそのようなタイミングはmain関数で出現していますが、ここでチャネルを閉じてはいけません。 Walk関数をゴルーチンで非同期実行しているため、木の走査中にチャネルが閉じられてしまう危険性があるからです。

go Walk(tree.New(1), ch)
close(ch)  // ここに書いてしまうと、Walk関数の処理と並行してチャネルを閉じようとしてしまう

では、どうするか

最初のWalk関数の実装を別関数として切り出してあげます。新しい関数を定義しても良いですが、 Walk関数内部で関数値(function value)として定義してもいいです。

func Walk(t *tree.Tree, ch chan int) {
    // 木全体を走査するロジックの実装
    var walker func(*tree.Tree)
    walker = func(t *tree.Tree) {
        if t.Left != nil {
            walker(t.Left)
        }
        ch <- t.Value
        if t.Right != nil {
            walker(t.Right)
        }
    }
    // 木のルートから走査を開始し、終わったらチャネルを閉じる
    walker(t)
    close(ch)
}

Walk関数内部で実際の走査を実装したwalkerという関数値を定義しています。これで、木全体を走査した後にチャネルを閉じるという処理を実現できました。

余談ですが

受け取り側のfor文はrangeを使うことでもう少しシンプルに書けます。

for v := range ch {
    fmt.Println(v)
}

rangeは先ほどの例のok = falseとなるまで自動的にループしてくれます。

Goエンジニアへの道のりは遠い

Goは最近作られた言語だけあって、処理をスマートかつ安全に書くためのノウハウが詰め込まれています。ここら辺をしっかり理解することが、イケてるGoエンジニアになるための第一歩でしょう。これからも頑張ります。

なまえはまだない

思いついたことをアウトプットします

Goに入門したら無事ゴルーチンでハマった話