(I am replying inline to make the context of my comment clear, although it seems common practice to top-post in this forum - is there any guidance about this?)
Arnaud On Thursday, 24 December 2020 at 10:31:54 UTC kortschak wrote: > You can also use the internal map implementation and make us of the > runtime's map iterator. This is relatively straightforward at the cost > of vigilance for changes in the runtime. > > Here is an example (note that yo need a .S file as well to get the > go:linkname magic to work). > https://github.com/gonum/gonum/blob/master/graph/iterator/map.go > > That's interesting, thanks. Although I don't think it fits my use case because I need something stronger than an iterator: a function that given a table and a key returns the next key in the table (as this is a public API that Lua provides, see https://www.lua.org/manual/5.3/manual.html#pdf-next). From my point of view this is an unfortunate API! Nevertheless it is what it is... I haven't found even a hacky way to obtain that for a Go map. That is why I think I need to make my own hashtable implementation > (we back this with a reflect equivalent that it provided by > https://golang.org/pkg/reflect/#MapIter. > > Dan > > On Thu, 2020-12-24 at 02:18 -0800, Arnaud Delobelle wrote: > > Hi there! > > > > In my continued efforts to improve the performance of my Go Lua > > implementation [1], I have reached a bottleneck which causes me a > > quandary. > > > > Lua has a data structure which is called 'table', which is > > essentially a hashmap. So far I have implemented it as a Go map, > > which works OK. However there is significant overhead coming from > > the fact that Lua has a `next` function that allows getting the > > "next" key-value pair in a table after a given one: `next(t, key)`. > > As far as I can tell Go doesn't allow this so if I want to use a Go > > map, I also have to keep track of the next key for each key, which > > doubles the memory requirement, necessitates more accounting in the > > code and makes iteration via `next` slower. > > > > So I am looking at not using the builtin Go map and making my own > > hashtable implementation. However, because the keys are still made > > of Go values, I would like to benefit from the quick hashing that > > maps use. After some poking around in the implementation of map (and > > discovering the //go:linkname compiler directive), I think that I can > > do this: > > > > > > // This is the Lua Value type. The scalar part contains the payload > > of int64, float64 or bool for quicker access and minimising > > allocations. > > type Value struct { > > scalar uint64 > > iface interface{} > > } > > > > > > //go:linkname goRuntimeInt64Hash runtime.int64Hash > > //go:noescape > > func goRuntimeInt64Hash(i uint64, seed uintptr) uintptr > > > > //go:linkname goRuntimeEfaceHash runtime.efaceHash > > //go:noescape > > func goRuntimeEfaceHash(i interface{}, seed uintptr) uintptr > > > > // Hash returns a hash for the value. > > func (v Value) Hash() uintptr { > > if v.scalar != 0 { > > return goRuntimeInt64Hash(v.scalar, 0) > > } > > return goRuntimeEfaceHash(v.iface, 0) > > } > > > > Does that sound like a sensible approach? I.e. is it safe enough to > > use the go:linkname directive, and do those seem like the right > > functions to call to obtain a good hash? > > > > TIA > > > > -- > > Arnaud > > -- > > You received this message because you are subscribed to the Google > > Groups "golang-nuts" group. > > To unsubscribe from this group and stop receiving emails from it, > > send an email to golang-nuts...@googlegroups.com. > > To view this discussion on the web visit > > > https://groups.google.com/d/msgid/golang-nuts/79e3f124-037c-4c10-a7b6-42f496bd26b6n%40googlegroups.com > > > . > > > > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/ee5e1f22-32a4-4adb-b1f0-52bf7148fa9bn%40googlegroups.com.
