https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112018-06-21T01:42:47ZRuby Issue Tracking SystemRuby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725472018-06-21T01:42:47Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><blockquote>
<p><a href="https://bugs.ruby-lang.org/issues/14859" class="external">https://bugs.ruby-lang.org/issues/14859</a></p>
</blockquote>
<p>I sometimes get failures in test_condvar_wait_deadlock_2 of<br>
test/thread/test_cv.rb with this, but I think that test is too<br>
dependent on thread scheduling timing...</p>
<p>In other words, I'm not sure it's a good test...</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725492018-06-21T02:04:06Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><blockquote>
<blockquote>
<p><a href="https://bugs.ruby-lang.org/issues/14859" class="external">https://bugs.ruby-lang.org/issues/14859</a></p>
</blockquote>
<p>I sometimes get failures in test_condvar_wait_deadlock_2 of<br>
test/thread/test_cv.rb with this, but I think that test is too<br>
dependent on thread scheduling timing...</p>
</blockquote>
<p>Disregard, will fix...</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725762018-06-21T11:30:12ZEregon (Benoit Daloze)
<ul></ul><p>Should lib/timeout.rb be removed then?<br>
Why is it moved to core, could it stay an extension?</p>
<p>Note that there are pure-Ruby implementations of Timeout using a single Ruby Thread, like<br>
<a href="https://github.com/oracle/truffleruby/blob/71df1ecc4fd9e318b5bd3998cfaeb85a96de7a8b/lib/truffle/timeout.rb" class="external">https://github.com/oracle/truffleruby/blob/71df1ecc4fd9e318b5bd3998cfaeb85a96de7a8b/lib/truffle/timeout.rb</a> (originally from Rubinius)</p>
<p>and that WEBrick has basically its own version of Timeout, using a single Thread:<br>
<a href="https://github.com/ruby/ruby/blob/48efa44719d03eb067d27b30c68cf821074aedce/lib/webrick/utils.rb" class="external">https://github.com/ruby/ruby/blob/48efa44719d03eb067d27b30c68cf821074aedce/lib/webrick/utils.rb</a></p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725772018-06-21T11:41:41ZEregon (Benoit Daloze)
<ul></ul><p>Something else, I would consider Timeout to be fundamentally flawed as long as it relies on Thread#raise,<br>
because it can fire in the middle of an ensure block:<br>
<a href="http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html" class="external">http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html</a></p>
<p>Maybe IO#write and such should directly accept a timeout argument and other changes to make the API easier to use?</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725872018-06-21T20:12:55Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p><a href="mailto:eregontp@gmail.com" class="email">eregontp@gmail.com</a> wrote:</p>
<blockquote>
<p>Should lib/timeout.rb be removed then?</p>
</blockquote>
<p>Yes, and the rdoc will be moved if accepted.</p>
<blockquote>
<p>Why is it moved to core, could it stay an extension?</p>
</blockquote>
<p>Right now it needs to hook into the core timer thread without<br>
needing additional threads. I already run into resource<br>
exhaustion problems with timer-thread when testing.</p>
<p>I'm working on making all wait functions aware of it:<br>
rb_wait_for_single_fd, rb_thread_fd_select, rb_thread_sleep*, etc.</p>
<p>Eventually, I also want to get rid of timer thread (for POSIX)<br>
but it might not be easy</p>
<blockquote>
<p>Note that there are pure-Ruby implementations of Timeout using a single Ruby Thread, like<br>
<a href="https://github.com/oracle/truffleruby/blob/71df1ecc4fd9e318b5bd3998cfaeb85a96de7a8b/lib/truffle/timeout.rb" class="external">https://github.com/oracle/truffleruby/blob/71df1ecc4fd9e318b5bd3998cfaeb85a96de7a8b/lib/truffle/timeout.rb</a> (originally from Rubinius)</p>
</blockquote>
<p>Using one extra Thread is already too much for me.</p>
<blockquote>
<p>and that WEBrick has basically its own version of Timeout, using a single Thread:<br>
<a href="https://github.com/ruby/ruby/blob/48efa44719d03eb067d27b30c68cf821074aedce/lib/webrick/utils.rb" class="external">https://github.com/ruby/ruby/blob/48efa44719d03eb067d27b30c68cf821074aedce/lib/webrick/utils.rb</a></p>
</blockquote>
<p>Yes, I want to get rid of that by making Timeout better.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725882018-06-21T20:12:55Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p><a href="mailto:eregontp@gmail.com" class="email">eregontp@gmail.com</a> wrote:</p>
<blockquote>
<p>Something else, I would consider Timeout to be fundamentally<br>
flawed as long as it relies on Thread#raise, because it can<br>
fire in the middle of an ensure block:<br>
<a href="http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html" class="external">http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html</a></p>
</blockquote>
<p>We have Thread.handle_interrupt, nowadays, to control when<br>
interrupts fire.</p>
<blockquote>
<p>Maybe IO#write_nonblock and such should directly accept a<br>
timeout argument and other changes to make the API easier to<br>
use?</p>
</blockquote>
<p>I considered that, too, but we'd need to add timeouts to every<br>
single method which can block. There are many: File.open, Queue#pop,<br>
SizedQueue#push, Mutex#lock/synchronize, Process.wait*,<br>
IO#gets, IO#write, IO#read, IO#getc, IO.copy_stream, ...</p>
<p>Pretty much every IO method needs to be changed and callers<br>
need to be rewritten.</p>
<p>Things like File.open and Process.wait* don't have timeouts<br>
in the underlying syscall, so we'd still have to use a timer<br>
thread or POSIX timers to interrupt them on timeout.</p>
<p>The goal is to make all those methods aware of Timeout<br>
without changing existing user code at all.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725922018-06-22T00:42:32Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p><a href="mailto:eregontp@gmail.com" class="email">eregontp@gmail.com</a> wrote:</p>
<blockquote>
<p>Should lib/timeout.rb be removed then?</p>
</blockquote>
<p>Also, I might keep compatibility code in timeout.rb and stop<br>
providing it. This avoids bloating the VM with deprecated<br>
stuff without breaking backwards compatibility.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=725932018-06-22T01:04:24Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><blockquote>
<p>stop providing it.</p>
</blockquote>
<p>I meant: stop using rb_provide("timeout.rb")</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=726112018-06-22T10:20:57ZEregon (Benoit Daloze)
<ul></ul><p>normalperson (Eric Wong) wrote:</p>
<blockquote>
<p><a href="mailto:eregontp@gmail.com" class="email">eregontp@gmail.com</a> wrote:</p>
<blockquote>
<p>Something else, I would consider Timeout to be fundamentally<br>
flawed as long as it relies on Thread#raise, because it can<br>
fire in the middle of an ensure block:<br>
<a href="http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html" class="external">http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html</a></p>
</blockquote>
<p>We have Thread.handle_interrupt, nowadays, to control when<br>
interrupts fire.</p>
</blockquote>
<p>Right, although it's very difficult to use correctly (for instance, it's incorrect to use Thread.handle_interrupt inside the ensure block) and can easily cause hangs or deadlocks.</p>
<p>BTW, it looks like MonitorMixin::ConditionVariable doesn't use Thread.handle_interrupt and could continue out of #wait (with an exception thrown by Thread#raise) without reacquiring the lock.</p>
<p>It might be nice to have a Timeout variant that only interrupts blocking IO, without relying on Thread#raise (but just SIGVTALRM).<br>
I think that would be easier/safer to use than the current Timeout.timeout().<br>
Not sure how to deal if there are multiple IO calls inside that Timeout block though.<br>
And there could still be blocking IO in an ensure block, which would not work as intended.</p>
<blockquote>
<p>I considered that, too, but we'd need to add timeouts to every<br>
single method which can block. There are many: File.open, Queue#pop,<br>
SizedQueue#push, Mutex#lock/synchronize, Process.wait*,<br>
IO#gets, IO#write, IO#read, IO#getc, IO.copy_stream, ...</p>
</blockquote>
<p>It seems fine to me. Other implementations already have a timeout on Queue#pop IIRC.<br>
I'm not sure we need all of them right now (what use case for Mutex#lock/synchronize ?).<br>
I think the main need would be for standard IO like IO#read/write, especially on sockets and pipes.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=726122018-06-22T22:12:48Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p><a href="mailto:eregontp@gmail.com" class="email">eregontp@gmail.com</a> wrote:</p>
<blockquote>
<p>normalperson (Eric Wong) wrote:</p>
<blockquote>
<p><a href="mailto:eregontp@gmail.com" class="email">eregontp@gmail.com</a> wrote:</p>
<blockquote>
<p>Something else, I would consider Timeout to be fundamentally<br>
flawed as long as it relies on Thread#raise, because it can<br>
fire in the middle of an ensure block:<br>
<a href="http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html" class="external">http://headius.blogspot.com/2008/02/rubys-threadraise-threadkill-timeoutrb.html</a></p>
</blockquote>
<p>We have Thread.handle_interrupt, nowadays, to control when<br>
interrupts fire.</p>
</blockquote>
</blockquote>
<blockquote>
<p>Right, although it's very difficult to use correctly (for<br>
instance, it's incorrect to use Thread.handle_interrupt inside<br>
the ensure block) and can easily cause hangs or deadlocks.</p>
</blockquote>
<p>Agreed, it should be easier-to-use; but that's a separate issue<br>
and I'm trying to avoid dealing with public API design as much<br>
as possible for this.</p>
<blockquote>
<p>BTW, it looks like MonitorMixin::ConditionVariable doesn't use<br>
Thread.handle_interrupt and could continue out of #wait (with<br>
an exception thrown by Thread#raise) without reacquiring the<br>
lock.</p>
</blockquote>
<p>Can you report separately to shugo to be sure he sees it?<br>
I've never really understood the point of that module :x</p>
<blockquote>
<p>It might be nice to have a Timeout variant that only<br>
interrupts blocking IO, without relying on Thread#raise (but<br>
just SIGVTALRM). I think that would be easier/safer to use<br>
than the current Timeout.timeout(). Not sure how to deal if<br>
there are multiple IO calls inside that Timeout block though.<br>
And there could still be blocking IO in an ensure block, which<br>
would not work as intended.</p>
</blockquote>
<p>Agreed, I would welcome a "soft" timeout, without using<br>
signals/raise at all. I think my work-in-progress "intrusive"<br>
[PATCH 2/1] for this will make such a thing easier-to-implement:</p>
<p><a href="https://80x24.org/spew/20180622215745.20698-1-e@80x24.org/raw" class="external">https://80x24.org/spew/20180622215745.20698-1-e@80x24.org/raw</a></p>
<blockquote>
<blockquote>
<p>I considered that, too, but we'd need to add timeouts to<br>
every<br>
single method which can block. There are many: File.open,<br>
Queue#pop, SizedQueue#push, Mutex#lock/synchronize,<br>
Process.wait*, IO#gets, IO#write, IO#read, IO#getc,<br>
IO.copy_stream, ...</p>
</blockquote>
<p>It seems fine to me. Other implementations already have a<br>
timeout on Queue#pop IIRC. I'm not sure we need all of them<br>
right now (what use case for Mutex#lock/synchronize ?). I<br>
think the main need would be for standard IO like<br>
IO#read/write, especially on sockets and pipes.</p>
</blockquote>
<p>The maintenance overhead for adding timeouts to every call would<br>
be overwhelming on a human level, especially when 3rd-party<br>
libraries need to be considered.</p>
<p>I would much rather do the following:</p>
<pre><code class="ruby syntaxhl" data-language="ruby"> <span class="no">Timeout</span><span class="p">.</span><span class="nf">timeout</span><span class="p">(</span><span class="mi">30</span><span class="p">)</span> <span class="k">do</span>
<span class="n">foo</span><span class="p">.</span><span class="nf">read</span><span class="p">(</span><span class="o">...</span><span class="p">)</span>
<span class="n">foo</span><span class="p">.</span><span class="nf">write</span><span class="p">(</span><span class="o">...</span><span class="p">)</span>
<span class="no">IO</span><span class="p">.</span><span class="nf">copy_stream</span><span class="p">(</span><span class="o">...</span><span class="p">)</span>
<span class="n">foo</span><span class="p">.</span><span class="nf">write</span><span class="p">(</span><span class="o">...</span><span class="p">)</span>
<span class="n">szqueue</span><span class="p">.</span><span class="nf">push</span><span class="p">(</span><span class="o">...</span><span class="p">)</span>
<span class="n">resultq</span><span class="p">.</span><span class="nf">pop</span>
<span class="k">end</span>
</code></pre>
<p>Than this:</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="k">def</span> <span class="nf">now</span>
<span class="no">Process</span><span class="p">.</span><span class="nf">clock_gettime</span><span class="p">(</span><span class="no">Process</span><span class="o">::</span><span class="no">CLOCK_MONOTONIC</span><span class="p">)</span>
<span class="k">end</span>
<span class="k">begin</span>
<span class="vi">@stop</span> <span class="o">=</span> <span class="n">now</span> <span class="o">+</span> <span class="mi">30</span>
<span class="o">...</span>
<span class="n">tout</span> <span class="o">=</span> <span class="vi">@stop</span> <span class="o">-</span> <span class="n">now</span>
<span class="k">raise</span> <span class="no">Timeout</span><span class="o">::</span><span class="no">Error</span> <span class="k">if</span> <span class="n">tout</span> <span class="o"><=</span> <span class="mi">0</span>
<span class="n">foo</span><span class="p">.</span><span class="nf">read</span><span class="p">(</span><span class="o">...</span><span class="p">,</span> <span class="n">tout</span><span class="p">)</span>
<span class="n">tout</span> <span class="o">=</span> <span class="vi">@stop</span> <span class="o">-</span> <span class="n">now</span>
<span class="k">raise</span> <span class="no">Timeout</span><span class="o">::</span><span class="no">Error</span> <span class="k">if</span> <span class="n">tout</span> <span class="o"><=</span> <span class="mi">0</span>
<span class="n">foo</span><span class="p">.</span><span class="nf">write</span><span class="p">(</span><span class="o">...</span><span class="p">,</span> <span class="n">tout</span><span class="p">)</span>
<span class="n">tout</span> <span class="o">=</span> <span class="vi">@stop</span> <span class="o">-</span> <span class="n">now</span>
<span class="k">raise</span> <span class="no">Timeout</span><span class="o">::</span><span class="no">Error</span> <span class="k">if</span> <span class="n">tout</span> <span class="o"><=</span> <span class="mi">0</span>
<span class="no">IO</span><span class="p">.</span><span class="nf">copy_stream</span><span class="p">(</span><span class="o">...</span><span class="p">,</span> <span class="n">tout</span><span class="p">)</span>
<span class="n">tout</span> <span class="o">=</span> <span class="vi">@stop</span> <span class="o">-</span> <span class="n">now</span>
<span class="k">raise</span> <span class="no">Timeout</span><span class="o">::</span><span class="no">Error</span> <span class="k">if</span> <span class="n">tout</span> <span class="o"><=</span> <span class="mi">0</span>
<span class="n">foo</span><span class="p">.</span><span class="nf">write</span><span class="p">(</span><span class="o">...</span><span class="p">,</span> <span class="n">tout</span><span class="p">)</span>
<span class="n">tout</span> <span class="o">=</span> <span class="vi">@stop</span> <span class="o">-</span> <span class="n">now</span>
<span class="k">raise</span> <span class="no">Timeout</span><span class="o">::</span><span class="no">Error</span> <span class="k">if</span> <span class="n">tout</span> <span class="o"><=</span> <span class="mi">0</span>
<span class="n">szqueue</span><span class="p">.</span><span class="nf">push</span><span class="p">(</span><span class="o">...</span><span class="p">,</span> <span class="n">tout</span><span class="p">)</span>
<span class="n">tout</span> <span class="o">=</span> <span class="vi">@stop</span> <span class="o">-</span> <span class="n">now</span>
<span class="k">raise</span> <span class="no">Timeout</span><span class="o">::</span><span class="no">Error</span> <span class="k">if</span> <span class="n">tout</span> <span class="o"><=</span> <span class="mi">0</span>
<span class="n">resultq</span><span class="p">.</span><span class="nf">pop</span><span class="p">(</span><span class="n">tout</span><span class="p">)</span>
<span class="k">end</span>
</code></pre> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=729752018-07-17T05:42:31Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><blockquote>
<p>Feature <a class="issue tracker-2 status-1 priority-4 priority-default" title="Feature: [PATCH] implement Timeout in VM (Open)" href="https://redmine.ruby-lang.org/issues/14859">#14859</a>: [PATCH] implement Timeout in VM<br>
<a href="https://bugs.ruby-lang.org/issues/14859" class="external">https://bugs.ruby-lang.org/issues/14859</a></p>
</blockquote>
<p>Note: I'm still working on this. [Feature <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: [PATCH] auto fiber schedule for rb_wait_for_single_fd and rb_waitpid (Closed)" href="https://redmine.ruby-lang.org/issues/13618">#13618</a>] (auto-fiber)<br>
basically has an implementation of timeouts in the VM, too,<br>
because of timeout args in rb_io_wait_*able.</p>
<p>I would rather implement this feature first without making<br>
visible API changes for <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: [PATCH] auto fiber schedule for rb_wait_for_single_fd and rb_waitpid (Closed)" href="https://redmine.ruby-lang.org/issues/13618">#13618</a>.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=730152018-07-19T01:53:00Zko1 (Koichi Sasada)
<ul></ul><p>Hi,</p>
<p>Could you explain your algorithm in pseudo code (or English)?<br>
Current <code>timeout</code> method call makes a thread and use <code>Thread#raise</code>.</p>
<p>I assume that your idea is creating "timeout scheduler" in VM and it manages <code>timeout</code> calls and invoke <code>Thread#raise</code> for timeout blocks if necessary.</p>
<p>BTW:</p>
<blockquote>
<p>I meant: stop using rb_provide("timeout.rb")</p>
</blockquote>
<p>Why? Some existing codes <code>require('timeout')</code>.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=730172018-07-19T04:04:19Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><pre><code>ko1@atdot.net wrote:
> Hi,
>
> Could you explain your algorithm in pseudo code (or English)?
> Current `timeout` method call makes a thread and use `Thread#raise`.
>
> I assume that your idea is creating "timeout scheduler" in VM and it manages `timeout` calls and invoke `Thread#raise` for timeout blocks if necessary.
Yes. The "timeout scheduler" is the same idea I used for auto-fiber.
It uses ccan/list to manage a sorted list of timeouts.
In my early version of the patch, I think the list_head struct
is per-VM. I may make this per-thread; not sure, yet.
Either way, the idea is the same based on ccan/list and sort order.
list_del() is fast, so timer expiration (common case) is cheap.
Slowest part is insertion sort to maintain order O(n); but
we can optimize for expected usage and limit traversal.
If the list_head is VM-wide; it insertion sort should walk
backwards since we can assume many Threads will use the same
timeout. If list_head is per-Thread, it should walk forwards;
because nested Timeout only makes sense if inner timeout is
smaller than outer one.
In other words, this is wrong regardless of implementation,
so I won't optimize for it:
Timeout.timeout(t+=1) do
Timeout.timeout(t+=1) do
Timeout.timeout(t+=1) do
Timeout.timeout(t+=1) do
Timeout.timeout(t+=1) do
This is correct, but overkill:
Timeout.timeout(t-=1) do
Timeout.timeout(t-=1) do
Timeout.timeout(t-=1) do
Timeout.timeout(t-=1) do
Timeout.timeout(t-=1) do
Best is just a single-timeout per-EC:
Timeout.timeout(t) do
...
Worst-case insertion sort should still be faster than Thread.new :)
The list_top() check covers good blocking functions which take
timeout arguments. However, we still need to rely on timer
interrupt flag for functions which do not take timeout (and
pure-Ruby code). So we need to set timer thread or POSIX timer
to set interrupt flag (same way we do normal timeslice).
(*) Btw, I should have timer-thread removal w/ POSIX timers
ready-to-publish soon.
> BTW:
>
> > I meant: stop using rb_provide("timeout.rb")
>
> Why? Some existing codes `require('timeout')`.
I mean, we keep lib/timeout.rb as an empty file so `require'
still works; but is a no-op. I don't feel strongly about it,
though.
</code></pre> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=730552018-07-21T08:09:12Zfunny_falcon (Yura Sokolov)funny.falcon@gmail.com
<ul></ul><p>normalperson (Eric Wong) wrote:</p>
<blockquote>
<p>Yes. The "timeout scheduler" is the same idea I used for auto-fiber.<br>
It uses ccan/list to manage a sorted list of timeouts.</p>
</blockquote>
<p>Still wonder, why you don't use binary min-heap for timers - most commonly used datastructure for this task.<br>
It has guaranteed O(log n) performance for insertion/deletion, and O(1) for check for min, and has very simple implementation.<br>
Note, that for insertion of new maximum value, binary min-heap also gives O(1) performance because item will not sift up.</p> Ruby master - Feature #14859: [PATCH] implement Timeout in VMhttps://redmine.ruby-lang.org/issues/14859?journal_id=730642018-07-22T07:42:38Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p><a href="mailto:funny.falcon@gmail.com" class="email">funny.falcon@gmail.com</a> wrote:</p>
<blockquote>
<p>normalperson (Eric Wong) wrote:</p>
<blockquote>
<p>Yes. The "timeout scheduler" is the same idea I used for auto-fiber.<br>
It uses ccan/list to manage a sorted list of timeouts.</p>
</blockquote>
<p>Still wonder, why you don't use binary min-heap for timers -<br>
most commonly used datastructure for this task.</p>
<p>It has guaranteed O(log n) performance for insertion/deletion,<br>
and O(1) for check for min, and has very simple<br>
implementation.</p>
<p>Note, that for insertion of new maximum value, binary min-heap<br>
also gives O(1) performance because item will not sift up.</p>
</blockquote>
<p>I'll keep that in mind; I haven't looked at heap data structures<br>
in years :< O(log n) for delete doesn't sound appealing, though.</p>
<p>Most timeouts do not fire, they are deleted before the timeout<br>
is up because the task finishes on time. So I gravitate towards<br>
ccan/timer which has O(1) branchless delete (because it is just<br>
list_del from ccan/list).</p>
<p>However I tried ccan/timer from git://git.ozlabs.org/~ccan/ccan<br>
and making it available via "timeout_lgpl" bundled gem (LGPL);<br>
but I kept on hitting the brute_force_first() function which<br>
ended up being slow to find the first timer. So I will avoid it<br>
until brute_force_first is replaced/optimized in ccan/timer.</p>
<p>[ Old abandoned patch + timeout_lgpl gem using ccan/timer:<br>
https://80x24.org/spew/<a href="mailto:20180616120544.28171-1-e@80x24.org" class="email">20180616120544.28171-1-e@80x24.org</a>/raw<br>
git clone https://80x24.org/timeout_ext.git ]</p>
<p>For initial implementation, I chose naive insertion sort as<br>
it still beats Thread.new in current timeout.rb. But maybe we<br>
can try other data structures in the future (maybe build a<br>
skip list using ccan/list).</p>