golangのmap[int]intのメモリ効率

最近使うコンパイル言語と言えばgolang。これはこれでけっこうハッピーですね。C++なんて最初からいらんかったんや! channelとgoroutineで並列処理も楽々。ただ適当に書いてるとgoroutineのリークがけっこう起きるみたいですね。

[]intとmap[int]intのどちらを使うか。sparseな感じだとどのくらい違うのかな? []intはだいたい意図したとおりの配列になるのだが、map[int]intはたぶんhash + listかred-black treeになっているだろうから、オーバーヘッドは気になる。

試してみた。

package main

import (
    "flag"
    "fmt"
    "syscall"
)

func main() {
    n := flag.Int("num", 10000, "number of iteratio")
    flag.Parse()
    fmt.Printf("num=%d\n", *n)
    data := make(map[int]int)
    for i := 0; i < *n; i++ {
        data[i] = i + 1
    }
    var r syscall.Rusage
    syscall.Getrusage(syscall.RUSAGE_SELF, &r)
    fmt.Printf("%+v\n", r)
    return
}

./test -num 67108864

num=671088
{Utime:{Sec:24 Usec:232528 Pad_cgo_0:[129 255 255 255]} Stime:{Sec:1 Usec:172404 Pad_cgo_0:[0 0 0 0]} Maxrss:5017321472 Ixrss:0 Idrss:0 Isrss:0 Minflt:1225546 Majflt:0 Nswap:0 Inblock:0 Oublock:0 Msgsnd:0 Msgrcv:0 Nsignals:0 Nvcsw:2759 Nivcsw:1253}

MacOSのgetrusageのMaxRSSはバイト単位。したがって、5017321472/67108864≒74.8。4バイトがキー、4バイトが値だから74.8-4-4で66バイト程度がmapのオーバーヘッドと考えられる。こんなもんか。もし密度が1/20以下くらいのsparseな配列であれば、mapを使うのもいいだろう。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です