Feature #6293: new queue / blocking queues

• Status: Assigned
• Assignee: matz (Yukihiro Matsumoto)
• Target version: -

[tenderlovemaking (Aaron Patterson)]

Hi,

I'd like to add new Queue objects to ruby. Whenever I use queues, I either use them in a blocking or non-blocking manner only, so I have separated them in to two classes Thread::Queue, and Thread::BlockingQueue.

Other notable differences, these queues:

• implement poll, which will return a nil if the queue is empty
• do not allow nil to be in the queue as it would interfere with poll
• include Enumerable

I think these will be a good basis for implementing a Deque, SynchronizedQueue, and PriorityQueue.

I've attached a patch against trunk.

[normalperson (Eric Wong)]

"tenderlovemaking (Aaron Patterson)" [e-mail] wrote:

Whenever I use queues, I either use them in a blocking or non-blocking
manner only, so I have separated them in to two classes Thread::Queue,
and Thread::BlockingQueue.

I don't think queues should be limited to strictly
blocking/non-blocking.

Outside of Ruby, but I've occassionally needed queues that could
toggle between blocking/non-blocking (even in the same thread)
to enforce some sort of fairness. Something like:

while task = queue.take
while task.run_one_timeslice

   if pending_task = queue.trytake # non-blocking

     # reschedule task if another task shows up
     queue.push(task)
     task = pending_task
   end

 end

end

Also, I very often use queues (often Unix pipes) where one end is
blocking and the other end is not (though you don't implement
non-blocking push at all)

[mame (Yusuke Endoh)]

• Status changed from Open to Assigned
• Assignee set to matz (Yukihiro Matsumoto)

Hello,

2012/4/14 tenderlovemaking (Aaron Patterson) [e-mail]:

I'd like to add new Queue objects to ruby.

I bet matz does not accept it because there is no good reason.
Why don't you extend the traditional Queue class?

• include Enumerable

The semantics is not trivial. See the discussion in #4589.

--
Yusuke Endoh [e-mail]

• File noname noname added

On Sat, Apr 14, 2012 at 10:23:56AM +0900, Eric Wong wrote:

"tenderlovemaking (Aaron Patterson)" [e-mail] wrote:

Whenever I use queues, I either use them in a blocking or non-blocking
manner only, so I have separated them in to two classes Thread::Queue,
and Thread::BlockingQueue.

I don't think queues should be limited to strictly
blocking/non-blocking.

Outside of Ruby, but I've occassionally needed queues that could
toggle between blocking/non-blocking (even in the same thread)
to enforce some sort of fairness. Something like:

while task = queue.take
while task.run_one_timeslice

  if pending_task = queue.trytake # non-blocking

    # reschedule task if another task shows up
    queue.push(task)
    task = pending_task
  end

end

end

The patch I submitted includes a method poll which will not block if a
timeout isn't supplied. In your case, I would rewrite as:

 queue = Thread::BlockingQueue.new

 while task = queue.shift
   while task.run_one_timeslice
 
     if pending_task = queue.poll # non-blocking
 
       # reschedule task if another task shows up
       queue.push(task)
       task = pending_task
     end
 
   end
 end

Also, I very often use queues (often Unix pipes) where one end is
blocking and the other end is not (though you don't implement
non-blocking push at all)

Both of these queues should have non-blocking push since neither is
bounded. If this patch is applied, I'll add sized queues which can
block. :-)

--
Aaron Patterson
http://tenderlovemaking.com/

• File noname noname added

On Sat, Apr 14, 2012 at 10:58:12AM +0900, mame (Yusuke Endoh) wrote:

Issue #6293 has been updated by mame (Yusuke Endoh).

Status changed from Open to Assigned
Assignee set to matz (Yukihiro Matsumoto)

Hello,

2012/4/14 tenderlovemaking (Aaron Patterson) [e-mail]:

I'd like to add new Queue objects to ruby.

I bet matz does not accept it because there is no good reason.
Why don't you extend the traditional Queue class?

I could, but I think the changes I want would add too much complexity
to the traditional Queue class. We have to add branching code for every
method that could block / not-block. Not to mention users must pass the
magical true | false to indicate if they want blocking or non-blocking
behavior. For example:

queue.pop(true) # does "true" mean I enable blocking?
queue.pop(false) # does "false" mean I disable blocking?

It seems confusing to me, especially given the actual api with twists
your brain with a double negative (from thread.rb):

def pop(non_block=false)
...
end

So calling pop() means we're doing a not not blocking call. :(

• include Enumerable

The semantics is not trivial. See the discussion in #4589.

I've read #4589. I don't think it's that much of a problem. Other
languages[1] include enumerable type behavior in their queues, and
consistency is not guaranteed.

1. http://docs.oracle.com/javase/6/docs/api/java/util/Queue.html#methods_inherited_from_class_java.util.Collection

--
Aaron Patterson
http://tenderlovemaking.com/

[ko1 (Koichi Sasada)]

Hi,

Just an idea.

(2012/04/14 11:25), Aaron Patterson wrote:

I could, but I think the changes I want would add too much
complexity to the traditional Queue class. We have to add
branching code for every method that could block / not-block. Not
to mention users must pass the magical true | false to indicate if
they want blocking or non-blocking behavior. For example:

queue.pop(true) # does "true" mean I enable blocking?
queue.pop(false) # does "false" mean I disable blocking?

It seems confusing to me, especially given the actual api with
twists your brain with a double negative (from thread.rb):

def pop(non_block=false) ... end

So calling pop() means we're doing a not not blocking call. :(

How about to add try_pop?

• include Enumerable

The semantics is not trivial. See the discussion in #4589.

I've read #4589. I don't think it's that much of a problem.
Other languages[1] include enumerable type behavior in their
queues, and consistency is not guaranteed.

http://docs.oracle.com/javase/6/docs/api/java/util/Queue.html#methods_inherited_from_class_java.util.Collection

How

about to implement Queue#to_a method that generate array which
contains queues containing objects?

I agree the name Thread::Queue because it is clear

that this object should be for synchronization.

Simple Queue class is ambiguous that we can use it

for synchronization or not. However, in the Ruby world,

::Queue is familiar as a data for synchronization.

--
// SASADA Koichi at atdot dot net

• File noname noname added

On Mon, Apr 16, 2012 at 06:25:59PM +0900, SASADA Koichi wrote:

Hi,

Just an idea.

(2012/04/14 11:25), Aaron Patterson wrote:

I could, but I think the changes I want would add too much
complexity to the traditional Queue class. We have to add
branching code for every method that could block / not-block. Not
to mention users must pass the magical true | false to indicate if
they want blocking or non-blocking behavior. For example:

queue.pop(true) # does "true" mean I enable blocking?
queue.pop(false) # does "false" mean I disable blocking?

It seems confusing to me, especially given the actual api with
twists your brain with a double negative (from thread.rb):

def pop(non_block=false) ... end

So calling pop() means we're doing a not not blocking call. :(

How about to add try_pop?

try_pop seems fine, but it still seems strange to combine blocking and
non-blocking queues (but maybe I am the one who is strange).

In the case of BlockingQueue#pop in the patch I submitted, it allows a
timeout. I don't think it's a feature that should be abandoned.

• include Enumerable

The semantics is not trivial. See the discussion in #4589.

I've read #4589. I don't think it's that much of a problem.
Other languages[1] include enumerable type behavior in their
queues, and consistency is not guaranteed.

http://docs.oracle.com/javase/6/docs/api/java/util/Queue.html#methods_inherited_from_class_java.util.Collection

How

about to implement Queue#to_a method that generate array which
contains queues containing objects?

That seems fine! Then we can eliminate Enumerable mixed in. :-)

I agree the name Thread::Queue because it is clear

that this object should be for synchronization.

Simple Queue class is ambiguous that we can use it

for synchronization or not. However, in the Ruby world,

::Queue is familiar as a data for synchronization.

Yes. I think keeping ::Queue is good. I think ::Queue can be
implemented in terms of Thread::BlockingQueue. I would have refactored
::Queue to be a subclass of Thread::BlockingQueue, but I didn't want my
patch to be ignored because the diff size. :-)

--
Aaron Patterson
http://tenderlovemaking.com/

[ko1 (Koichi Sasada)]

Hi,

(2012/04/17 0:24), Aaron Patterson wrote:

So calling pop() means we're doing a not not blocking call. :(

How about to add try_pop?

try_pop seems fine, but it still seems strange to combine blocking
and non-blocking queues (but maybe I am the one who is strange).

In the case of BlockingQueue#pop in the patch I submitted, it
allows a timeout. I don't think it's a feature that should be
abandoned.

I understand that ::Queue#pop should receive timeout extra parameter.

However, I'm not sure we need to separate (Blocking|Unblocking)Queue yet.

How

about to implement Queue#to_a method that generate array which
contains queues containing objects?

That seems fine! Then we can eliminate Enumerable mixed in. :-)

Yes. And it is clear semantics.

::Queue#each can be implemented on at least two semantics:

1. block the end of queue. (like IO)
2. return when reach end of queue. (like Array)

Against IO, Queue#each with semantics (1) can't stop. It is similar
to the cycle object (generated by Enumerator#cycle).

--
// SASADA Koichi at atdot dot net

[cout (Paul Brannan)]

On Mon, 2012-04-16 at 18:25 +0900, SASADA Koichi wrote:

How about to add try_pop?

I like it! It's consistent with Mutex.

Paul

• File queue.patch queue.patch added
• File noname noname added

On Thu, Apr 19, 2012 at 03:20:50PM +0900, SASADA Koichi wrote:

Hi,

(2012/04/17 0:24), Aaron Patterson wrote:

So calling pop() means we're doing a not not blocking call. :(

How about to add try_pop?

try_pop seems fine, but it still seems strange to combine blocking
and non-blocking queues (but maybe I am the one who is strange).

In the case of BlockingQueue#pop in the patch I submitted, it
allows a timeout. I don't think it's a feature that should be
abandoned.

I understand that ::Queue#pop should receive timeout extra parameter.

So the interface would be:

queue.pop(true, 10)

or

queue.pop(false, 10)

It seems confusing. I do not think it is as clear as:

queue = BlockingQueue.new
queue.pop 10

I'm not sure the clarity of ::Queue API really matters though. The
queues I've submitted do not allow nil. In this way, we can have
non-blocking reads that do not throw exceptions.

I think the queues I've submitted have different (but better) semantics.

However, I'm not sure we need to separate (Blocking|Unblocking)Queue yet.

I would like them so that I can change queue types without changing the
code that pops off the queue. I simply change the queue I instantiate,
and the rest of my code should not have to change.

How

about to implement Queue#to_a method that generate array which
contains queues containing objects?

That seems fine! Then we can eliminate Enumerable mixed in. :-)

Yes. And it is clear semantics.

::Queue#each can be implemented on at least two semantics:

1. block the end of queue. (like IO)
2. return when reach end of queue. (like Array)

Against IO, Queue#each with semantics (1) can't stop. It is similar
to the cycle object (generated by Enumerator#cycle).

I agree. I've attached an updated patch that uses to_a and removes Enumerable.

--
Aaron Patterson
http://tenderlovemaking.com/

[mame (Yusuke Endoh)]

• Target version set to 2.6

[naruse (Yui NARUSE)]

• Target version deleted (2.6)