genny でkernel のlist_head スタイルのcontainer/list をつくった
Published on
go には [container/list] package というlinked-list を扱う パッケージがあるんだけど。どうにも具合がよくない。ということで自分でつくってみた
なにが具合が良くないかというと
- list を管理するstruct をelement が別であり、無駄。
- 数が多くなると heavy にheap を使いgc 案件である。
- 要素がinterface{} なので型変換のコストがでかいでござる。
LRU みたいなのに使うとパフォーマンス的な問題がおきたりしていた。 詳細とかは improve container/list に詳しかったりします。
根本的に interface{} は使わざるをえない。
という感じ。generics はまだ当然ないので、以前に template をつかってcode 生成することで linux kernel のlist_head のようなやり口のlinked-list をつくった。
ですが作成時にvscode の補助がきかないとかだいぶつらかったです。 最近は genny というすばらしいものがあって、偽装的な type をつくって それでコードをかくのでvscode で補助もきいてすばらしいということでつくりました。
いちよインターフェースはほぼ [container/list] と同じものをもつので 使うのにもこまりません。またconcurrent access にも対応してるので 複数のgoroutine からアクセスしても壊れません。
使い方
最初に linked-list にいれる 要素を定義
package example
import (
"github.com/kazu/loncha/list_head"
)
type SampleParent struct {
Name string
}
type Sample struct {
ID int
Name string
Parent *SampleParent
list_head.ListHead
}
linked-list は listHead をstruct に内包することで実現している。
生成してみる。
$ wget -q -O - "https://github.com/kazu/loncha/master/container_list/container_list.go" | genny gen "ListEntry=Sample" > sample_list.go
これでできた。
...
func (d *Sample) Init() {
d.ListHead.Init()
}
// Next ... returns the next list element or nil.
func (d *Sample) Next() *Sample {
if d.ListHead.Next() == nil {
panic(errors.New("d.next is nil"))
}
return (*Sample)(unsafe.Pointer(uintptr(unsafe.Pointer(d.ListHead.Next())) - unsafe.Offsetof(d.ListHead)))
}
// Prev ... returns the previous list element or nil.
func (d *Sample) Prev() *Sample {
if d.ListHead.Next() == nil {
panic(errors.New("d.prev is nil"))
}
return (*Sample)(unsafe.Pointer(uintptr(unsafe.Pointer(d.ListHead.Prev())) - unsafe.Offsetof(d.ListHead)))
}
// NewSampleList ... New returns an initialized list.
func NewSampleList(h *Sample) *Sample {
h.Init()
return h
}
...
できてる。
ついでにbenchmark もとってみる。
const (
CREATE_NODE_MAX int = 10000
)
func MakeSample() (samples []*Sample, oldSamples []*OldSample) {
samples = make([]*Sample, CREATE_NODE_MAX)
oldSamples = make([]*OldSample, CREATE_NODE_MAX)
for i ,_ := range samples {
id := int(math.Abs(float64(rand.Intn(CREATE_NODE_MAX))))
samples[i] = &Sample{
ID: id,
Name: fmt.Sprintf("aaa%d", i),
}
oldSamples[i] = &OldSample{ID: samples[i].ID, Name: samples[i].Name}
}
return
}
func BenchmarkInsert(b *testing.B) {
orig, origOld := MakeSample()
b.ResetTimer()
b.Run("original container/list", func(b *testing.B) {
for j := 1; j < b.N; j++ {
b.StopTimer()
objs := make([]*OldSample, len(origOld))
copy(objs, origOld)
l := list.New()
for i := 0; i < len(objs); i++ {
b.StartTimer()
l.PushBack(objs[i])
b.StopTimer()
}
}
})
b.ResetTimer()
b.Run("loncha.container/list", func(b *testing.B) {
objs := make([]*Sample, len(orig))
copy(objs, orig)
objs[0].Init()
b.StopTimer()
for j := 1; j < b.N; j++ {
b.StopTimer()
objs := make([]*Sample, len(orig))
copy(objs, orig)
objs[0].Init()
for i := 1; i < len(objs); i++ {
b.StartTimer()
objs[i].Init()
objs[i-1].PushBack(objs[i])
b.StopTimer()
}
}
})
}
とりあえず 10000件のリストをPushBack するのを10回計測してみた。 いっぱい回すのは時間かかるのでとりあえず。
% go test -bench . --benchmem --benchtime 10x --run=BenchmarkInsert
BenchmarkInsert/original_container/list-16 10 4145263 ns/op 432030 B/op 9000 allocs/op
BenchmarkInsert/loncha.container/list-16 10 1148802 ns/op 8192 B/op 0 allocs/op
PASS
ok github.com/kazu/loncha/example/genny 5.552s
我が軍は圧倒的じゃないか!
- 7/7 追記 bencnmark コードが間違えてて速すぎたので酒精しましたw さすがに速すぎるとおもったw