Re: [go-nuts] Are there any plans to add concurrent algorithms or types?

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

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

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

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

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

Ah; occam's par i = 0 for n {..}

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.

Er, I forgot wg.Wait() after the loop, naturally.

Your code is not efficient ... a poll approach is better that creating a
goroutine in each loop

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

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.

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