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