built in support for a FIFO queue?

[karl.m...@gmail.com]

I am writing a program where I have a long running process and the main data structures will be a FIFO queue.    Whats a good way to implement a queue?  

Slice is a first class container in go.  I have found multiple user groups suggesting ways to make slice to emulate a queue. 

Dequeue

x, a = a[len(a)-1], a[:len(a)-1]

Enqueue

a = append(a, x)

The dequeue implementation makes me very nervous.  The program is long running and millions of push/pops are expected.  Randomly,  the queue may get very long or it may get dequeue to len 0, over and over.  If a slice is backed by a classic contiguous array, wont the unused front of the array left by the dequeue memory leak?    The memory management of the append does not to lend its self to a long running queue either.   Wont it just get more and more costly each time the backing array needs a resize?

Second choice is a channel.  I could just use the channel as a queue and push and pop as needed using the channel operators.   But a channel does a lot of extra behavior.   Perhaps it is too heavy weight to be used as a mere FIFO queue?

The third option seems to be list from the container package.  Sadly list does not support range and requires explicit type casts to extract the data value.   Maybe in a future version of go, custom classes could support a Rangeable interface and generics?  Is that ever likely to happen?  

Fourth option was roll my own.   Make an interface ListNode that requires Enqueue and Dequeue functions.  But go does not have a nice generics support.   So the ListNode interface may need to be implemented several times if I ever want more then queue of types.   So clumsy again. 

Anyway....

I am leaning towards just using the channel.  But I am still very new to go so wanted to see what the trade offs were. 

[Ian Lance Taylor]

On Mon, Feb 16, 2015 at 6:31 AM, <karl.m...@gmail.com> wrote:
>
> I am writing a program where I have a long running process and the main data
> structures will be a FIFO queue. Whats a good way to implement a queue?
>
> Slice is a first class container in go. I have found multiple user groups
> suggesting ways to make slice to emulate a queue.
> Dequeue
> x, a = a[len(a)-1], a[:len(a)-1]
>
> Enqueue
> a = append(a, x)
>
> The dequeue implementation makes me very nervous. The program is long
> running and millions of push/pops are expected. Randomly, the queue may
> get very long or it may get dequeue to len 0, over and over. If a slice is
> backed by a classic contiguous array, wont the unused front of the array
> left by the dequeue memory leak? The memory management of the append does
> not to lend its self to a long running queue either. Wont it just get more
> and more costly each time the backing array needs a resize?

Not really. The append function will allocate a new backing array
based on the current size of the slice itself, not the size of the
backing array of the slice. If you do something like this:
a = make([]int, 5)
a = a[4:]
a = append(a, 1, 2)
the append function will have to allocate a new backing array, because
there is no more room in the original one, and it will allocate a new
array of size 3 (plus some room to grow after those 3 elements).

> Second choice is a channel. I could just use the channel as a queue and
> push and pop as needed using the channel operators. But a channel does a
> lot of extra behavior. Perhaps it is too heavy weight to be used as a mere
> FIFO queue?

Channels are fairly lightweight, and they work nicely for a fixed-size
FIFO queue, provided values are pushed and popped by different
goroutines. It doesn't work to have one goroutine push a value on and
then pop it off later, because if the queue gets full the goroutine
will deadlock. Also, of course, you must set the size of the channel
buffer when you create the channel; there is no easy way to
dynamically adjust the queue size as the program executes.

Ian

[Carlos Castillo]

The code you have written implements a stack, since you are reading and writing at the end.

Dequeue should be:

x, a := a[0], a[1:]

Then items are read at the front of the slice. 

As Ian said, your x slice will start with the next object to be read, when you append, only those objects to the end of the slice will be copied to the new slice when append does the resize. If the queue stays small, you will only have ever have a small slice.

eg:

ENQ 1,2,3,4 => [1,2,3,4,_,_,_] // _s are unused between len and cap of slice

DEQ 2 items => [3,4,_,_,_] // memory used by first two will be held until slice is resized

ENQ 5,6,7,8 => [3,4,5,6,7,8, _, _, _] // new backing array is allocated by append, and only 3,4 are copied over, old slice with 1,2 is now garbage

There may be situations where the dequed elements are still "held" in memory until the append happens, but you can just zero out the element in the slice before reslicing to allow the objects to be collected:

Dequeue:

x := a[0]

a[0] = nil

a = a[1:]

[Egon]

On Monday, 16 February 2015 16:31:11 UTC+2, karl.m...@gmail.com wrote:

I am writing a program where I have a long running process and the main data structures will be a FIFO queue.    Whats a good way to implement a queue?  

Slice is a first class container in go.  I have found multiple user groups suggesting ways to make slice to emulate a queue. 

Dequeue

x, a = a[len(a)-1], a[:len(a)-1]

Enqueue

a = append(a, x)

The dequeue implementation makes me very nervous.  The program is long running and millions of push/pops are expected.  Randomly,  the queue may get very long or it may get dequeue to len 0, over and over.  If a slice is backed by a classic contiguous array, wont the unused front of the array left by the dequeue memory leak?    The memory management of the append does not to lend its self to a long running queue either.   Wont it just get more and more costly each time the backing array needs a resize?

At some point I experimented and benched different fifo/lifo implementations and 

https://github.com/karalabe/cookiejar/tree/master/collections

were the fastest...  I expect nothing hasn't changed since then. (PS. you might get some extra boost by replacing []interface{} with your own type).

Of course depending what you are doing a disruptor might also be an option (https://github.com/smartystreets/go-disruptor)

And you might get even get more out of a custom built data-structure.

So... what exactly are you doing?

+ Egon

[Edward Muller]

Why not use a channel? They are bounded fifos. Unbounded queues are bad if you care about RAM and at enough scale you always do.

--
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.
For more options, visit https://groups.google.com/d/optout.

--
Edward Muller
@freeformz

[jasdel]

Read/Writing a channel from within the same go routine would cause a dead lock soon as the channel's buffer was filled. In multi go routine environment the writer would block if the channel was buffer was full. The reader would also if the channel was empty without a select statement wrapping the read.

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.

--
Edward Muller
@freeformz

[agro...@digitalocean.com]

FWIW, this tool can generate an efficient FIFO queue for you:

https://github.com/aybabtme/datagen

It's unbounded and not thread safe, but well tested and pretty fast. If the things you enqueue need to survive a crash, I'd suggest you use an external persistent queue.

[Edward Muller]

On Wed, Feb 18, 2015 at 2:53 PM, jasdel <delp...@gmail.com> wrote:

Read/Writing a channel from within the same go routine would cause a dead lock soon as the channel's buffer was filled. In multi go routine environment the writer would block if the channel was buffer was full. The reader would also if the channel was empty without a select statement wrapping the read.

Yes. I am aware of all of that. Ian also pointed it out earlier in the thread.  I still don't think that answers the question though of why not use a channel. Maybe I'm just too used to CSP at this point. Make one or more producing goroutines pushing stuff into the channel. Make one or more consuming go routines pulling stuff off. Let the runtime do the needful.

Anyway. Karl can and should do whatever suites him best.

 

On Tuesday, February 17, 2015 at 8:30:23 PM UTC-8, freeformz wrote:

Why not use a channel? They are bounded fifos. Unbounded queues are bad if you care about RAM and at enough scale you always do.

On Monday, February 16, 2015, <karl.m...@gmail.com> wrote:

I am writing a program where I have a long running process and the main data structures will be a FIFO queue.    Whats a good way to implement a queue?  

Slice is a first class container in go.  I have found multiple user groups suggesting ways to make slice to emulate a queue. 

Dequeue

x, a = a[len(a)-1], a[:len(a)-1]

Enqueue

a = append(a, x)

The dequeue implementation makes me very nervous.  The program is long running and millions of push/pops are expected.  Randomly,  the queue may get very long or it may get dequeue to len 0, over and over.  If a slice is backed by a classic contiguous array, wont the unused front of the array left by the dequeue memory leak?    The memory management of the append does not to lend its self to a long running queue either.   Wont it just get more and more costly each time the backing array needs a resize?

Second choice is a channel.  I could just use the channel as a queue and push and pop as needed using the channel operators.   But a channel does a lot of extra behavior.   Perhaps it is too heavy weight to be used as a mere FIFO queue?

The third option seems to be list from the container package.  Sadly list does not support range and requires explicit type casts to extract the data value.   Maybe in a future version of go, custom classes could support a Rangeable interface and generics?  Is that ever likely to happen?  

Fourth option was roll my own.   Make an interface ListNode that requires Enqueue and Dequeue functions.  But go does not have a nice generics support.   So the ListNode interface may need to be implemented several times if I ever want more then queue of types.   So clumsy again. 

Anyway....

I am leaning towards just using the channel.  But I am still very new to go so wanted to see what the trade offs were. 

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

--
Edward Muller
@freeformz

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

For more options, visit https://groups.google.com/d/optout.

--

Edward Muller
@freeformz

[karl.m...@gmail.com]

Guys, thank you for the excellent information. 

So the dequeue operator  creates a new slice with a head pointer, the old would be discarded with a manual nil if it was a slice of structs

x := a[0]

a[0] = nil  // discard reference in array

a = a[1:]  // advance head

and then the enqueue can be implemented with append

a = append(a, x)   // may resize, and may discard old backing array

As long as you are confident the queue length stays reasonably small, slice, seems to make sense for many cases.  If the queue tended to grow long, very often, it might not scale.     

The reason I originally asked the question, I was working on   the Go Tutorial Web Crawler exercise.   https://tour.golang.org/concurrency/9

and for my implementation, chose to solve it with worker pool of go routines with a dispatcher that had a queue of unique url that were pending.   The dispatcher also maintained the global visited url map. 

For the tutorial using the slice to implement it would would have been fine of course.

But I wanted to think about what a production system might look like so I pretended that queue lengths could hit millions on a regular basis.     I wound up using the concurrency/list package. 

Even without language supported generics I was very pleased that the library container turned out to be concise and easy to use.   I wound up making a struct that would describe each pending url.   so...

pending := list.New()   // allocate the list at start

then my dispatcher polled the worker go routines response channel for discovered url.   The dispatcher would keep a global visited list and then enqueue novel url that were discovered 

....

pending.PushBack( 

       PendingRequest{

          worker.PendingRequest.Depth+1,

           url })

and then if there was an idle worker  the dispatacher would dequeue the next request

request := pending.Remove(pending.Front()).(PendingRequest)

so overall the list container was easy to use and would likely have been sufficiently performant in production. 

Thanks for the info guys.