type parameter と linked list

skiplistmapの発表も終わったし、go 1.18 から type parameter のサポートもはじまったということで　自分のpackage も type parameter に対応していこうかなといじりはじめたら、結構罠があったりしたのでそのメモ代わり

そもそも type parameter の仕様ってはっきり記載されてなくて

たぶん type parameter Proposal しかいまだに見るしかないのだろうか? なんかきちんと記載したものがあるなら誰か教えてほしい。

埋め込みの中のfield の unsafe.Offsetof が取れない

まずはいきなりバグにはまったという話

lock free なlinked list である　elist_head とかでは

type SampleEntry struct {
	Name string
	Age  int
	ListHead
}

というふうに埋め込んでいる。

定義したリストには　以下のようにmethod をはやす前提だ

type List interface {
	Offset() uintptr
	PtrListHead() *ListHead
	FromListHead(*ListHead) List
}

ここの例でいうと SampleEntry から ListHead へのoffset を unsafe.Offsetof() をつかってとらないといけない

  item := SampleEntry{}
  unsafe.OffsetOf(item.ListHead)

ここは問題ないのだが

skiplistmap などでは

type MapHead struct {
    ListHead
}

type Entry struct {
    MapHead
}

とかになっている。このときtype parameter をつかって

type Entry[T any] struct {
    Val T
    MapHead
}

とかってした場合

entry := new(Entry[int])
unsafe.OffsetOf(&entry.ListHead)

を実行すると0 がかえってきてしまう。

どうやら MapHead からのListHead までのoffset をとるらしい。

ということで bug report した。

あっというまに 1.18backport に入り。1.18.3 に入るかとおもったがどうやら間に合わなかったらしくたぶん 1.18.4に入りそう

pointer でmethod をはやしたやつがなやましい。


type Base struct {
    I int
}

type(b *Base) Int() int {
    return b.I
}

type Sample[T any] struct {
    Value T
}

こんな感じで定義したときに

func Fuga[T any](s Sample[T]) {
    s.Value.I // 呼べない
    s.Value.Int() // 呼べない

}

こういう感じで Base の Int() とかは呼べない。 T が any だから当然。

てことで

type CallerInt interface{
    Int()
}

type Sample[T CallerInt] struct {
    Value T
}

これでも呼べない。*Base は　CallerInt　だけど Base は CallerInt じゃないので

Sample[Hoge] はcontaraint ではじかれて Sample[*Hoge] だと Sample[T] のメンバーがポインタになってしまう。

こんなことを悩んでいたら

僕らの心の親友であるstackoverflow 先生に How can I instantiate a non-nil pointer of type argument with generic Go?　こんな記事があった。

type CallerInt[T] struct {
    Int()
    *T
}

func Fuga[T any, PT CallerInt[T]](s Sample[T]) {

    PT(&s.Value).Int()
}

なんていうかどっかでみたtemplate 感があふれてきて、読んでもわからないとかなりそうw

説明すると CallerInt[T]　は *T を受けるので　PT() してあげると Tのポインタでかつ Int() をもってる状態になるからそれなら呼べるということですね。ポインタでも実体でも method のinterface がというconstraint をつけるにはいまのところこれしかなさそうでこれはなんとかしてほしい感はあるけど難しいかなぁ。

type parameter を使う理由として、interface{} の変換コストがバカにならないので減らしたいということもある。

しかし　このやり方すると PT() のたびに変換はいるし。　制約をいれる時点で interface{} 化してしまうので type any = interface{} だしね

そうすると単純にinterface{} つかうより constraint で interface{} 変換 PT() と呼ぶところでもう一度実体化と2回走るのでこのあたりはなんとかしてほしい。

method が定義されてるものは method 呼び出しとかはもうちょっと最適化できるだろうと思うがそこはどうなのか

ということで可能な限り constraint を使わないでうまくやるのがパフォーマンスだしつつ恩恵に預かるということで

頭をひねって linked list のtype parameter 版は以下のような感じではじめようかとおもった

Proposal にある

// ListHead is the head of a linked list.
type ListHead[T any] struct {
	head *ListElement[T]
}

// ListElement is an element in a linked list with a head.
// Each element points back to the head.
type ListElement[T any] struct {
	next *ListElement[T]
	val  T
	// Using ListHead[T] here is OK.
	// ListHead[T] refers to ListElement[T] refers to ListHead[T].
	// Using ListHead[int] would not be OK, as ListHead[T]
	// would have an indirect reference to ListHead[int].
	head *ListHead[T]
}

これだと ListElement[T] に next と head があって両方あって空間効率的にすこし無駄なので

type ListHead struct {
	next, prev *ListHead
}

type Element = any

type List[T any] struct {
	ListHead
	Element T
}

func New[T any]() *List[T] {
	start := &List[T]{}
	end := &List[T]{}
	start.prev = &start.ListHead
	start.next = &end.ListHead

	end.prev = &start.ListHead
	end.next = &end.ListHead
	return start
}


func ElementOf[T any, L List[T]](h *listHead) *L {

    l := new(List[T])
    offset := unsafe.OffsetOf(l.Element)

	return (*List[T])(unsafe.Add(unsafe.Pointer(h), offset))
}

こういう感じにすることで List[T] 自体に Prev()/Next() を生やすだけでいままでように　先にmethod を定義するというのは避けられそうな気がしている。