Re: [go-nuts] Obtaining an efficient hash for Go values

[Arnaud Delobelle]

Lua `next` is a function that takes two arguments: a table and a key and 
returns the another key (or nil).  Unlike an iterator, it holds no 
context.  It is guaranteed that you will iterate over all keys if you 
repeatedly call next as follows

k = next(t)
while k ~= nil do
k = next(t, k)
end

If, however, you were to insert new items into t in the body of this loop, 
this guaranteed would no longer hold.  This is what is meant by "undefined 
behaviour", as far as I understand.

Arnaud

On Thursday, 24 December 2020 at 15:55:27 UTC Jan Mercl wrote:

> On Thu, Dec 24, 2020 at 4:08 PM Arnaud Delobelle  wrote:
>
> > The order is undefined but stable (provided you don't insert new 
> values), and accessible via the `next` function. Here is an example:
>
> Quoting from the provided link:
>
> 
> next (table [, index])
>
> Allows a program to traverse all fields of a table. Its first argument
> is a table and its second argument is an index in this table. next
> returns the next index of the table and its associated value. When
> called with nil as its second argument, next returns an initial index
> and its associated value. When called with the last index, or with nil
> in an empty table, next returns nil. If the second argument is absent,
> then it is interpreted as nil. In particular, you can use next(t) to
> check whether a table is empty.
>
> The order in which the indices are enumerated is not specified, even
> for numeric indices. (To traverse a table in numerical order, use a
> numerical for.)
>
> The behavior of next is undefined if, during the traversal, you assign
> any value to a non-existent field in the table. You may however modify
> existing fields. In particular, you may clear existing fields.
> 
>
> The word 'stable' does not seem to be present in this part of the
> specs at all, so only "The order in which the indices are enumerated
> is not specified, even for numeric indices." remains to be considered.
> That said, I see no problem with implementing it by iterating a Go
> map.
>
> Or is the Lua specification perhaps incomplete? Maybe people
> incorrectly rely on the behavior of a particular implementation.
> That's why the Go map iteration is intentionally randomized, BTW.
>

-- 
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/4aa8f174-2e3b-4124-9e55-44b415cce398n%40googlegroups.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

[Jan Mercl]

On Thu, Dec 24, 2020 at 4:08 PM Arnaud Delobelle  wrote:

> The order is undefined but stable (provided you don't insert new values), and 
> accessible via the `next` function.  Here is an example:

Quoting from the provided link:


next (table [, index])

Allows a program to traverse all fields of a table. Its first argument
is a table and its second argument is an index in this table. next
returns the next index of the table and its associated value. When
called with nil as its second argument, next returns an initial index
and its associated value. When called with the last index, or with nil
in an empty table, next returns nil. If the second argument is absent,
then it is interpreted as nil. In particular, you can use next(t) to
check whether a table is empty.

The order in which the indices are enumerated is not specified, even
for numeric indices. (To traverse a table in numerical order, use a
numerical for.)

The behavior of next is undefined if, during the traversal, you assign
any value to a non-existent field in the table. You may however modify
existing fields. In particular, you may clear existing fields.


The word 'stable' does not seem to be present in this part of the
specs at all, so only "The order in which the indices are enumerated
is not specified, even for numeric indices." remains to be considered.
That said, I see no problem with implementing it by iterating a Go
map.

Or is the Lua specification perhaps incomplete? Maybe people
incorrectly rely on the behavior of a particular implementation.
That's why the Go map iteration is intentionally randomized, BTW.

-- 
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/CAA40n-ViaFtYCZ1X%3D6FrXd9zwDR%2Bu_ws9v%2BsaWLWNWk5Ck56vQ%40mail.gmail.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

[Wojciech S. Czarnecki]

Dnia 2020-12-24, o godz. 06:19:53
Arnaud Delobelle  napisał(a):

> I did have a look at hash/maphash, but I didn't think it was the right 
> shaped API for what I am doing.

Do not be afraid to just "steal" runtime implementation and tinker with it to
get at desired properties.  

https://github.com/golang/go/blob/master/src/runtime/map.go
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics

Hope this helps,

-- 
Wojciech S. Czarnecki
 << ^oo^ >> OHIR-RIPE

-- 
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/20201224165055.2cc4d487%40xmint.

Re: [go-nuts] Obtaining an efficient hash for Go values

['Axel Wagner' via golang-nuts]

I think theoretically, you might be able to optimize it away (at least in
the overwhelming majority of use-cases) by storing a couple of
`*reflect.MapIter` for the last used tables in the context of the VM and
then check, when `next` is called, if the key passed is the one it's
currently at. But I agree, that it's pretty hackish and also doesn't give
you the "stable, unless the elements are changed" property.

So, I tend to agree that you won't be able to do without your own
hashtable. Which is a shame, as the builtin map is pretty good.

On Thu, Dec 24, 2020 at 4:08 PM Arnaud Delobelle  wrote:

>
>
> On Thursday, 24 December 2020 at 14:31:22 UTC Jan Mercl wrote:
>
>> On Thu, Dec 24, 2020 at 3:12 PM Arnaud Delobelle 
>> wrote:
>> > 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
>>
>> The linked pdf seems to indicate that Lua's 'next' can be implemented
>> using Go range over a map with no problem because the iteration order
>> is undefined in Lua as well.
>>
>> What am I missing?
>>
>
> The order is undefined but stable (provided you don't insert new values),
> and accessible via the `next` function.  Here is an example:
>
> $ lua
> Lua 5.3.5  Copyright (C) 1994-2018 Lua.org, PUC-Rio
> > t = { x = 1, y = 2, z = 3 }
> > next(t, 'y')
> z   3
> > next(t, 'z')
> x   1
> > next(t, 'y')
> z   3
> > next(t, 'z')
> x   1
>
> I don't understand how to do that with a map iterator unless get a new
> iterator each time and consume it till I get the key I want to find the
> next key for (which would be very inefficient), or there is a way to
> initialise the iterator at a given key - but I haven't found how to do the
> latter.
>
> 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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/31930063-9c33-4e0f-8372-ee5ae991b3e1n%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/CAEkBMfEoMYKTTrfxvbPUpypgCXAibHuWZqQeruPzw3Kr6MsiMw%40mail.gmail.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

[Arnaud Delobelle]

On Thursday, 24 December 2020 at 14:31:22 UTC Jan Mercl wrote:

> On Thu, Dec 24, 2020 at 3:12 PM Arnaud Delobelle  
> wrote: 
> > 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 
>
> The linked pdf seems to indicate that Lua's 'next' can be implemented 
> using Go range over a map with no problem because the iteration order 
> is undefined in Lua as well. 
>
> What am I missing? 
>

The order is undefined but stable (provided you don't insert new values), 
and accessible via the `next` function.  Here is an example:

$ lua
Lua 5.3.5  Copyright (C) 1994-2018 Lua.org, PUC-Rio
> t = { x = 1, y = 2, z = 3 }
> next(t, 'y')
z   3
> next(t, 'z')
x   1
> next(t, 'y')
z   3
> next(t, 'z')
x   1

I don't understand how to do that with a map iterator unless get a new 
iterator each time and consume it till I get the key I want to find the 
next key for (which would be very inefficient), or there is a way to 
initialise the iterator at a given key - but I haven't found how to do the 
latter.

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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/golang-nuts/31930063-9c33-4e0f-8372-ee5ae991b3e1n%40googlegroups.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

[Jan Mercl]

On Thu, Dec 24, 2020 at 3:12 PM Arnaud Delobelle  wrote:
> 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

The linked pdf seems to indicate that Lua's 'next' can be implemented
using Go range over a map with no problem because the iteration order
is undefined in Lua as well.

What am I missing?

-- 
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/CAA40n-UVtQH2zgaMG0F-MUvkmSO83d8yX9bpZQgJrpV%2BfnOGew%40mail.gmail.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

[Arnaud Delobelle]

I did have a look at hash/maphash, but I didn't think it was the right 
shaped API for what I am doing.  In short, I would have to contrive to 
provide words to the package as byte slices, which then would turn them 
back into words under the hood.  That feels like a superfluous round trip, 
given that the table is at the heart of everything in Lua as it is the only 
data structure available (so it is used to implement objects, modules, 
namespaces...).  I haven't discarded it yet but I wanted to explore other 
possibilities before doing some benchmarking.

Arnaud

On Thursday, 24 December 2020 at 10:45:30 UTC axel.wa...@googlemail.com 
wrote:

> On Thu, Dec 24, 2020 at 11:19 AM Arnaud Delobelle  
> wrote:
>
>> 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?
>>
>
> It is probably better to use hash/maphash, if you can.
> https://golang.org/pkg/hash/maphash/
> It's the intended use-case for that package and not subject to changes in 
> the runtime. However, the downside is that it doesn't allow all the same 
> values to be used as keys as Go maps do (you have to do the mapping from 
> values to []byte manually), so it might not be suitable.
>  
> Personally, I feel that go:linkname and similar trickery is too much black 
> magic to actually use. But TBF, I might be too biased on cleanliness over 
> performance and other concerns.
>
>
>> 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/53df26d1-cacc-48ed-9355-38dd46cddef4n%40googlegroups.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

[Arnaud Delobelle]

(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.

Re: [go-nuts] Obtaining an efficient hash for Go values

['Axel Wagner' via golang-nuts]

On Thu, Dec 24, 2020 at 11:19 AM Arnaud Delobelle  wrote:

> 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?
>

It is probably better to use hash/maphash, if you can.
https://golang.org/pkg/hash/maphash/
It's the intended use-case for that package and not subject to changes in
the runtime. However, the downside is that it doesn't allow all the same
values to be used as keys as Go maps do (you have to do the mapping from
values to []byte manually), so it might not be suitable.

Personally, I feel that go:linkname and similar trickery is too much black
magic to actually use. But TBF, I might be too biased on cleanliness over
performance and other concerns.


> 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+unsubscr...@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/CAEkBMfHi6R8wkx%2B%3DkOkmkqOCHcY8UuNfjHCYhfDchZNzBRG2%3Dw%40mail.gmail.com.

Re: [go-nuts] Obtaining an efficient hash for Go values

['Dan Kortschak' via golang-nuts]

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

(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+unsubscr...@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/d2d742dcbb9ddf7d495255c9efdef2ec01e35096.camel%40kortschak.io.