Issue #14859 has been updated by funny_falcon (Yura Sokolov).


normalperson (Eric Wong) wrote:
>  Yes.  The "timeout scheduler" is the same idea I used for auto-fiber.
>  It uses ccan/list to manage a sorted list of timeouts.

Still wonder, why you don't use binary min-heap for timers - most commonly used datastructure for this task. 
It has guaranteed O(log n) performance for insertion/deletion, and O(1) for check for min, and has very simple implementation.
Note, that for insertion of new maximum value, binary min-heap also gives O(1) performance because item will not sift up. 


----------------------------------------
Feature #14859: [PATCH] implement Timeout in VM
https://bugs.ruby-lang.org/issues/14859#change-73055

* Author: normalperson (Eric Wong)
* Status: Open
* Priority: Normal
* Assignee: ko1 (Koichi Sasada)
* Target version: 
----------------------------------------
implement Timeout in VM

Based on the ugliness of handling partial writes with
IO#write_nonblock and inability to use writev(2) effectively
with write timeouts in Net::HTTP in r63587-r63589, I've
decided Timeout to be the more programmer-friendly option
to use and to improve it.

Timeout is significantly faster with this patch, and stopping
the timeout before expiration (common case) is optimized to be
as fast as possible.  This version relies on timer-thread to
provide wakeup interrupts.

This is a minimally intrusive patch.  I also started working on
a more intrusive patch to touch all sleep/waiting function
calls, but this is easier-to-review for now.  In the future,
I will try per-thread timeouts and eliminate timer-thread
for platforms with POSIX timers (timer_create/timer_settime)

Speedup ratio: compare with the result of `trunk' (greater is better)

timeout_mt_nested       3.887
timeout_mt_same         3.843
timeout_mt_ugly         1.335
timeout_nested          7.059
timeout_same            5.173
timeout_zero            2.587


---Files--------------------------------
0001-implement-Timeout-in-VM.patch (27.2 KB)


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

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>