From: "Eregon (Benoit Daloze) via ruby-core" Date: 2025-12-03T09:28:33+00:00 Subject: [ruby-core:123999] [Ruby Feature#21721] Allow `Queue` and `SizedQueue` to be used as LIFO queues Issue #21721 has been updated by Eregon (Benoit Daloze). I ran the benchmark on TruffleRuby to get an idea how much of that slowdown is due to a slow ConditionVariable & other things, the results are interesting: CRuby: ``` ruby 3.4.7 (2025-10-08 revision 7a5688e2a2) +YJIT +PRISM [x86_64-linux] Warming up -------------------------------------- core-queue 586.699k i/100ms ar-queue 191.693k i/100ms cp gem 98.616k i/100ms Calculating ------------------------------------- core-queue 5.776M (�� 0.5%) i/s (173.14 ns/i) - 29.335M in 5.079108s ar-queue 1.962M (�� 0.7%) i/s (509.74 ns/i) - 9.968M in 5.081312s cp gem 987.708k (�� 0.4%) i/s (1.01 ��s/i) - 5.029M in 5.092099s Comparison: core-queue: 5775785.1 i/s ar-queue: 1961797.2 i/s - 2.94x slower cp gem: 987707.6 i/s - 5.85x slower ``` TruffleRuby: ``` truffleruby 33.0.0-dev-bb226b84 (2025-12-01), like ruby 3.3.7, Oracle GraalVM JVM [x86_64-linux] Warming up -------------------------------------- core-queue 904.661k i/100ms ar-queue 1.099M i/100ms cp gem 263.200k i/100ms Calculating ------------------------------------- core-queue 9.039M (�� 0.4%) i/s (110.64 ns/i) - 45.233M in 5.004452s ar-queue 16.200M (�� 0.7%) i/s (61.73 ns/i) - 81.351M in 5.022020s cp gem 7.429M (�� 0.7%) i/s (134.61 ns/i) - 37.374M in 5.031286s Comparison: core-queue: 9038694.1 i/s ar-queue: 16199536.5 i/s - 1.79x faster cp gem: 7428815.5 i/s - 1.22x slower ``` Note that ar-queue is *faster* than core-queue here, while core-queue on TruffleRuby is faster than core-queue on CRuby. In fact `ar-queue` is 8.25x faster on TruffleRuby than CRuby, while Queue is just 1.55x faster, which I think indicates ConditionVariable and maybe Mutex (as well as how fast Ruby code is executed) have a lot of optimization potential on CRuby. Optimizing ConditionVariable & Mutex would not only benefit these gems but also all other usages of them, notably thread pools (including Puma's one), etc. Similar the `connection_pool` stack is 7.25x faster on TruffleRuby than CRuby, which I think is further indication of that. IOW, it seems to me like adding `Thread::Stack` would just be a band aid/workaround, the real issue here seems to be that ConditionVariable and Mutex are too slow on CRuby. ---------------------------------------- Feature #21721: Allow `Queue` and `SizedQueue` to be used as LIFO queues https://bugs.ruby-lang.org/issues/21721#change-115426 * Author: byroot (Jean Boussier) * Status: Open ---------------------------------------- ### Context Since `Queue` and `SizedQueue` gained a proper timeout mechanism, I've been wanting to use them to implement simpler and more efficient connection pools. However for connection pools you ideally want a LIFO queue because it's preferable to checkout the most recently used connection. ### Problem Both `Queue` and `SizedQueue` only support FIFO because you can only enqueue elements at the beginning of the backing array, and only dequeue at the end. `Queue#push` (aliased as `Queue#<<` and `Queue#enq`) calls `Array#unshift` on the backing array and `Queue#pop` (aliased as `Queue#deq` and `Queue#shift`) calls `Array#pop`. Hence it is impossible to use these two classes for anything other than FIFO queues. I tried to use `git blame` to see if there was a justification for this, but I ended up in a git blame loop around May 2000 https://github.com/ruby/ruby/commit/9da4f78db46764be6dae5e7e83ff48cbecb3fb23 ### Feature I'd like to introduce either of two new methods (or both) to allow for LIFO: - A method to dequeue from the beginning of the backing array (`array_shift`). - A method to enqueue from the end of the backing array (`array_push`). A difficulty I have however is that since the common `shift/pop/push` terms are already used with uncommon meaning, it's hard to come up with good names. Ideas welcome. ### Possible alternatives - Define different classes for LIFO queues - But I find that less flexible, and it means exposing new constant names in the global namespace. - Add an initializer argument to define the queue ordering, e.g. `Queue.new([], lifo: true)` - Similarly, I find this less flexible than to decide the order during enqueue/dequeue - Add an argument to `Queue#pop` and `Queue#push`, e.g. `queue.push(element, front: true)`. -- https://bugs.ruby-lang.org/ ______________________________________________ ruby-core mailing list -- ruby-core@ml.ruby-lang.org To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/