golang thread/goroutine safe append only arrays

[Sankar]

Hi

I have about a few hundred go routines and they all want to append data to a common array / list.

I can create a channel and receive values in that channel. But I was wondering if there is any other threadsafe array datastructure ?

I do not have to worry about deletions as the goroutines will only append values and never modify or delete values.

I remember reading that channels come with a cost and so wanted to know if there are any cheaper alternatives.

Thanks.

Sankar

[Jan Mercl]

On Thu, Sep 25, 2014 at 10:14 AM, Sankar <sankar.c...@gmail.com> wrote:
> I remember reading that channels come with a cost and so wanted to know if
> there are any cheaper alternatives.

http://golang.org/pkg/sync/#Mutex

-j

[Jesse McNelis]

On Thu, Sep 25, 2014 at 6:14 PM, Sankar <sankar.c...@gmail.com> wrote:
> I remember reading that channels come with a cost and so wanted to know if
> there are any cheaper alternatives.

Synchronisation between threads always comes with a cost.
sync.Mutex is a bit cheaper than a channel but also less structured,
easier to get wrong and harder to understand.

[Dave Cheney]

What happens to the data that these goroutines are writing ? You don't seem to be concerned with entries being ordered in this shared buffer so why not have each goroutine collect its own buffer then transmit it via a channel when it is done?

[Sankar P]

2014-09-25 14:05 GMT+05:30 Dave Cheney <da...@cheney.net>:
> What happens to the data that these goroutines are writing ? You don't seem
> to be concerned with entries being ordered in this shared buffer so why not
> have each goroutine collect its own buffer then transmit it via a channel
> when it is done?

Actually each go routine will have only one value to append to the
buffer. I have a WaitGroup where I will wait until all the goroutines
have returned and then I will access the contents of the common
buffer. And as you said, the ordering of the elements in the buffer
does not matter to me.

I was trying to avoid using mutexes or channels as I felt it may be
costly. I was looking for some lock-free datastructure (if any) which
might internally work with some kind of byte-range locks over a
pre-allocated buffer to give an illusion of lock-free-thread-safe
arrays which has only an append operation.

But I will probably leave that experiment later for some free time
hacking and will use mutexes properly for now, remembering Rob Pike's
advice to not use fancy algorithms/datastructures and measure things
before optimizing :)

Thanks.

>
>
> On Thursday, 25 September 2014 18:14:26 UTC+10, Sankar wrote:
>>
>> Hi
>>
>> I have about a few hundred go routines and they all want to append data to
>> a common array / list.
>>
>> I can create a channel and receive values in that channel. But I was
>> wondering if there is any other threadsafe array datastructure ?
>>
>> I do not have to worry about deletions as the goroutines will only append
>> values and never modify or delete values.
>>
>> I remember reading that channels come with a cost and so wanted to know if
>> there are any cheaper alternatives.
>>
>> Thanks.
>>
>> Sankar
>

> --
> You received this message because you are subscribed to a topic in the
> Google Groups "golang-nuts" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/golang-nuts/A1DmY4PiNM4/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.



--
Sankar P
http://psankar.blogspot.com

[Dave Cheney]

On 25 Sep 2014 18:57, "Sankar P" <sankar.c...@gmail.com> wrote:
>
> 2014-09-25 14:05 GMT+05:30 Dave Cheney <da...@cheney.net>:
> > What happens to the data that these goroutines are writing ? You don't seem
> > to be concerned with entries being ordered in this shared buffer so why not
> > have each goroutine collect its own buffer then transmit it via a channel
> > when it is done?
>
> Actually each go routine will have only one value to append to the
> buffer. I have a WaitGroup where I will wait until all the goroutines
> have returned and then I will access the contents of the common
> buffer. And as you said, the ordering of the elements in the buffer
> does not matter to me.
>
> I was trying to avoid using mutexes or channels as I felt it may be
> costly.

Please, please. Write your code _then_ benchmark it if you think it is too slow.

If you do things the other way around, you'll get the wrong result.

[Mateusz Czapliński]

On Thursday, September 25, 2014 10:57:55 AM UTC+2, Sankar wrote:

2014-09-25 14:05 GMT+05:30 Dave Cheney <da...@cheney.net>:
> What happens to the data that these goroutines are writing ? You don't seem
> to be concerned with entries being ordered in this shared buffer so why not
> have each goroutine collect its own buffer then transmit it via a channel
> when it is done?

Actually each go routine will have only one value to append to the
buffer. I have a WaitGroup where I will wait until all the goroutines
have returned and then I will access the contents of the common
buffer. And as you said, the ordering of the elements in the buffer
does not matter to me.

I was trying to avoid using mutexes or channels as I felt it may be
costly. I was looking for some lock-free datastructure (if any) which
might internally work with some kind of byte-range locks over a
pre-allocated buffer to give an illusion of lock-free-thread-safe
arrays which has only an append operation.

But I will probably leave that experiment later for some free time
hacking and will use mutexes properly for now, remembering Rob Pike's
advice to not use fancy algorithms/datastructures and measure things
before optimizing :)

From what you describe, it seems to me, that:
* If you're already waiting for all goroutines to complete, you most probably don't really need to super-micro-optimize around this;
* Also, if you have exactly one result per goroutine, and don't even care about order, I'd think it would be conceptually simpler to even drop the WaitGroup, and instead just do something like below:

ch := make(chan Response, n)
for i:=0; i<n; i++ {
  go func() {
    result := yourWork()
    ch <- result
  }()
}
for i:=0; i<n; i++ {
  result := <-ch
  // process the i-th result
}

/Mateusz.

[Tamás Gulácsi]

2014. szeptember 25., csütörtök 10:57:55 UTC+2 időpontban Sankar a következőt írta:

2014-09-25 14:05 GMT+05:30 Dave Cheney <da...@cheney.net>:
> What happens to the data that these goroutines are writing ? You don't seem
> to be concerned with entries being ordered in this shared buffer so why not
> have each goroutine collect its own buffer then transmit it via a channel
> when it is done?

Actually each go routine will have only one value to append to the
buffer. I have a WaitGroup where I will wait until all the goroutines
have returned and then I will access the contents of the common
buffer. And as you said, the ordering of the elements in the buffer
does not matter to me.

I was trying to avoid using mutexes or channels as I felt it may be
costly. I was looking for some lock-free datastructure (if any) which
might internally work with some kind of byte-range locks over a
pre-allocated buffer to give an illusion of lock-free-thread-safe
arrays which has only an append operation.

But I will probably leave that experiment later for some free time
hacking and will use mutexes properly for now, remembering Rob Pike's
advice to not use fancy algorithms/datastructures and measure things
before optimizing :)

Thanks.

If you REALLY want to avoid synchronization and each goroutine have only one value as a result, then
allocate a slice as big as the number of goroutines, and call each goroutine with the position where
it has to insert its result to:

    results := make([]int, N)
    var wg sync.WaitGroup
    for i := 0; i<N; i++ {
        wg.Add(1)
        go func(i int) {
            results[i] = 42
            wg.Done()
        }
    }
    wg.Wait()

[Liam]

On Thursday, September 25, 2014 1:57:55 AM UTC-7, Sankar wrote:

I was trying to avoid using mutexes or channels as I felt it may be
costly. I was looking for some lock-free datastructure (if any) which
might internally work with some kind of byte-range locks over a
pre-allocated buffer to give an illusion of lock-free-thread-safe
arrays which has only an append operation.

Try a sync/atomic type as the index into your pre-allocated array.
Try a buffered channel, which you close after waitgroup.Wait() finishes, so range works.
Then post a performance analysis of the two approaches.