C# ConcurrentDictionary in golang

[si guy]

Hi all, while using go and XNA(c# game engine by Microsoft) together I've come to appreciate the massive differences in the concurrency models of go and c#. Namely the fact that naive concurrency in c# is locked shared memory and/or callbacks while go seems to be the opposite.

One of the more useful constructs I've used in c# is the ConcurrentDictionary generic type. The generic part isn't what interests me, it's the atomic operations.

My go program uses the container/list package extensively for various buckets of various things, and I'm wondering if there is a go package available which offers the simpler atomicity offered by MSs ConcurrentDictionary.

I'm repeatedly finding myself building new and interesting(see complicated) ways to have concurrently mutable lists and I don't know if I'm going about it the right way. I'm not looking for a shared memory list, just a convenient wrapper for atomic operations that I can learn from.

Any suggestions from the go dashboard or online code examples would be really helpful.

Thanks.

-Simon Watt

[Mikhail Strebkov]

Maybe not exactly what you are looking for, but worth mentioning - there is a good example of implementing concurrent wrapper around standard go map (using channels internally) in the Mark Summerfield book (section 7.2.3. Example: Thread-Safe Map): http://bit.ly/xFYFLV

[Dmitry Vyukov]

On Mon, Jan 23, 2012 at 2:22 AM, si guy <sjw...@gmail.com> wrote:

Hi all, while using go and XNA(c# game engine by Microsoft) together I've come to appreciate the massive differences in the concurrency models of go and c#. Namely the fact that naive concurrency in c# is locked shared memory and/or callbacks while go seems to be the opposite.

One of the more useful constructs I've used in c# is the ConcurrentDictionary generic type. The generic part isn't what interests me, it's the atomic operations.

My go program uses the container/list package extensively for various buckets of various things, and I'm wondering if there is a go package available which offers the simpler atomicity offered by MSs ConcurrentDictionary.

map+sync.Mutex should do.

 

I'm repeatedly finding myself building new and interesting(see complicated) ways to have concurrently mutable lists and I don't know if I'm going about it the right way. I'm not looking for a shared memory list, just a convenient wrapper for atomic operations that I can learn from.

Not sure what you mean by " wrapper for atomic operations", but std sync/atomic package contains atomic operations.

[André Moraes]

> I'm repeatedly finding myself building new and interesting(see complicated) ways to have concurrently mutable lists and I don't know if I'm going about it the right way. I'm not looking for a shared memory list, just a convenient wrapper for atomic operations that I can learn from.
>
> Any suggestions from the go dashboard or online code examples would be really helpful.

This talk from Andrew,
http://blip.tv/open-source-developers-conference/the-go-programming-language-4450722,
shows how to make a map thread safe without too much trouble.

The sample from Mark's book is quite heavy given the simple goal a
thread-safe map.

Also is a example on how to decide when to use sync package vs channles.

--
André Moraes
http://andredevchannel.blogspot.com/

[Mark Summerfield]

On Mon, 23 Jan 2012 09:58:48 -0200
André Moraes <and...@gmail.com> wrote:
> > I'm repeatedly finding myself building new and interesting(see
> > complicated) ways to have concurrently mutable lists and I don't
> > know if I'm going about it the right way. I'm not looking for a
> > shared memory list, just a convenient wrapper for atomic operations
> > that I can learn from.
> >
> > Any suggestions from the go dashboard or online code examples would
> > be really helpful.
>
> This talk from Andrew,
> http://blip.tv/open-source-developers-conference/the-go-programming-language-4450722,
> shows how to make a map thread safe without too much trouble.
>
> The sample from Mark's book is quite heavy given the simple goal a
> thread-safe map.

Actually, the goal of that example is really to show how to use channels
& goroutines to create a thread-safe data structure generally. It is a
bit heavy as you say, so I also show alternative approaches, one using
mutexes, and another using separate maps (so there's no contention during
processing), followed by merging the maps into one.

> Also is a example on how to decide when to use sync package vs
> channles.

--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
"Programming in Go" - ISBN 0321774639
http://www.qtrac.eu/gobook.html

[si guy]

Excellent stuff there Mark, purchased. Look forward to final revision.

[si guy]

The issue I have doesn't allow me to use a mutexed map, or even a map of mutexed items because i want to be able to have multiple workers operate on the same collection simultaneously and that includes adding new elements and removing dead ones on the fly.

I considered splitting and merging but that has some weird memory copy implications that hurt performance (for the adding elements case).

My best solution to date is to defer the addition and removal until all of the workers are done which is not an issue for me because these are physics frames in a video game engine, but that does mean an extra synchronized step.

I should note that these additions and removals also trigger external events so they can't be hidden behind the scenes.

Fortunately the items don't interact with each other so I am able to divide them by quadtree, i am still looking for a possible further use for that detail.

Thanks for the help.

-Simon Watt

[Kyle Lemons]

The issue I have doesn't allow me to use a mutexed map, or even a map of mutexed items because i want to be able to have multiple workers operate on the same collection simultaneously and that includes adding new elements and removing dead ones on the fly.

That's not really what you mean.  You don't want a map on which every access is interlocked.  Two solutions are to use an RWMutex (if you read much more often than write), and to pipeline your computation (all workers read from a map and compute data which is queued and published to an outgoing map at the end).

[Jeff Hodges]

The short answer, si guy, is that there is no lock-free hashmap at the
level of C#'s ConcurrentDictionary or highscalelib's
NonBlockingHashMap.

There are various ways you may write your own layer on top of Go's map
to make it concurrency-safe. They are known to be less sophisticated
than NBHM or ConcurrentDictionary. Performance comparisons have not
been made.

It would probably be nice to have those things, but Go does not yet have them.

[Dmitry Vyukov]

The simplest option how to get a concurrent hashmap from a non-concurrent one is partition it:

type Part struct {

  mtx sync.RWMutex

  m map[int]int

  pad [128]byte  

}

type ConcMap [51]Part

func (m *ConcMap) Get(k int) int {

  p := m[k%51]

  p.mtx.RLock()

  v := p.m[k]

  p.mtx.RUnlock()

  return v

}

It should work reasonably well. At least much better than a centralized map or a goroutine-wrapped map.