sliceとmapのdelete(+make)はどちらが速いのか

Golangでmapとsliceどちらが速いのかに引き続いて、要素を削除する場合のベンチマークを取ってみる。

やり方

slice

メモリリークしないようにSliceTricksにある以下の方法で要素を削除する。

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

map

組み込みのdeleteで削除する

delete(map[typeA]typeB, typeA)

条件

  • sliceは[]int型とする
  • mapはmap[int]int型とする
  • sliceから削除したい要素のindexはn/2を使う
  • mapから削除したい要素をn/2とする

環境

macOS High Sierra version 10.13.4（17E202）
MacBook Pro (Retina, 13-inch, Early 2015)
2.7 GHz Intel Core i5
16 GB 1867 MHz DDR3
Intel Iris Graphics 6100 1536 MB

❯ go version
go version go1.10.1 darwin/amd64

実装

map, sliceどちらも削除前の状態を毎回使いまわす必要があるが、どちらも参照型で実装されるので、毎回makeで作り直すことにする。 make自体がmapとsliceで差がある(Appendix参照)ので、それぞれmakeするだけベンチマークも測定し、差分(make+delete-make)を結果とする。 makeに掛かる時間は要素数に単調増加するので、それぞれ差分の計算は、同じ要素数でmakeした結果から求める。

ベンチマークの実装は以下の通り。

slice

func benchmarkOfDeleteFromSlice(n int, b *testing.B) {
    idx := n / 2

    for i := 0; i < b.N; i++ {
        s := make([]int, n)
        copy(s[idx:], s[idx+1:])
        s[len(s)-1] = 0
        s = s[:len(s)-1]
    }
}

func benchmarkOfMakeSlice(n int, b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = make([]int, n)
    }
}

map

func benchmarkOfDeleteFromMap(n int, b *testing.B) {
    idx := n / 2

    for i := 0; i < b.N; i++ {
        m := make(map[int]int, n)
        delete(m, idx)
    }
}
func benchmarkOfMakeMap(n int, b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = make(map[int]int, n)
    }
}

結果

f:id:cipepser:20180508221142p:plain

要素数が少ないとmakeに掛かる時間が測定によってばらつきがあり、差分がマイナスになったが、要素数が1000を超えたあたりからmapよりsliceが有利であることがわかる。またsliceは削除に要する時間が要素数に依らず、ある程度一定の値となっている。

Appendix

ベンチマーク結果の生データは以下の通り。

BenchmarkOfDeleteFromSlice10-4        30000000           40.0 ns/op
BenchmarkOfDeleteFromSlice30-4         20000000           66.5 ns/op
BenchmarkOfDeleteFromSlice70-4         10000000          134 ns/op
BenchmarkOfDeleteFromSlice100-4        10000000          229 ns/op
BenchmarkOfDeleteFromSlice300-4         3000000          554 ns/op
BenchmarkOfDeleteFromSlice700-4         1000000         1034 ns/op
BenchmarkOfDeleteFromSlice1000-4        1000000         1478 ns/op
BenchmarkOfDeleteFromSlice3000-4         300000         3903 ns/op

BenchmarkOfMakeSlice10-4               50000000           33.8 ns/op
BenchmarkOfMakeSlice30-4               20000000           59.6 ns/op
BenchmarkOfMakeSlice70-4               10000000          119 ns/op
BenchmarkOfMakeSlice100-4              10000000          173 ns/op
BenchmarkOfMakeSlice300-4               3000000          494 ns/op
BenchmarkOfMakeSlice700-4               2000000          938 ns/op
BenchmarkOfMakeSlice1000-4              1000000         1465 ns/op
BenchmarkOfMakeSlice3000-4               300000         3785 ns/op

BenchmarkOfDeleteFromMap10-4           20000000          102 ns/op
BenchmarkOfDeleteFromMap30-4            5000000          255 ns/op
BenchmarkOfDeleteFromMap70-4            3000000          604 ns/op
BenchmarkOfDeleteFromMap100-4           3000000          583 ns/op
BenchmarkOfDeleteFromMap300-4           1000000         1546 ns/op
BenchmarkOfDeleteFromMap700-4            500000         2992 ns/op
BenchmarkOfDeleteFromMap1000-4           200000         6079 ns/op
BenchmarkOfDeleteFromMap3000-4           100000        12120 ns/op

BenchmarkOfMakeMap10-4                 20000000           97.8 ns/op
BenchmarkOfMakeMap30-4                  5000000          251 ns/op
BenchmarkOfMakeMap70-4                  3000000          590 ns/op
BenchmarkOfMakeMap100-4                 2000000          580 ns/op
BenchmarkOfMakeMap300-4                 1000000         1563 ns/op
BenchmarkOfMakeMap700-4                  500000         3100 ns/op
BenchmarkOfMakeMap1000-4                 200000         5980 ns/op
BenchmarkOfMakeMap3000-4                 100000        11305 ns/op

すべてまとめてグラフにすると以下の通り。

f:id:cipepser:20180508221231p:plain

makeのみの所要時間は以下の通り。

f:id:cipepser:20180508221234p:plain

一貫して、sliceのほうがmakeに要する時間は少なかった。 sliceとmapの内部実装も以下の通りで、sliceのほうが初期化に掛かる時間が少ないと思われる。

sliceの内部実装

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

mapの内部実装

// A hash iteration structure.
// If you modify hiter, also change cmd/internal/gc/reflect.go to indicate
// the layout of this structure.
type hiter struct {
    key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/internal/gc/range.go).
    value       unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go).
    t           *maptype
    h           *hmap
    buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
    bptr        *bmap          // current bucket
    overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
    oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
    startBucket uintptr        // bucket iteration started at
    offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
    wrapped     bool           // already wrapped around from end of bucket array to beginning
    B           uint8
    i           uint8
    bucket      uintptr
    checkBucket uintptr
}

References