use same for/range code on a hash map but it has different result

[Kilos]

when I run the same code like this https://play.golang.org/p/fSPpo4_-k57,most of the time it print A,B,C and D,but sometimes it just print A,B and C,why ???

[seank...@gmail.com]

spec: https://golang.org/ref/spec#RangeClause

point 3: ... If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. ...

[jake...@gmail.com]

I'm not sure what strange way you decided to show your code, but in my Firefox browser all I see is two empty boxes. Please use fixed width plain text for all code in this group. Thanks.

[Kilos]

Thanks for reply, but I want to know the underlying reason about it, I think the reason is in how the runtime functions works.

And I'm sorry about the empty picture, when I write this, I just copy the screenshot in this, the code is https://play.golang.org/p/fSPpo4_-k57    

The empty picture is the code and it's different results.

package main

import (

"fmt"

)

func main() {

var m = map[string]int{

"A": 21,

"B": 22,

"C": 23,

}

counter := 0

for k, v := range m {

if counter == 0 {

m["D"] = 20

}

counter++

fmt.Println(k, v)

}

fmt.Println(counter)

}

[Dan Kortschak]

On Tue, 2020-11-10 at 19:08 -0800, 'Kilos' via golang-nuts wrote:
> Thanks for reply, but I want to know the underlying reason about it,
> I think the reason is in how the runtime functions works.

The direct cause is that the hash function used for the map
implementation is seeded from the system clock.

The reason for doing this was largely to avoid time complexity attacks
against servers that use maps for passing arguments in URIs.

[Kurtis Rader]

On Tue, Nov 10, 2020 at 7:09 PM 'Kilos' via golang-nuts <golan...@googlegroups.com> wrote:

Thanks for reply, but I want to know the underlying reason about it, I think the reason is in how the runtime functions works.

And I'm sorry about the empty picture, when I write this, I just copy the screenshot in this, the code is https://play.golang.org/p/fSPpo4_-k57   

Think about what it means to mutate a map while iterating over it. Do you want the `range` operator to enumerate all the key:value pairs before returning the first result? That's incredibly expensive. Also, what happens if instead of inserting a new key you delete a key that is about to be enumerated? Consider what happens whether or not the `range` operator enumerates all keys before returning the first result.

Dan's reply regarding the map's hash seed being randomized to thwart security attacks that rely on a predictable map hash function is the proximate cause of the behavior you're seeing. But even without that security mechanism you would still experience unpredictable behavior when mutating a map while iterating over it. It's just that the problem would depend only on the specific values (i.e., keys) used in your example code.

Do not mutate a map while iterating over it unless you're using something like a functional programming language that provides guarantees about the behavior in that case. Go documents the behavior here: https://golang.org/ref/spec#RangeClause. Specifically,

1. n/a
2. n/a
3. The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If a map entry that has not yet been reached is removed during iteration, the corresponding iteration value will not be produced. If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. If the map is nil, the number of iterations is 0.
4. n/a

--

Kurtis Rader

Caretaker of the exceptional canines Junior and Hank

[Kilos]

For Dan:

I have an idea that the cause is in the runtime function mapiternext.

The runtime calls mapiternext function to choose next bucket to iterate by index,

if we put a key-value into a bucket which already be iterated, then the for-range will not iterate it again,

so the new key-value will not be printed.

But I don't know this idea is true or false.

[Kilos]

For Kurtis:

I know the map will choose random hash seed to init itself, and the iterator will also choose random order to iterate map.

And I know it is a bad idea to add or delete a key when iterating a map, but I want to know what causes the inpredictable result, not the key's iterating order, but the key's count that was printed.

[Kurtis Rader]

On Tue, Nov 10, 2020 at 7:57 PM 'Kilos' via golang-nuts <golan...@googlegroups.com> wrote:

For Dan:

I have an idea that the cause is in the runtime function mapiternext.

The runtime calls mapiternext function to choose next bucket to iterate by index,

if we put a key-value into a bucket which already be iterated, then the for-range will not iterate it again,

so the new key-value will not be printed.

But I don't know this idea is true or false.

Your idea (hypothesis) is basically correct. However, note that it doesn't really matter that Go implements maps using a hash function and a list+bucket data structure or another data structure (e.g., a tree). You cannot safely iterate over a map, in any language, while concurrently mutating the map unless the implementation explicitly says that is okay and documents the semantics. Go expressly says you cannot expect predictable behavior when doing so.

[Kilos]

For Kurtis:

If my idea is correct, then my question has been solved, thank you for replying.

[Kurtis Rader]

On Tue, Nov 10, 2020 at 8:12 PM 'Kilos' via golang-nuts <golan...@googlegroups.com> wrote:

For Kurtis:

I know the map will choose random hash seed to init itself, and the iterator will also choose random order to iterate map.

And I know it is a bad idea to add or delete a key when iterating a map, but I want to know what causes the inpredictable result, not the key's iterating order, but the key's count that was printed.

The count is wrong, sometimes, because you are relying on undefined behavior. Ignore the Go map implementation as it is irrelevant to your question. If Go's map implementation used something like a binary tree without mutating the keys (to make it hard to create a DOS attack) your example program would still behave unpredictably if you vary the keys. Repeat after me: You cannot safely mutate a Go map while iterating over it with the `range` operator. This is true for most map data structures in most, non-functional (e.g., Haskell), programming languages.

[Kilos]

For Kurtis:

Thank you, I will remember this:

You cannot safely mutate a Go map while iterating over it with the `range` operator. 

I will not do this when programming, but when I learned about this, then  I want to know the underlying reason.

And now, I have known.

[Dan Kortschak]

On Tue, 2020-11-10 at 20:28 -0800, 'Kilos' via golang-nuts wrote:
> You cannot safely mutate a Go map while iterating over it with the
> `range` operator.

This is not true, depending on your definition of "safely". See
https://golang.org/ref/spec#For_statements "For statements with range
clause"

```
3. The iteration order over maps is not specified and is not

guaranteed to be the same from one iteration to the next.
If a map entry that has not yet been reached is removed
during iteration, the corresponding iteration value will
not be produced. If a map entry is created during iteration,
that entry may be produced during the iteration or may be
skipped. The choice may vary for each entry created and
from one iteration to the next. If the map is nil, the
number of iterations is 0.

```

So long as you take into account these caveats, mutating a map during a
range will not corrupt the map or other data structure, and will cause
your application to crash.

[Dan Kortschak]

On Wed, 2020-11-11 at 06:02 +0000, 'Dan Kortschak' via golang-nuts
wrote:

> So long as you take into account these caveats, mutating a map during
> a range will not corrupt the map or other data structure, and will
> cause your application to crash.

s/will cause/will not cause/

[Kurtis Rader]

On Tue, Nov 10, 2020 at 10:03 PM 'Dan Kortschak' via golang-nuts <golan...@googlegroups.com> wrote:

On Tue, 2020-11-10 at 20:28 -0800, 'Kilos' via golang-nuts wrote:
> You cannot safely mutate a Go map while iterating over it with the
> `range` operator.

This is not true, depending on your definition of "safely". See
https://golang.org/ref/spec#For_statements "For statements with range
clause"

 

So long as you take into account these caveats, mutating a map during a

range will not corrupt the map or other data structure, and will cause
your application to crash.

Jeebus. H. Christ! Yes, you can "safely" mutate a map while iterating over it. In as much as doing so will not result in a panic; although, I'm not convinced that is true. The point of the O.P. is that they expect the map mutation to always be visible.

         

[Dan Kortschak]

On Tue, 2020-11-10 at 22:17 -0800, Kurtis Rader wrote:
> Jeebus. H. Christ! Yes, you can "safely" mutate a map while iterating
> over it. In as much as doing so will not result in a panic; although,
> I'm not convinced that is true. The point of the O.P. is that they
> expect the map mutation to always be visible.

Yes, this is why I said it depends on how you define safely.

As far as whether is is actually panic-safe, it's specified to be and
so is a bug if it's now. Over the time I've been writing in Go, I have
never seen a map mutation cause a panic unless due to a raced mutation.

[Wojciech S. Czarnecki]

Dnia 2020-11-10, o godz. 19:08:10
"'Kilos' via golang-nuts" <golan...@googlegroups.com> napisał(a):

> I just copy the screenshot in this

Do not do that again. It is akin to saying:

"it is more convenient for me to hit two keys instead of selecting text and paste it what would effect in four strokes for me".
"So now I am asking you for help so you should start to retype my code from the picture and — in case you are using a
screen reader due to failing sight you should ask a seeing human what she sees aloud".

> The empty picture is the code and it's different results.

There are people on this (and many other technical lists) to whom ALL pictures sounds the same.

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