FAQ

On Friday, February 18, 2011 4:48:36 PM UTC+2, Ian Lance Taylor wrote:
josvazg <jos...@gmail.com <javascript:>> writes:

There are no locks on maps. So I can make a concurrent map by putting a

goroutine in charge of it, and communicating with the goroutine via a
channel. [snipped]
So, what specifically do we gain by defining a concurrent map?
This way you lock the entire map for every write operation. Good concurrent
maps, like Java's ConcurrentMap, would stripe the locks, and a write would
lock only a subset of the keys, reducing contention. See [0]. I'm not
talking about things like Cliff Click's concurrent hashmap, which is
completely lock free, and design to avoid contention even for a large
number of working threads[1].

I'm not saying it should be in the standard library, but I'll be very happy
to see proven implementation. These algorithms are hard to get right.

[0] http://javaopensourcecode.blogspot.co.il/2012/06/concurrenthashmap.html
[1] http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf


>

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Brendan Tracey at Apr 6, 2014 at 8:42 am

    doesn't make sense to speak of a concurrent data structure with no locks
    at all.
    Could I ask you to expand on this (to be clear about terminology)? When you
    say "lock" do you mean in the ASM sense, or in a sync.Mutex sense (or a
    different one)? It seems like go allows you to have "lockless" data
    structures by using channels (though of course the runtime is helping you
    out)

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jan Mercl at Apr 6, 2014 at 8:56 am

    On Sun, Apr 6, 2014 at 10:42 AM, Brendan Tracey wrote:
    doesn't make sense to speak of a concurrent data structure with no locks
    at all.

    Could I ask you to expand on this (to be clear about terminology)? When you
    say "lock" do you mean in the ASM sense, or in a sync.Mutex sense (or a
    different one)? It seems like go allows you to have "lockless" data
    structures by using channels (though of course the runtime is helping you
    out)
    Please note you've quoted Ian's words, but CC'ed me, not him ;-)

    CC: Ian

    -j

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ian Lance Taylor at Apr 7, 2014 at 5:03 pm

    On Sun, Apr 6, 2014 at 1:42 AM, Brendan Tracey wrote:
    doesn't make sense to speak of a concurrent data structure with no locks
    at all.

    Could I ask you to expand on this (to be clear about terminology)? When you
    say "lock" do you mean in the ASM sense, or in a sync.Mutex sense (or a
    different one)? It seems like go allows you to have "lockless" data
    structures by using channels (though of course the runtime is helping you
    out)
    Note that this thread is being resurrected from three years ago.

    Channels count as locks in the terminology I was using, since they
    have internal locks in the runtime. When I said that it doesn't make
    sense to speak of a concurrent data structure with no locks I meant,
    as you suggest, locks in the assembler sense.

    Ian

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Scott Pakin at Apr 7, 2014 at 8:09 pm

    On Monday, April 7, 2014 11:03:40 AM UTC-6, Ian Lance Taylor wrote:
    Channels count as locks in the terminology I was using, since they
    have internal locks in the runtime. When I said that it doesn't make
    sense to speak of a concurrent data structure with no locks I meant,
    as you suggest, locks in the assembler sense.
    Why does that not make sense? I interpret concurrent data structures as
    being wait-free (cf. Herlihy <http://dx.doi.org/10.1145/114005.102808>),
    meaning that—unlike lock-based mechanisms—a slow thread cannot delay other
    threads' progress. Atomic assembler instructions can be used for a lot
    more than implementing locks. For example, a compare&swap can be used to
    append a value to a linked list (compare to NULL and swap in a new
    pointer). Wouldn't you consider such a linked-list implementation to be a
    concurrent data structure with no locks in the assembler sense?

    — Scott

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Ian Lance Taylor at Apr 7, 2014 at 8:50 pm

    On Mon, Apr 7, 2014 at 1:09 PM, Scott Pakin wrote:
    On Monday, April 7, 2014 11:03:40 AM UTC-6, Ian Lance Taylor wrote:

    Channels count as locks in the terminology I was using, since they
    have internal locks in the runtime. When I said that it doesn't make
    sense to speak of a concurrent data structure with no locks I meant,
    as you suggest, locks in the assembler sense.

    Why does that not make sense? I interpret concurrent data structures as
    being wait-free (cf. Herlihy), meaning that—unlike lock-based mechanisms—a
    slow thread cannot delay other threads' progress. Atomic assembler
    instructions can be used for a lot more than implementing locks. For
    example, a compare&swap can be used to append a value to a linked list
    (compare to NULL and swap in a new pointer). Wouldn't you consider such a
    linked-list implementation to be a concurrent data structure with no locks
    in the assembler sense?
    No. It implies that compare-and-swap is much faster than a mutex,
    which isn't so--it's only slightly faster I consider the name
    lock-free to be misleading. A lock is a lock.

    Ian

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Michael Jones at Apr 7, 2014 at 10:42 pm
    It would be nice to have a "forgo" that was a parallel for with an implicit
    sync at the end...

    On Mon, Apr 7, 2014 at 1:50 PM, Ian Lance Taylor wrote:
    On Mon, Apr 7, 2014 at 1:09 PM, Scott Pakin wrote:
    On Monday, April 7, 2014 11:03:40 AM UTC-6, Ian Lance Taylor wrote:

    Channels count as locks in the terminology I was using, since they
    have internal locks in the runtime. When I said that it doesn't make
    sense to speak of a concurrent data structure with no locks I meant,
    as you suggest, locks in the assembler sense.

    Why does that not make sense? I interpret concurrent data structures as
    being wait-free (cf. Herlihy), meaning that--unlike lock-based
    mechanisms--a
    slow thread cannot delay other threads' progress. Atomic assembler
    instructions can be used for a lot more than implementing locks. For
    example, a compare&swap can be used to append a value to a linked list
    (compare to NULL and swap in a new pointer). Wouldn't you consider such a
    linked-list implementation to be a concurrent data structure with no locks
    in the assembler sense?
    No. It implies that compare-and-swap is much faster than a mutex,
    which isn't so--it's only slightly faster I consider the name
    lock-free to be misleading. A lock is a lock.

    Ian

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.


    --
    *Michael T. Jones | Chief Technology Advocate | mtj@google.com
    <mtj@google.com> | +1 650-335-5765 <%2B1%20650-335-5765>*

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Pete Wilson at Apr 8, 2014 at 1:40 am
    Ah; occam's par i = 0 for n {..}
    On Monday, April 7, 2014 5:41:34 PM UTC-5, Michael Jones wrote:

    It would be nice to have a "forgo" that was a parallel for with an
    implicit sync at the end...


    On Mon, Apr 7, 2014 at 1:50 PM, Ian Lance Taylor <ia...@golang.org<javascript:>
    wrote:
    On Mon, Apr 7, 2014 at 1:09 PM, Scott Pakin <scot...@pakin.org<javascript:>>
    wrote:
    On Monday, April 7, 2014 11:03:40 AM UTC-6, Ian Lance Taylor wrote:

    Channels count as locks in the terminology I was using, since they
    have internal locks in the runtime. When I said that it doesn't make
    sense to speak of a concurrent data structure with no locks I meant,
    as you suggest, locks in the assembler sense.

    Why does that not make sense? I interpret concurrent data structures as
    being wait-free (cf. Herlihy), meaning that—unlike lock-based
    mechanisms—a
    slow thread cannot delay other threads' progress. Atomic assembler
    instructions can be used for a lot more than implementing locks. For
    example, a compare&swap can be used to append a value to a linked list
    (compare to NULL and swap in a new pointer). Wouldn't you consider such a
    linked-list implementation to be a concurrent data structure with no locks
    in the assembler sense?
    No. It implies that compare-and-swap is much faster than a mutex,
    which isn't so--it's only slightly faster I consider the name
    lock-free to be misleading. A lock is a lock.

    Ian

    --
    You received this message because you are subscribed to the Google Groups
    "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an
    email to golang-nuts...@googlegroups.com <javascript:>.
    For more options, visit https://groups.google.com/d/optout.


    --
    *Michael T. Jones | Chief Technology Advocate | m...@google.com
    <javascript:> | +1 650-335-5765*
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jsor at Apr 8, 2014 at 2:16 am

    On Monday, April 7, 2014 3:41:34 PM UTC-7, Michael Jones wrote:
    It would be nice to have a "forgo" that was a parallel for with an
    implicit sync at the end...

    Eh, it's pretty trivial to implement

    forgo _,el := range list {
         // Do Stuff
    }

    Is basically

    wg := sync.WaitGroup{}
    wg.Add(len(list))
    for _,el := range list {
         go func() {
              // Do Stuff
              wg.Done()
          }
    }

    Yeah, there's a little boilerplate, but IMO not enough to justify a
    language feature.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jsor at Apr 8, 2014 at 2:17 am
    Er, I forgot wg.Wait() after the loop, naturally.
    On Monday, April 7, 2014 7:16:44 PM UTC-7, Jsor wrote:
    On Monday, April 7, 2014 3:41:34 PM UTC-7, Michael Jones wrote:

    It would be nice to have a "forgo" that was a parallel for with an
    implicit sync at the end...

    Eh, it's pretty trivial to implement

    forgo _,el := range list {
    // Do Stuff
    }

    Is basically

    wg := sync.WaitGroup{}
    wg.Add(len(list))
    for _,el := range list {
    go func() {
    // Do Stuff
    wg.Done()
    }
    }

    Yeah, there's a little boilerplate, but IMO not enough to justify a
    language feature.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Oleku Konko at Apr 8, 2014 at 10:23 am
    Your code is not efficient ... a poll approach is better that creating a
    goroutine in each loop
    On Tuesday, April 8, 2014 3:16:44 AM UTC+1, Jsor wrote:
    On Monday, April 7, 2014 3:41:34 PM UTC-7, Michael Jones wrote:

    It would be nice to have a "forgo" that was a parallel for with an
    implicit sync at the end...

    Eh, it's pretty trivial to implement

    forgo _,el := range list {
    // Do Stuff
    }

    Is basically

    wg := sync.WaitGroup{}
    wg.Add(len(list))
    for _,el := range list {
    go func() {
    // Do Stuff
    wg.Done()
    }
    }

    Yeah, there's a little boilerplate, but IMO not enough to justify a
    language feature.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jsor at Apr 8, 2014 at 10:48 am
    Okay, fair enough, but what else would you expect a forgo loop to do?
    Anything other than being an alias for calling "Go" each loop iteration
    would be what I'd call "surprising behavior".
    On Tuesday, April 8, 2014 3:23:47 AM UTC-7, Oleku Konko wrote:

    Your code is not efficient ... a poll approach is better that creating a
    goroutine in each loop
    On Tuesday, April 8, 2014 3:16:44 AM UTC+1, Jsor wrote:
    On Monday, April 7, 2014 3:41:34 PM UTC-7, Michael Jones wrote:

    It would be nice to have a "forgo" that was a parallel for with an
    implicit sync at the end...

    Eh, it's pretty trivial to implement

    forgo _,el := range list {
    // Do Stuff
    }

    Is basically

    wg := sync.WaitGroup{}
    wg.Add(len(list))
    for _,el := range list {
    go func() {
    // Do Stuff
    wg.Done()
    }
    }

    Yeah, there's a little boilerplate, but IMO not enough to justify a
    language feature.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Hotei at Apr 8, 2014 at 12:58 pm
    My template for that type code frequently uses a pool of NCPU goroutines.
      While it's usually just a few percent faster than using one goroutine per
    loop, the bigger benefit is I can still use it when the loop is done 1e+9
    times. That behavior might be better than crashing with too many goroutines.
    On Tuesday, April 8, 2014 6:48:00 AM UTC-4, Jsor wrote:

    Okay, fair enough, but what else would you expect a forgo loop to do?
    Anything other than being an alias for calling "Go" each loop iteration
    would be what I'd call "surprising behavior".
    On Tuesday, April 8, 2014 3:23:47 AM UTC-7, Oleku Konko wrote:

    Your code is not efficient ... a poll approach is better that creating a
    goroutine in each loop
    On Tuesday, April 8, 2014 3:16:44 AM UTC+1, Jsor wrote:
    On Monday, April 7, 2014 3:41:34 PM UTC-7, Michael Jones wrote:

    It would be nice to have a "forgo" that was a parallel for with an
    implicit sync at the end...

    Eh, it's pretty trivial to implement

    forgo _,el := range list {
    // Do Stuff
    }

    Is basically

    wg := sync.WaitGroup{}
    wg.Add(len(list))
    for _,el := range list {
    go func() {
    // Do Stuff
    wg.Done()
    }
    }

    Yeah, there's a little boilerplate, but IMO not enough to justify a
    language feature.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Scott Pakin at Apr 8, 2014 at 12:03 am

    On Monday, April 7, 2014 2:50:48 PM UTC-6, Ian Lance Taylor wrote:
    No. It implies that compare-and-swap is much faster than a mutex,
    which isn't so--it's only slightly faster I consider the name
    lock-free to be misleading. A lock is a lock.
    In many cases, lock-free (by which I mean wait-free) algorithms are in fact
    *slower* than lock-based algorithms in normal operating mode. The main
    advantage is not performance but rather resiliency. In a lock-based
    algorithm, if a thread that holds the lock dies, the program's in bad shape
    and needs to figure out a way to recover. In a lock-free algorithm, thread
    loss has no impact on correctness or program progress.

    While a lock may be a lock, it really is possible to do lock-free
    concurrency. It's just that it tends to be slower and more complicated
    than simply using compare-and-swap as a locking mechanism.

    — Scott

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedApr 6, '14 at 8:17a
activeApr 8, '14 at 12:58p
posts14
users10
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase