Re: [go-nuts] Go Map assignment order determine by position of terminator?

[Rémy Oudompheng]

On 2012/8/7 Ruben A. <rjan...@gmail.com> wrote:
> So you can see the assignment order in the map was affected by just scooting
> in that closing '}' 4 spaces. I am doing this on the "Tour of Go" but was
> wondering if anyone had any idea why this would be??

The order of map iteration is undefined and even non-deterministic and
non-reproducible. This is intentional and you should expect to get
different results even when not changing your code.

Rémy.

[Ruben A.]

Thanks for the explanation.  I figured it didn't matter in any way (being a map and all), but I still found the difference interesting.  

[kortschak]

This is something I've found interesting. It's one place where a significant amount of magic is displayed; (nearly) everywhere else, one run can be guaranteed to be identical to another down to variable address allocation, but there is no way to enforce identity on map key retrieval order. This hasn't caused any problems, but it does seem kind of odd in the context of most other design choices (that's not to say the motivation is unclear).

Dan

[Jesse McNelis]

On Wed, Aug 8, 2012 at 11:23 AM, kortschak
<dan.ko...@adelaide.edu.au> wrote:
> This is something I've found interesting. It's one place where a significant
> amount of magic is displayed; (nearly) everywhere else, one run can be
> guaranteed to be identical to another down to variable address allocation,
> but there is no way to enforce identity on map key retrieval order. This
> hasn't caused any problems, but it does seem kind of odd in the context of
> most other design choices (that's not to say the motivation is unclear).

The spec says that maps are unordered which gives the implementation
of maps far more flexibility in terms of performance.
Map behaviour in the gc implementation of Go was fairly predictable
because it didn't exploit the fact that the spec defines it as
unordered.
This caused problems because developers started writing code that
relied on maps being ordered (because in this implementation they
were).

Changes where made to add additional randomness to the map
implementation just to prevent programmers from relying on
implementation specific behaviour.


--
=====================
http://jessta.id.au

[kortschak]

Yeah, I understand that, the issue is the balance of magic vs. gently pushing people away from dependency on unspecified behaviour.

The current behaviour can make debugging code that uses maps difficult because of the impossibility of guaranteeing a failing case. This dependency on behaviour is not the same as dependency in production.

Dan

On Wednesday, August 8, 2012 11:23:43 AM UTC+9:30, Jesse McNelis wrote:

[Patrick Mylund Nielsen]

http://code.google.com/p/go/issues/detail?id=2630 

http://code.google.com/p/go/source/detail?r=cd86b08237be 

[kortschak]

Thanks. That's the kind of answer I'm looking for.

Dan

On Wednesday, August 8, 2012 4:10:15 PM UTC+9:30, Patrick Mylund Nielsen wrote:

http://code.google.com/p/go/issues/detail?id=2630 

http://code.google.com/p/go/source/detail?r=cd86b08237be

[Rémy Oudompheng]

On 2012/8/8 kortschak <dan.ko...@adelaide.edu.au> wrote:
> This is something I've found interesting. It's one place where a significant
> amount of magic is displayed; (nearly) everywhere else, one run can be
> guaranteed to be identical to another down to variable address allocation,
> but there is no way to enforce identity on map key retrieval order. This
> hasn't caused any problems, but it does seem kind of odd in the context of
> most other design choices (that's not to say the motivation is unclear).
>
> Dan

You should not rely on it being "fairly random" (wrt the choice of
starting point of iteration) either:
http://play.golang.org/p/Qumc1xbh3A

Rémy.

[Patrick Mylund Nielsen]

And what a nice thing: When you see magic in Go, it's actually there for a reason.

[kortschak]

Yeah, I understood there was a reason, it was a matter of finding out what that was - unfortunately people often answer these question with "because the spec says so" - design principle questions really require design principle answers, rather than gospel, so thanks for that.

The reason that "it's there to stop people doing bad stuff" seemed particularly weak. Avoiding malicious hash collisions makes a lot more sense. Further the pointer to the code makes it possible in development to revert that behaviour in the case that there is an intermittent bug that's difficult to work through.

Dan

[Patrick Mylund Nielsen]

Dan's note was actually the main argument why Python devs were reluctant to adopt hash IV randomization--it broke their unit tests! PHP ultimately chose not to do it at all, and instead limited the size of the http.Request header, and Oracle and others didn't think it was a language problem at all. Perl saw the problem and applied a fix similar to Go's which was included in Perl 5.8.1 in 2003. I might be wrong, but I think they were the only ones to actually care then when this paper was presented:  http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/

For others, this, which became very popular about a year ago, was a good motivator: http://www.youtube.com/watch?v=R2Cq3CLI6H8

[Ruben A.]

Great Reply!  Thanks for the info.  This is exactly what I needed to hear (not knowing 'why' always bothers me).

[Russ Cox]

Map iteration is non-deterministic both from map to map (issue 2630)
but also from loop to loop on the same map (issue 1544).

Russ

[Ruben A.]

Russ, I noticed 1544 was finally resolved as 'fixed'.  Is it really just 'closed?.  Since the issue really wasn't (and seemingly can't be, since it is inherent to it's nature) fixed?

Slightly off-topic but that was an interesting discussion.

[Russ Cox]

> Russ, I noticed 1544 was finally resolved as 'fixed'. Is it really just
> 'closed?. Since the issue really wasn't (and seemingly can't be, since it
> is inherent to it's nature) fixed?

No, it's really fixed. The iteration starts in a random location each
time, so the map does not end up unbalanced.

Russ