2020/04/04


Go でスライスに挿入する例として Go の Wiki に以下の物が記載されている。

しかしこのコードは、挿入されるスライスから部分スライスを取り出し、そこに挿入するスライスを append に割り当てる為に展開し、さらに残りの部分スライスも append に割り当てる展開を行っている。なので実装コードとしては短いが、実際に実行されるオペレーションコードが冗長になる。また、スライスの伸長はおよそ2倍ずつ増える。なので例えば 5000 個のスライスに 1000 個のアイテムを挿入すると、キャパシティはおよそ 12000 近くになる。Go ではこういったスライスの操作も、基本的には自身で make によりメモリを確保し、ループで値を割り当てるのが良い(面倒かもしれないがその方がメモリも節約され速い)とされている。

以下、ベンチマークを取ってみる。

package main_test

import (
    "reflect"
    "testing"
)

type T int

func BenchmarkAppend(b *testing.B) {
    b.ResetTimer()

    input := make([]int5000)
    for i := 0; i < 5000; i++ {
        input[i] = i
    }
    insert := make([]int1000)
    for i := 0; i < 1000; i++ {
        insert[i] = i
    }
    expected := make([]int6000)
    for i := 0; i < 6000; i++ {
        if i < 1000 {
            expected[i] = i
        } else if i < 2000 {
            expected[i] = i - 1000
        } else {
            expected[i] = i - 1000
        }
    }
    n := 1000
    var output []int

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        output = append(input[:n], append(insert, input[n:]...)...)
    }
    b.StopTimer()
    if !reflect.DeepEqual(output, expected) {
        b.Fatal("bad insertion")
    }
}

func BenchmarkNormal(b *testing.B) {
    input := make([]int5000)
    for i := 0; i < 5000; i++ {
        input[i] = i
    }
    insert := make([]int1000)
    for i := 0; i < 1000; i++ {
        insert[i] = i
    }
    expected := make([]int6000)
    for i := 0; i < 6000; i++ {
        if i < 1000 {
            expected[i] = i
        } else if i < 2000 {
            expected[i] = i - 1000
        } else {
            expected[i] = i - 1000
        }
    }
    n := 1000
    var output []int

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        output = make([]intlen(input)+len(insert))
        for l := 0; l < n; l++ {
            output[l] = input[l]
        }
        for l := 0; l < len(insert); l++ {
            output[l+n] = insert[l]
        }
        for l := n; l < len(input); l++ {
            output[l+len(insert)] = input[l]
        }
    }
    b.StopTimer()
    if !reflect.DeepEqual(output, expected) {
        b.Fatal("bad insertion")
    }
}

func BenchmarkCopy(b *testing.B) {
    input := make([]int5000)
    for i := 0; i < 5000; i++ {
        input[i] = i
    }
    insert := make([]int1000)
    for i := 0; i < 1000; i++ {
        insert[i] = i
    }
    expected := make([]int6000)
    for i := 0; i < 6000; i++ {
        if i < 1000 {
            expected[i] = i
        } else if i < 2000 {
            expected[i] = i - 1000
        } else {
            expected[i] = i - 1000
        }
    }
    n := 1000
    var output []int

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        output = make([]intlen(input)+len(insert))
        copy(output, input[:n])
        copy(output[n:], insert)
        copy(output[n+len(insert):], input[n:])
    }
    b.StopTimer()
    if !reflect.DeepEqual(output, expected) {
        b.Fatal("bad insertion")
    }
}
BenchmarkAppend-8          42700             26185 ns/op
BenchmarkNormal-8          70170             18005 ns/op
BenchmarkCopy-8            90902             15787 ns/op

Wiki に載っているコードは、手動でスライスを挿入するコードの1.5~2倍遅い。copy を使うともう少し速い。

みんなのGo言語[現場で使える実践テクニック] みんなのGo言語[現場で使える実践テクニック]
松木雅幸, mattn, 藤原俊一郎, 中島大一, 牧大輔, 鈴木健太
技術評論社 Kindle版 / ¥2,178 (2016年09月09日)
 
発送可能時間:

Posted at by



2020/02/27


こういった場合に便利なのがオフィシャルが提供している解析コマンド shadow です。(相変わらずググらび...)

インストールは以下を実行します。

$ go get golang.org/x/tools/go/analysis/passes/shadow/cmd/shadow

ツイートされておられる以下のコードで実行してみます。

package main

import (
    "fmt"
)

var condition = true

func main() {

    var hoge *string
    if condition {
        hoge, err := do("word")
        if err != nil {
            return
        }
        fmt.Printf("checkpoint: %v\n", *hoge)
    } else {
        hoge = nil
    }

    fmt.Printf("RESUT: %v\n", hoge)

}

func do(v string) (*stringerror) {
    return &v, nil
}
.../main.go:13:3: declaration of "hoge" shadows declaration at line 11

便利。

改訂2版 みんなのGo言語 改訂2版 みんなのGo言語
松木 雅幸, mattn, 藤原 俊一郎, 中島 大一, 上田 拓也, 牧 大輔, 鈴木 健太
技術評論社 Kindle版 / ¥2,350 (2019年08月01日)
 
発送可能時間:

Posted at by



2020/02/21


Go 言語は struct のレシーバがポインタの場合は実体であってもポインタの場合であっても呼び出せるので、もし struct が参照カウントに従い動作する様な場合は実体でコピーされてしまっては困る場合があります。例えば以下の様なインタフェースを考えます。

package main

import (
    "fmt"
    "sync/atomic"
    "time"
)

type foo struct {
    n int64
    q chan struct{}
}

func (f *foo) Add() {
    if atomic.AddInt64(&f.n, 1) == 1 {
        f.q = make(chan struct{})
    }
}

func (f *foo) Done() {
    if atomic.AddInt64(&f.n, -1) == 0 {
        f.q <- struct{}{}
    }
}

func (f *foo) Watch() {
    <-f.q
}

func main() {
    var f foo

    f.Add()
    f.Add()
    f.Add()
    go func() {
        fmt.Println("いーち!")
        time.Sleep(time.Second)
        f.Done()
        fmt.Println("にー!")
        time.Sleep(time.Second)
        f.Done()
        fmt.Println("さーん!")
        time.Sleep(time.Second)
        f.Done()
    }()

    f.Watch()
    fmt.Println("ダーッ!")
}

このコードは main の中だけで動く場合には機嫌良く動きます。次にこの処理を分散してみたい考えてみます。関数 doSomething1 と doSomething2 に foo を引数で渡します。

func doSomething1(f foo) {
    time.Sleep(2 * time.Second)
    fmt.Println("さーん!")
    time.Sleep(time.Second)
    f.Done()
}

func doSomething2(f foo) {
    fmt.Println("いーち!")
    time.Sleep(time.Second)
    f.Done()
    fmt.Println("にー!")
    time.Sleep(time.Second)
    f.Done()
}

func main() {
    var f foo

    f.Add()
    f.Add()
    f.Add()
    go doSomething1(f)
    go doSomething2(f)

    f.Watch()
    fmt.Println("ダーッ!")
}

この処理は一見うまく行きそうに見えます。しかし実行するとデッドロックが起きます。

いーち!
にー!
さーん!
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.(*foo).Watch(...)
    C:/Users/mattn/go/src/github.com/mattn/misc/inoki_app/main.go:27
main.main()
    C:/Users/mattn/go/src/github.com/mattn/misc/inoki_app/main.go:55 +0xfd

「しっかり atomic.AddInt64 を使っているのにおかしい」と思うかもしれません。しかし実際は doSomething1 や doSomething2 の引数として foo の実体を渡した際にはコピーが発生してしまいます。参照カウンタである foo.n は両方の関数に 3 が渡り、foo.n が 0 になる事はありません。もちろんこれは引数をポインタにする事で回避できます。

func doSomething1(f *foo) {
    time.Sleep(2 * time.Second)
    fmt.Println("さーん!")
    time.Sleep(time.Second)
    f.Done()
}

func doSomething2(f *foo) {
    fmt.Println("いーち!")
    time.Sleep(time.Second)
    f.Done()
    fmt.Println("にー!")
    time.Sleep(time.Second)
    f.Done()
}

func main() {
    var f foo

    f.Add()
    f.Add()
    f.Add()
    go doSomething1(&f)
    go doSomething2(&f)

    f.Watch()
    fmt.Println("ダーッ!")
}

こういった struct をライブラリとして提供したい場合、使い手側に「ポインタで使って欲しい」と示す事ができないと、いくらでもバグが発生してしまいます。そこで使うテクニックが noCopy です。Go 言語を知っていてここまで読んだ方であれば、これが何かに似ていると気付いたはずです。そう sync.WaitGroup です。sync.WaitGroup も実体で引数に渡すとデッドロックが発生します。sync.WaitGroup の場合は以下のテクニックを使っています。

type WaitGroup struct {
    noCopy noCopy

    // 64-bit value: high 32 bits are counter, low 32 bits are waiter count.
    // 64-bit atomic operations require 64-bit alignment, but 32-bit
    // compilers do not ensure it. So we allocate 12 bytes and then use
    // the aligned 8 bytes in them as state, and the other 4 as storage
    // for the sema.
    state1 [3]uint32
}

type noCopy struct{}
func (*noCopy) Lock()   {}
func (*noCopy) Unlock() {}

go vet は Go 言語でのお作法の良くない書き方を検出してくれるツールですが、この Lock() と Unlock() を持ったインタフェースを実体でコピーしようとすると go vet の copylocks というチェック機能により警告がでる仕組みになっています。

# github.com/mattn/misc/inoki_app
.\main.go:5:21: doSomething passes lock by value: sync.WaitGroup contains sync.noCopy
.\main.go:11:14: call of doSomething copies lock value: sync.WaitGroup contains sync.noCopy

実際に組み込んでみましょう。

package inoki

import (
    "sync/atomic"
)

type noCopy struct{}

func (*noCopy) Lock()   {}
func (*noCopy) Unlock() {}

type Toukon struct {
    noCopy noCopy

    n int64
    q chan struct{}
}

func (f *Toukon) Add() {
    if atomic.AddInt64(&f.n, 1) == 1 {
        f.q = make(chan struct{})
    }
}

func (f *Toukon) Done() {
    if atomic.AddInt64(&f.n, -1) == 0 {
        f.q <- struct{}{}
    }
}

func (f *Toukon) Watch() {
    <-f.q
}

言語仕様上、禁止する事はできないのでコンパイルは出来てしまいますが、go vet を使う IDE 等ではちゃんと警告がでる様になっています。

ダー!

便利なテクニックなので使ってみてみるといいと思います。

改訂2版 みんなのGo言語 改訂2版 みんなのGo言語
松木 雅幸, mattn, 藤原 俊一郎, 中島 大一, 上田 拓也, 牧 大輔, 鈴木 健太
技術評論社 Kindle版 / ¥2,350 (2019年08月01日)
 
発送可能時間:

Posted at by