Big Sky

記事中に間違いがありました。数倍も速くはなりませんでした。確か 1.0X ～ 1.1 倍程度の高速化は得られましたがびっくりするほどの物ではありませんでした。すみません。

そろそろ Go1.7 がリリースされるそうですが、皆さん如何お過ごしですか。Go 界隈の波平こと mattn ですこんにちわ。ﾊﾞｶﾓｰ(略

Go1.7 ではコンパイラの最適化が行われ、ビルド速度がかなり短縮される様になりました。毎日ビルドしてる僕としては非常に嬉しい機能改善ですね。

さてとてもキャッチ―なタイトルで釣ってしまった訳ですが、気にしたら負けなのでどんどん話を進めます。

var t [256]byte

func f(b *[16]byte) {
    for i, v := range b {
        b[i] = t[v]
    }
}


例えばこのコードを見て下さい。このコードはココから拝借しました。issue の内容はスコープ外の t を参照している為、LEAQ がバイトコード出力されるのですがこれによりパフォーマンスが落ちるというもの。LEAQ とはスレッド固有変数にアクセスする為の x64 TLS 命令です。

例えば以下のコードを go tool compile -S foo.go でバイトコード出力します。

package main

var t [256]byte

func f(b []byte) {
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func main() {
}


すると以下のアセンブリが出力されます。

0x002f 00047 (s1.go:7)  TESTQ   CX, CX
0x0032 00050 (s1.go:7)  JEQ $0, 149
0x0034 00052 (s1.go:7)  MOVQ    BX, AX
0x0037 00055 (s1.go:7)  CMPQ    CX, $-1
0x003b 00059 (s1.go:7)  JEQ 144
0x003d 00061 (s1.go:7)  CQO
0x003f 00063 (s1.go:7)  IDIVQ   CX
0x0042 00066 (s1.go:7)  MOVQ    BX, SI
0x0045 00069 (s1.go:7)  SARQ    $63, BX
0x0049 00073 (s1.go:7)  MOVBQZX BL, BX
0x004c 00076 (s1.go:7)  LEAQ    (SI)(BX*1), DI
0x0050 00080 (s1.go:7)  MOVBQZX DIB, DI
0x0054 00084 (s1.go:7)  SUBQ    BX, DI
0x0057 00087 (s1.go:7)  CMPQ    DI, $256
0x005e 00094 (s1.go:7)  JCC $0, 137
0x0060 00096 (s1.go:7)  LEAQ    "".t(SB), BX
0x0067 00103 (s1.go:7)  MOVBLZX (BX)(DI*1), BX
0x006b 00107 (s1.go:7)  CMPQ    DX, CX
0x006e 00110 (s1.go:7)  JCC $0, 137
0x0070 00112 (s1.go:7)  MOVQ    "".b+8(FP), DI
0x0075 00117 (s1.go:7)  MOVB    BL, (DI)(DX*1)
0x0078 00120 (s1.go:6)  LEAQ    1(SI), BX
0x007c 00124 (s1.go:7)  MOVQ    DI, DX
0x007f 00127 (s1.go:6)  CMPQ    BX, $100000000
0x0086 00134 (s1.go:6)  JLT $0, 47


ループ内で毎回 LEAQ を実行しているのが分かるかと思います。golang の場合、goroutine で外部から t を書き換えられる、もしくは t に nil を代入出来てしまう為、厳密にループ途中で新しい t を参照したり nil リファレンス例外を出すためにはループ内で LEAQ を使って毎回 t を参照しなければなりません。

しかし TLS 命令はある程度コストの掛かる命令です。そこで以下の1行を足します。

var t [256]byte

func f(b []byte) {
    t := t // ココ
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}


一見まったく意味のなさそうなコードに見えますが、これにより t が関数内に束縛され TLS 関数を使う必要がなくなります。もう一度アセンブリを見てみましょう。

0x0057 00087 (s2.go:7)  MOVQ    "".b+272(FP), AX
0x005f 00095 (s2.go:7)  MOVQ    $0, CX
0x0061 00097 (s2.go:7)  CMPQ    CX, $100000000
0x0068 00104 (s2.go:7)  JGE $0, 181
0x006a 00106 (s2.go:8)  MOVQ    CX, DX
0x006d 00109 (s2.go:8)  SARQ    $63, CX
0x0071 00113 (s2.go:8)  MOVQ    CX, BX
0x0074 00116 (s2.go:8)  ANDQ    $15, CX
0x0078 00120 (s2.go:8)  LEAQ    (DX)(CX*1), SI
0x007c 00124 (s2.go:8)  ANDQ    $15, SI
0x0080 00128 (s2.go:8)  SUBQ    CX, SI
0x0083 00131 (s2.go:8)  MOVBQZX BL, CX
0x0086 00134 (s2.go:8)  LEAQ    (DX)(CX*1), BX
0x008a 00138 (s2.go:8)  MOVBQZX BL, BX
0x008d 00141 (s2.go:8)  SUBQ    CX, BX
0x0090 00144 (s2.go:8)  CMPQ    BX, $256
0x0097 00151 (s2.go:8)  JCC $0, 197
0x0099 00153 (s2.go:8)  MOVBLZX "".t(SP)(BX*1), CX
0x009d 00157 (s2.go:8)  TESTB   AL, (AX)
0x009f 00159 (s2.go:8)  CMPQ    SI, $16
0x00a3 00163 (s2.go:8)  JCC $0, 197
0x00a5 00165 (s2.go:8)  MOVB    CL, (AX)(SI*1)
0x00a8 00168 (s2.go:7)  LEAQ    1(DX), CX
0x00ac 00172 (s2.go:7)  CMPQ    CX, $100000000
0x00b3 00179 (s2.go:7)  JLT $0, 106


今度は t に関する LEAQ が消えました。実際にどれくらい効果があるのかベンチマークを書いてみました。

package main

import "testing"

var t [256]byte

func f1(b []byte) {
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func f2(b []byte) {
    t := t
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func BenchmarkWithLEAQ(b *testing.B) {
    var m [16]byte
    f1(m[:])
}

func BenchmarkWithoutLEAQ(b *testing.B) {
    var m [16]byte
    f2(m[:])
}


ベンチマークの実行は go test -bench . で行います。結果は以下の通り。

BenchmarkWithLEAQ-4                    1        1035500000 ns/op
BenchmarkWithoutLEAQ-4                 3         334666666 ns/op
PASS
ok      github.com/mattn/leaq   4.722s


たった1行で3倍1.0X倍から1.1倍程度のパフォーマンスアップが出来ました。この様に、並行でアクセス可能な変数をローカルで拘束する事で簡単に高速化が行えました。地味なテクニックですが手持ちの処理が遅くて困ってる人は一度試してみては如何でしょうか。なお、このテクニックはループ回数が多い場合に効いてきます。逆にループ回数が少ないと冒頭の LEAQ 分だけ損してしまう為、上記の f1/f2 を多い回数ループすると逆に f1 の方が速くなります。この辺はコンパイラの気持ちになって考えると答えが出てくるかもしれません。

変数のアトミック性を TLS を使って同期して実現してるのだと思ってましたが間違っていましたので記事を修正しました。

次回予告「並列ダウンロードするHTTPクライアントをバンド幅制限するサーバをGoで実装した」 / “高速でダウンロードできるツールを Go で実装した。 - Qiita” https://t.co/6NfEyJCwbu

— Kazuho Oku (@kazuho) July 13, 2016

並列ダウンローダを使うと幾らかサーバに負荷が掛かってしまいます。golang のサーバ側で帯域制限を行う場合には2つ方法があります。

• 転送量制限する
• 接続数制限する

まずは転送量制限。転送量の制限には throttled が便利です。

GitHub - throttled/throttled: Package throttled implements rate limiting access to resources such as HTTP endpoints.

README.md Throttled Package throttled implements rate limiting access to resources such as HTTP endp...

https://github.com/throttled/throttled

http.Handler 互換のミドルウェアなので既存のサーバに埋め込む形で使えます。 store, err := memstore.New(65536)
if err != nil {
    log.Fatal(err)
}

quota := throttled.RateQuota{throttled.PerMin(20), 5}
rateLimiter, err := throttled.NewGCRARateLimiter(store, quota)
if err != nil {
    log.Fatal(err)
}

httpRateLimiter := throttled.HTTPRateLimiter{
    RateLimiter: rateLimiter,
    VaryBy:      &throttled.VaryBy{Path: true},
}

http.ListenAndServe(":8080", httpRateLimiter.RateLimit(myHandler))


次に接続数制限。接続数制限には netutil.LimitedListener を使います。

netutil - GoDoc

package netutil import "golang.org/x/net/netutil" Package netutil provides network utility functions...

https://godoc.org/golang.org/x/net/netutil#LimitListener

こちらは net.Listener にかぶせるだけで最大接続本数を制限できます。

package main

import (
    "fmt"
    "golang.org/x/net/netutil"
    "log"
    "net"
    "net/http"
)

func main() {
    l, err := net.Listen("tcp", ":8080")
    if err != nil {
        log.Fatal(err)
    }
    http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
        fmt.Fprintf(w, "")
    })
    http.Serve(netutil.LimitListener(l, 100), http.DefaultServeMux)
}


今年の夏も暑そうですが、頑張って乗り切りましょう。

golang の channel は他の言語に見ない独特のパラダイムを開発者に提供します。

単純にスレッド間でメッセージングをするだけでもC言語で書けばそこそこの量になったり、慣れていない人であればどう実装すればいいか分からないなんて事もあったと思います。しかし golang の goroutine/channel は、やっている内容の割にとても容易にスレッド間通信やキューイング、処理の受け待ち等を実装できる様になっています。尚、channel をどの様に適用したら良いかについては以下を参照下さい。

Big Sky :: Golang の channel の使い所

golang の特徴と言えば goroutine と channel ですが、その使いどころに悩む人もおられる様です。 goroutine は非同期に実行される処理、channel はその grout...

http://mattn.kaoriya.net/software/lang/go/20131112132831.htm

今日はその goroutine/channel を使ったテクニックを3つほど紹介したいと思います。

ポーリング

channel は一般的に goroutine 側で chan への送信を行い、メイン処理側で chan の受信を行う事が多いと思います。

package main

import (
    "time"
)

func main() {
    q := make(chan struct{})

    go func() {
        // 重たい処理
        time.Sleep(3 * time.Second)
        q <- struct{}{}
    }()

    // q に何か入るまで待つ
    <-q
}


しかしメイン処理側でも待ち時間でやりたい事があったりもします。そういった場合にもう一つ goroutine/channel を作って...という方法もアリですが実は channel のポーリングは len(q) を使って簡単に実装できます。len(q) はその時点で channel に溜まったキューの数を返します。アトミックです。

package main

import (
    "fmt"
    "time"
)

func main() {
    q := make(chan struct{}, 2)

    go func() {
        // 重たい処理
        time.Sleep(3 * time.Second)
        q <- struct{}{}
    }()

    for {
        if len(q) > 0 {
            break
        }

        // q に溜まるまで他の事をしたい
        time.Sleep(1 * time.Second)
        fmt.Println("何か")
    }
}


こうする事で、q が送信されるまで別の処理を実できる様になります。GUI のメッセージループと channel を組み合わせる場合などには有効な手段です。注意点としては make で channel を作成する際に、バッファ数を 2 以上に設定しなければならない点です。そうしないと len(q) は常に 0 を返し続けます。

キューイング

例えば channel の受信をトリガにしてデータベースに接続して更新処理を実行する処理を実装するとします。複数のトリガが同時に発生した場合、channel には更新リクエストが溜まっていく訳ですが出来れば1回のデータベース接続で溜まった分全ての更新リクエストを処理したいといったケースもあります。あり得るケースで言えばデータベース接続が遅いなど。そこで登場するのが time.After との組み合わせです。

package main

import (
    "fmt"
    "time"
)

func main() {
    q := make(chan string, 5)

    go func() {
        time.Sleep(3 * time.Second)
        q <- "foo"
    }()
    go func() {
        time.Sleep(3 * time.Second)
        q <- "bar"
    }()

    // ほぼ同時に2つトリガが発生するのが分かっている
    var cmds []string
    cmds = append(cmds, <-q) // まずは一つ受信する
wait_some:
    for {
        select {
        case cmd := <-q:
            // 1秒以内なら一緒に処理しちゃうよ
            cmds = append(cmds, cmd)
        case <-time.After(1 * time.Second):
            // 1秒過ぎたらもう受け付けないよ
            break wait_some
        }
    }
    for _, cmd := range cmds {
        fmt.Println(cmd)
    }
}


この様に time.After が作る1秒間タイマー(実際は channel)とコマンド要求 channel を同時に待つ事で簡単に実装できます。これを他の言語で実装しようと考えるとちょっと頭がクラッとしてしまうかもしれませんね。

ワーカー

goroutine/channel を使えばワーカースレッドも簡単に作れます。例えば仕事量が5個あり、それを3つのワーカースレッドで仕事を取り合う物を実装したい場合は以下の様に実装します。

package main

import (
    "fmt"
    "sync"
    "time"
)

func fetchURL(wg *sync.WaitGroup, q chan string) {
    // 注意点: ↑これポインタな。
    defer wg.Done()
    for {
        url, ok := <-q // closeされると ok が false になる
        if !ok {
            return
        }

        fmt.Println("ダウンロード: ", url)
        time.Sleep(3 * time.Second)
    }
}
func main() {
    var wg sync.WaitGroup

    q := make(chan string, 5)

    // ワーカーを3つ作る
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go fetchURL(&wg, q)
    }

    // 同時には3つまでしか処理できない
    q <- "http://www.example.com"
    q <- "http://www.example.net"
    q <- "http://www.example.net/foo"
    q <- "http://www.example.net/bar"
    q <- "http://www.example.net/baz"
    close(q) // これ大事

    wg.Wait() // すべてのgoroutineが終了するのをまつ
}
channel の受信処理 url, ok := <-q は channel が閉じられると2つ目の戻り値に false を返します。なので各ワーカースレッドはそれが true である間は channel からジョブを受け取って処理すれば良い事になります。

可能性はまだまだある

goroutine/channel の可能性はまだまだあると思っています。軽量なのでどんどん使っていけば良いですし、「こんな簡単な物に channel を使うのは大げさだ」と考える必要もないと思います。例えば peco では内部で大量に channel が使われていますがキビキビと動作します。CUI と golang の channel については昔に書かせて頂いた Gopher Academy の Advent Calendar 2013 でも紹介しています。

まだまだ channel を使った技はありそうなので、イイカンジのテクニックが出来たらぜひ情報発信して皆で共有して欲しいです。