2020/04/04

Recent entries from same category

  1. Go 言語プログラミングエッセンスという本を書きました。
  2. errors.Join が入った。
  3. unsafe.StringData、unsafe.String、unsafe.SliceData が入った。
  4. Re: Go言語で画像ファイルか確認してみる
  5. net/url に JoinPath が入った。

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 を使うともう少し速い。

Posted at by | Edit