From: Eric Wong <normalperson@...>
Date: 2018-07-19T03:58:26+00:00
Subject: [ruby-core:88001] Re: [Ruby trunk Feature#14859] [PATCH] implement Timeout in VM

```
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.

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