[ruby-core:70844] [Ruby trunk - Feature #11518] Queue enhancement - promote! and promote_all!

Issue #11518 has been updated by Jonathan Cruz.


Yura Sokolov wrote:
> First: you forgot to lock queue. Multithreading will bite you.
>=20
> Second: if you want custom behaviour why don't you make custom structure?
> Till 2.0 Queue were implemented in ruby. If your tasks are heavy, then=20
> you won't notice difference.

First: You're right. My C skills are a bit rusty and I wasn't sure how to d=
o that. Then I think I just forgot about it before submitting this. I'll up=
date the patch, but if you could point me to an example of locking, it'll s=
ave me some time.

Second: That is exactly what we did. We recreated the Ruby implementation o=
f Queue in our project and then subclassed that to add #promote! and #promo=
te_all! methods (as well as the conditional version of #pop in https://bugs=
.ruby-lang.org/issues/11517). That works fine for our needs. However, this =
will eventaully cause us to become out of synch with the core Ruby version =
of Queue. We would rather not have to remember to update our implementation=
 of Queue every time we upgrade Ruby.
We can get by without this, but it would be nice to expose some limited met=
hods to change the order of the queue. Obviously, you cannot expose the und=
erlying array object and remain threadsafe, but as it is, that array is com=
pletely inaccessible even by child classes.

----------------------------------------
Feature #11518: Queue enhancement - promote! and promote_all!
https://bugs.ruby-lang.org/issues/11518#change-54218

* Author: Jonathan Cruz
* Status: Open
* Priority: Normal
* Assignee: Yukihiro Matsumoto
----------------------------------------
I=E2=80=99m submitting a patch to enhance the Queue class by adding the met=
hods Queue#promote! and Queue#promote_all!. These methods require a block t=
hat accepts queue elements. Elements for which the block returns a truthy v=
alue are moved to the =E2=80=98front=E2=80=99 of the queue.  Queue#promote!=
 only applies to the first such element and Queue#promote_all! applies to a=
ll matching elements (preserving their relative order).

Motivation for this enhancement: Our project has several worker threads wor=
king on long-running work units in a queue, trying to find a =E2=80=98match=
=E2=80=99.  The queue is pre-sorted with the most likely matches at the fro=
nt and least likely at the back. However, there are cases where as we work =
on some elements, we gain new data that certain elements are more likely to=
 match than we originally thought. We need a way to promote these elements =
to the front of the queue.

---Files--------------------------------
ruby_queue_promote.patch (2.82 KB)


--=20
https://bugs.ruby-lang.org/