LIFO: Blocking pop() non-blocking push()

[Aiden]

Hi all,

I'm new to Go and writing a LIFO stack with a non-blocking Push() and a Pop() that blocks when the
stack is empty (for multiple consumers/producers). I have made an example here:

http://play.golang.org/p/poxU3ccuFE

The issue i'm having (ignoring my crude use of interface{}, slices and buffered channels) is that
the StackCount never increases for consumers, so I get this kind of output:

2009/11/10 23:00:00 PushRoutine() Pushing to stack[2]
2009/11/10 23:00:00 PushRoutine() Stack size is 3, waking a consumer
2009/11/10 23:00:00 Pop() Woken up!
2009/11/10 23:00:00 Pop() got lock on stack of 0
2009/11/10 23:00:00 Pop() Waiting for wakeup, stack empty

Any tips or advice appriciated. I get the feeling my implementation is
either fundamentally wrong or just buggy ... but I am just learning :)

[steve wang]

You should change 

func NewWorkStack() WorkStack

to

func NewWorkStack() *WorkStack

[Aiden]

Hi Steve, I knew there would be something trivial :(
I'm disappointed in myself. Seems to be workin now.

http://play.golang.org/p/HJ89OulA7U

Thanks ;) Now for some more testing/bug hunting on it.

[steve wang]

I think a good way is to write some code and test it in turn rather than write piles of code and test it.

Keep the right rhythm of coding and testing, you will find it much easier in programming.

[Aiden]

lol too true, embarassingly im a long-time programmer with a C background so you'd think i'd know better
and be stumped less easily :P

[David DENG]

Have a look at my implementation for your LIFO stack, I think its much easier to understand:

http://play.golang.org/p/xL91hyi7sT

David

On Tuesday, January 8, 2013 10:05:55 PM UTC+8, Aiden wrote:

[steve wang]

Well, I have mine too.

http://play.golang.org/p/WH6Q2t3hcz

[Aiden]

Thanks David, that does look cleaner :) I enjoyed reading it.

[Aiden]

Thanks Steve! That's much better, my use of slices was all over the place in terms of sizing semantics.

[Dustin Sallings]

Aiden <aide...@gmail.com> writes:

> Hi Steve, I knew there would be something trivial :(
> I'm disappointed in myself. Seems to be workin now.
>
> http://play.golang.org/p/HJ89OulA7U
>
> Thanks ;) Now for some more testing/bug hunting on it.

Two things that stuck out for me:

1. Why are you do you have a busy loop in PushRoutine()?
2. Your lock channel is confusing.

Regarding #1: http://play.golang.org/p/XaI8h57-09

That seems clearer and will definitely use less CPU.

Regarding #2... I just don't quite understand it. The code operating
on channels isn't going to be doing anything if there's nothing on the
channel. You're best off either sending everything through channels, or
just using a plain mutex.

--
dustin

[Aiden]

Hi Dustin,

Thanks for the feedback. As for the busy loop, I was using a pattern I saw elsewhere
on the net where the select{} on the channel blocks waiting for a signal to wake the goroutine,
stopping the busyness of the for{}, and the for{} exists only to never stop reading items
from PushChan ... or am I mistaken there?

Your range example does look clearer, I guess I didn't pick up that range polls
until PushChan is closed and performs the for body on each item. They look equivalent to me?

The Lock was used in-place of a mutex (as per go blogs etc) to stop the concurrency issue
of Pop() decrementing and PushRoutine() incrementing (and both stuffing in to the slice) without control.
TBH both the other examples given by David and Steve are much cleaner altogether.

[Aiden]

IIRC the code was written from http://golang.org/doc/effective_go.html#sharing , first attempt at doing anything useful with Chans,
so bound to be ugly. The for{select{}} non-busy endless channel poll pattern is used there and in many of the solutions given in go-nuts posts ...
Unless I misunderstood that completely.

On Tuesday, 8 January 2013 19:16:58 UTC, Dustin wrote:

[Aiden]

Hi David, I ended up using a version of yours. It is simple and readable. Thanks.

On Tuesday, 8 January 2013 15:30:35 UTC, David DENG wrote:

[Dustin Sallings]

Aiden <aide...@gmail.com> writes:


> Thanks for the feedback. As for the busy loop, I was using a pattern I
> saw elsewhere on the net where the select{} on the channel blocks
> waiting for a signal to wake the goroutine, stopping the busyness of
> the for{}, and the for{} exists only to never stop reading items from
> PushChan ... or am I mistaken there?

That was a misread on my part. select with just one channel does the
same thing as not using select. When I see that code with only one
case, I assume there's a default (because I wouldn't expect you to do it
for any other reason).

Should do roughly the same thing.

> Your range example does look clearer, I guess I didn't pick up that
> range polls until PushChan is closed and performs the for body on each
> item. They look equivalent to me?

Not quite equivalent. Yours didn't terminate on close (which *would*
make it a busy loop).

> The Lock was used in-place of a mutex (as per go blogs etc) to stop
> the concurrency issue of Pop() decrementing and PushRoutine()
> incrementing (and both stuffing in to the slice) without control. TBH
> both the other examples given by David and Steve are much cleaner
> altogether.

I wouldn't use a channel as a mutex other than as an exercise. I
didn't look at the other examples, but assuming you're running a select
over a few different channels to decide what to do and you're pushing
instructions into those channels, it gets really easy to think about,
and there's no locking that needs to occur as all the state is
manipulated on a single goroutine's context. When you do this, you
don't need locks.

--
dustin

[David DENG]

When you are more familiar with go-lang, you can also read Steve's implementation, which is more tricky, and a little bit more efficient. It uses the trick of nil channel in a select statement.

And for both approaches, add the following line before shrinking the stack(objs) slice, if the elements need gc:

s.stack[len(s.stack)-1] = nil // or some other zero value

Otherwise, a small memory leak, though not accumulative, occurs.

David

[Aiden]

On Wednesday, 9 January 2013 00:47:04 UTC, Dustin wrote:

Aiden <aide...@gmail.com> writes:


> Thanks for the feedback. As for the busy loop, I was using a pattern I
> saw elsewhere on the net where the select{} on the channel blocks
> waiting for a signal to wake the goroutine, stopping the busyness of
> the for{}, and the for{} exists only to never stop reading items from
> PushChan ... or am I mistaken there?

  That was a misread on my part.  select with just one channel does the
same thing as not using select.  When I see that code with only one
case, I assume there's a default (because I wouldn't expect you to do it
for any other reason).

  Should do roughly the same thing.

> Your range example does look clearer, I guess I didn't pick up that
> range polls until PushChan is closed and performs the for body on each
> item. They look equivalent to me?

  Not quite equivalent.  Yours didn't terminate on close (which *would*
make it a busy loop).

Good point, didn't quite catch that and see how it would become busy.
 

> The Lock was used in-place of a mutex (as per go blogs etc) to stop
> the concurrency issue of Pop() decrementing and PushRoutine()
> incrementing (and both stuffing in to the slice) without control.  TBH
> both the other examples given by David and Steve are much cleaner
> altogether.

  I wouldn't use a channel as a mutex other than as an exercise.  I
didn't look at the other examples, but assuming you're running a select
over a few different channels to decide what to do and you're pushing
instructions into those channels, it gets really easy to think about,
and there's no locking that needs to occur as all the state is
manipulated on a single goroutine's context.  When you do this, you
don't need locks.

Yea I think it was the concurrent access of the stack type by splitting
the access from a single select ... also a throwback from C threads :(
The multiple select as a form of control is much nicer and I see now
more idiomatic for Go. Nice pointers, thanks :)

--
dustin

[roger peppe]

Playing devil's advocate slightly, here's a version that doesn't use
channels at all. The zero value is OK to use without initialisation,
which is always a nice property if you can get it. It will also be
garbage collected correctly (most of the above examples also lack
tear-down code).

http://play.golang.org/p/0aExosRigH

It's harder to reason about though.

> --
>
>

[Aiden]

That's quite a nice example. I like it. My original was like a grim car crash between yours
and the other channel-based examples :)