[go-nuts] Where can I find documentation about non-deterministic map operations within 'range'?

[Gyu-Ho Lee]

Hello,

This great talk (*Kevin Cantwell - What Could Go Wrong?*
-

taught me to be more careful when I am updating map within range.

Here's an example to show non-deterministic behavior of map operations when
I update or delete inside for-loop range.

Try this Go PlayGround:
http://play.golang.org/p/1vMgYhs_3B

func nonDeterministicMapUpdateV1() {
mmap := map[string]int{
"hello": 10,
"world": 50,
"here": 5,
"go": 7,
"code": 11,
}
length := len(mmap)
for i := 0; i < 10; i++ {
fmt.Println("nonDeterministicMapUpdateV1 TRY =", i)
for k, v := range mmap {
mmap[strings.ToUpper(k)] = v * v
delete(mmap, k)
}
if length == len(mmap) {
fmt.Println("Luckily, Deterministic with nonDeterministicMapUpdateV1:",
length, len(mmap))
return
}
}
fmt.Println("Non-Deterministic with nonDeterministicMapUpdateV1:", length,
len(mmap))
}

func nonDeterministicMapUpdateV2() {
mmap := map[string]int{
"hello": 10,
"world": 50,
"here": 5,
"go": 7,
"code": 11,
}
length := len(mmap)
for i := 0; i < 10; i++ {
fmt.Println("nonDeterministicMapUpdateV2 TRY =", i)
ks := []string{}
for k, v := range mmap {
mmap[strings.ToUpper(k)] = v * v
ks = append(ks, k)
}
for _, k := range ks {
delete(mmap, k)
}
if length == len(mmap) {
fmt.Println("Luckily, Deterministic with nonDeterministicMapUpdateV2:",
length, len(mmap))
return
}
}
fmt.Println("Non-Deterministic with nonDeterministicMapUpdateV2:", length,
len(mmap))
}

func deterministicMapSet() {
mmap := make(map[int]bool)
for i := 0; i < 10000; i++ {
mmap[i] = true
}
length := len(mmap)
for i := 0; i < 10000; i++ {
for k := range mmap {
delete(mmap, k)
}
if len(mmap) == 0 {
fmt.Println("Deterministic with deterministicMapSet:", length, len(mmap))
return
}
}
fmt.Println("Non-Deterministic with deterministicMapSet:", length,
len(mmap))
}

func deterministicMapDelete() {
mmap := map[string]int{
"hello": 10,
"world": 50,
"here": 5,
"go": 7,
"code": 11,
}
length := len(mmap)
for i := 0; i < 10000; i++ {
fmt.Println("deterministicMapDelete TRY =", i)
for k := range mmap {
delete(mmap, k)
}
if len(mmap) == 0 {
fmt.Println("Deterministic with deterministicMapDelete:", length, len(mmap))
return
}
}
fmt.Println("Non-Deterministic with deterministicMapDelete:", length,
len(mmap))
}

func deterministicMapUpdate() {
mmap := map[string]int{
"hello": 10,
"world": 50,
"here": 5,
"go": 7,
"code": 11,
}
mmapCopy := make(map[string]int)
length := len(mmap)
for i := 0; i < 10000; i++ {
fmt.Println("deterministicMapUpdate TRY =", i)
for k, v := range mmap {
mmapCopy[strings.ToUpper(k)] = v * v
}
for k := range mmap {
delete(mmap, k)
}
if length == len(mmapCopy) {
fmt.Println("Deterministic with deterministicMapUpdate:", length,
len(mmapCopy))
return
} else {
mmapCopy = make(map[string]int) // to initialize(empty)
//
// (X)
// mmapCopy = nil
}
}
fmt.Println("Non-Deterministic with deterministicMapUpdate:", length,
len(mmap))
}


So I learned that I need to make a separate copy of a map if I want to
update the map with 'range'.
But I still do not understand why. Can anybody explain or point me to
related documentation?

The speaker mentioned Go Spec
(http://golang.org/ref/spec#Deletion_of_map_elements) but I couldn't find
it.

*Go FAQ *(http://golang.org/doc/faq#atomic_maps) instead explains:

Why are map operations not defined to be atomic?

After long discussion it was decided that the typical use of maps did not
require safe access from multiple goroutines, and in those cases where it
did, the map was probably part of some larger data structure or computation
that was already synchronized. Therefore requiring that all map operations
grab a mutex would slow down most programs and add safety to few. This was
not an easy decision, however, since it means uncontrolled map access can
crash the program.
The language does not preclude atomic map updates. When required, such as
when hosting an untrusted program, the implementation could interlock map
access.

But how do I interpret this to explain the non-deterministic behaviors
above?
I do not use any goroutines in my code.

Thanks in advance!

[Dan Kortschak]

What behaviour are you expecting here? You are doing things that are confounding a reasonable valid analysis AFAICS.

Here's an example to show non-deterministic behavior of map operations when I update or delete inside for-loop range.
http://play.golang.org/p/1vMgYhs_3B

[Gyu-Ho Lee]

Thanks, Dan.

Sorry for being not clear.

I wasn't expecting anything from the code.
If you run the same code in local machine
(http://play.golang.org/p/1vMgYhs_3B), about 1 out of 10 returns:

nonDeterministicMapUpdateV1 TRY = 0
Luckily, Deterministic with nonDeterministicMapUpdateV1: 5 5

nonDeterministicMapUpdateV2 TRY = 0
Luckily, Deterministic with nonDeterministicMapUpdateV2: 5 5

which means there's no guarantee that the updates on map within for-range
loop would go through
, therefore we need a copy of a map.

I am just trying to understand WHY this happens.

The talk only briefly mentions the behavior but not why.
http://youtu.be/VC3QXZ-x5yI


Thanks,

Post by Dan Kortschak
What behaviour are you expecting here? You are doing things that are
confounding a reasonable valid analysis AFAICS.

Post by Gyu-Ho Lee
Here's an example to show non-deterministic behavior of map operations

when I update or delete inside for-loop range.

Post by Gyu-Ho Lee
http://play.golang.org/p/1vMgYhs_3B

[Dan Kortschak]

James has provided the answer, but to explain why I say you are
confounding your analysis - you are doing ten time an add of the
uppercase version of the key and then deleting the key. The second time
this happens you delete the uppercase key.

If you do the test only once and print the keys that are being operated
on you will see the cause; you are adding keys and then the range
expression finds those added keys and does the operation above - you add
and uppercased version of an uppercase key with and then delete the
original [sic] uppercase key -> no more entry.

Post by Gyu-Ho Lee
Sorry for being not clear.
I wasn't expecting anything from the code.
If you run the same code in local machine
nonDeterministicMapUpdateV1 TRY = 0
Luckily, Deterministic with nonDeterministicMapUpdateV1: 5 5
nonDeterministicMapUpdateV2 TRY = 0
Luckily, Deterministic with nonDeterministicMapUpdateV2: 5 5
which means there's no guarantee that the updates on map within for-range
loop would go through
, therefore we need a copy of a map.
I am just trying to understand WHY this happens.

[Gyu-Ho Lee]

Oh, yeah it wasn't a correct way of generating an example code.

Thanks for pointing that out!

Sincerely,
Gyu-Ho Lee

On Thu, Jul 30, 2015 at 4:23 PM, Dan Kortschak <

Post by Dan Kortschak
James has provided the answer, but to explain why I say you are
confounding your analysis - you are doing ten time an add of the
uppercase version of the key and then deleting the key. The second time
this happens you delete the uppercase key.
If you do the test only once and print the keys that are being operated
on you will see the cause; you are adding keys and then the range
expression finds those added keys and does the operation above - you add
and uppercased version of an uppercase key with and then delete the
original [sic] uppercase key -> no more entry.

Post by Gyu-Ho Lee
Sorry for being not clear.
I wasn't expecting anything from the code.
If you run the same code in local machine
nonDeterministicMapUpdateV1 TRY = 0
Luckily, Deterministic with nonDeterministicMapUpdateV1: 5 5
nonDeterministicMapUpdateV2 TRY = 0
Luckily, Deterministic with nonDeterministicMapUpdateV2: 5 5
which means there's no guarantee that the updates on map within for-range
loop would go through
, therefore we need a copy of a map.
I am just trying to understand WHY this happens.

[James Aguilar]

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

See the section that starts with "The iteration order over maps ..."

You may or may not see new keys that are added when you add during range.
You may or may not see keys that you delete if they are not the current key.

[Gyu-Ho Lee]

Thanks a lot.


1. The iteration order over maps is not specified and is not guaranteed
to be the same from one iteration to the next. If map entries that have not
yet been reached are removed during iteration, the corresponding iteration
values will not be produced. If map entries are 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.


That link is exactly what I was looking for. Now makes sense.

Post by James Aguilar
https://golang.org/ref/spec#For_statements
See the section that starts with "The iteration order over maps ..."
You may or may not see new keys that are added when you add during range.
You may or may not see keys that you delete if they are not the current key.

[James Aguilar]

In most languages it is actually an error to modify an unordered map during
iteration. In Java, it will produce a ConcurrentModificationException. In
c++, "exciting" bugs will occur.

Post by Gyu-Ho Lee
Thanks a lot.
1. The iteration order over maps is not specified and is not
guaranteed to be the same from one iteration to the next. If map entries
that have not yet been reached are removed during iteration, the
corresponding iteration values will not be produced. If map entries are
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.
That link is exactly what I was looking for. Now makes sense.

Post by James Aguilar
https://golang.org/ref/spec#For_statements
See the section that starts with "The iteration order over maps ..."
You may or may not see new keys that are added when you add during range.
You may or may not see keys that you delete if they are not the current key.

[Dan Kortschak]

Post by James Aguilar
In most languages it is actually an error to modify an unordered map
during iteration. In Java, it will produce a
ConcurrentModificationException. In c++, "exciting" bugs will occur.

In Go though it is accetpable to do deletions on the ranged keys. Gyu-Ho
was confounding that though by adding at the same time and expecting the
added keys not to be iterated over.

[James Aguilar]

Yep. I'm just providing flavor for go's decision. One could wish for a map
that would never produce added values during iteration, but other languages
offer even less than go in this regard.

Post by Dan Kortschak

Post by James Aguilar
In most languages it is actually an error to modify an unordered map
during iteration. In Java, it will produce a
ConcurrentModificationException. In c++, "exciting" bugs will occur.

In Go though it is accetpable to do deletions on the ranged keys. Gyu-Ho
was confounding that though by adding at the same time and expecting the
added keys not to be iterated over.