Efficient ForEach() on a map protected by a mutex

[tsuna]

Hi there,

I have a struct that contains an unexported map protected by a mutex, let’s say something like:

type Map struct {

mtx sync.Mutex

col map[string]interface{}

}

I want to implement a ForEach method that works in O(1) space and doesn’t hold the mutex while working on each entry.  This is what I have:

func (m *Map) ForEach(fn func(k, v interface{})) {

m.mtx.Lock()

for k, v := range m.col {

m.mtx.Unlock()

fn(k, v)

m.mtx.Lock()

}

m.mtx.Unlock()

}

(runnable example: https://play.golang.org/p/tX2lCCYWxq)

The language spec says:

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

With the caveats mentioned above regarding concurrent deletions/insertions in mind, is this implementation of ForEach correct?  Is there a better way?

Thanks.

--

Benoit "tsuna" Sigoure

[Jan Mercl]

On Sat, Jan 7, 2017 at 2:12 AM tsuna <tsun...@gmail.com> wrote:

> Is there a better way?

Is fn allowed to mutate the map? If not then the locking/unlocking is not necessary at all. If yes then there's a race between acquiring the k,v pair from the map under a lock and calling fn with those, now possibly obsolete values.

--

-j

[Dragos Harabor]

> Is there a better way?

Is fn allowed to mutate the map? If not then the locking/unlocking is not necessary at all. If yes then there's a race between acquiring the k,v pair from the map under a lock and calling fn with those, now possibly obsolete values.

Even if fn does not mutate the map, some other goroutine could and that's not safe without holding any locks. From the Go 1.6 release notes:

The runtime has added lightweight, best-effort detection of concurrent misuse of maps. As always, if one goroutine is writing to a map, no other goroutine should be reading or writing the map concurrently. If the runtime detects this condition, it prints a diagnosis and crashes the program. The best way to find out more about the problem is to run the program under the race detector, which will more reliably identify the race and give more detail.

Perhaps a sync.RWMutex would work better, just hold the RLock while iterating which will allow other goroutines to also read from the map (but not change the map).

Dragos

[Keith Randall]

I'm not sure I understand what you're trying to guarantee.  The code you've shown looks fine, but the devil is in the details of what fn does.

The fundamental constraint is that you need to make sure that no two concurrent operations, at least one of which is a write, happen to the map.  Treat iteration as a read.  And it isn't one read extending for the whole loop.  It is one "instantaneous" read each time a new k,v is assigned.

So fn can read all it wants.

If fn writes, those writes must be synchronized so that they do not happen concurrently with the ForEach goroutine iterating.

So if fn writes in the same goroutine that ForEach is running in, that is fine.

If fn spawns other goroutines to write to the map, asks other goroutines to write to the map via channels, etc. then those accesses must be properly synchronized.

One way to do that is to use the same lock as you used in ForEach around those accesses.

Another way would be for fn to wait for all the write operations it requested to complete (wait on a channel or WaitGroup, say) before returning.

[tsuna]

On Sat, Jan 7, 2017 at 7:00 PM, 'Keith Randall' via golang-nuts <golan...@googlegroups.com> wrote:

On Friday, January 6, 2017 at 5:12:54 PM UTC-8, tsuna wrote:

Hi there,

I have a struct that contains an unexported map protected by a mutex, let’s say something like:

type Map struct {

mtx sync.Mutex

col map[string]interface{}

}

I want to implement a ForEach method that works in O(1) space and doesn’t hold the mutex while working on each entry.  This is what I have:

func (m *Map) ForEach(fn func(k, v interface{})) {

m.mtx.Lock()

for k, v := range m.col {

m.mtx.Unlock()

fn(k, v)

m.mtx.Lock()

}

m.mtx.Unlock()

}

(runnable example: https://play.golang.org/p/tX2lCCYWxq)

The language spec says:

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

With the caveats mentioned above regarding concurrent deletions/insertions in mind, is this implementation of ForEach correct?  Is there a better way?

I'm not sure I understand what you're trying to guarantee.

That the code is race-free.  The guarantees on data access are pretty loose – fn() could be called on a key-value pair while it’s being removed/changed by another goroutine.  That’s okay.

 

The code you've shown looks fine, but the devil is in the details of what fn does.

The fundamental constraint is that you need to make sure that no two concurrent operations, at least one of which is a write, happen to the map.  Treat iteration as a read.  And it isn't one read extending for the whole loop.  It is one "instantaneous" read each time a new k,v is assigned.

So fn can read all it wants.

If fn writes, those writes must be synchronized so that they do not happen concurrently with the ForEach goroutine iterating.

So if fn writes in the same goroutine that ForEach is running in, that is fine.

If fn spawns other goroutines to write to the map, asks other goroutines to write to the map via channels, etc. then those accesses must be properly synchronized.

One way to do that is to use the same lock as you used in ForEach around those accesses.

Yes, that’s exactly what’s happening.  The contrived example I showed only included ForEach(), but I also have Get(k) and Set(k, v) methods on this struct, which can be called concurrently from other goroutines.  Of course they also acquire the same mutex.

Alright, so thanks for checking this wasn’t insane.  The code looks weird, but it is what it is.

--

Benoit "tsuna" Sigoure

[Dragos Harabor]

You can compile/run with -race :

https://golang.org/doc/articles/race_detector.html

[tsuna]

On Sun, Jan 8, 2017 at 8:42 AM, Dragos Harabor <dh...@harabor.com> wrote:
> You can compile/run with -race :
> https://golang.org/doc/articles/race_detector.html

Yes I’m very familiar with this, thank you, but the race detector
doesn’t guarantee your code is correct, and it’s hard to run in
production due to the insane memory overhead. So the absence of
complaints from the race detector is a good thing, and we already run
our unit tests with it in an automated fashion, but that’s no
substitute for actually looking at the logic in the code and asking
the question “is this actually legit”.

--
Benoit "tsuna" Sigoure

[Egon]

On Saturday, 7 January 2017 03:12:54 UTC+2, tsuna wrote:

 

Is there a better way?

It depends on the problem being solved by the map. And on all the different statistics: R/W ratio, key and value types, map size, what fn does etc. etc.

+ Egon

[Dragos Harabor]

Looks like we'll have even better runtime detection in 1.8:

https://beta.golang.org/doc/go1.8#mapiter

And I agree with what you said above.