funny.falcon / gmail.com wrote:
> 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. 

I'll keep that in mind; I haven't looked at heap data structures
in years :<   O(log n) for delete doesn't sound appealing, though.

Most timeouts do not fire, they are deleted before the timeout
is up because the task finishes on time.  So I gravitate towards
ccan/timer which has O(1) branchless delete (because it is just
list_del from ccan/list).

However I tried ccan/timer from git://git.ozlabs.org/~ccan/ccan
and making it available via "timeout_lgpl" bundled gem (LGPL);
but I kept on hitting the brute_force_first() function which
ended up being slow to find the first timer.  So I will avoid it
until brute_force_first is replaced/optimized in ccan/timer.

[ Old abandoned patch + timeout_lgpl gem using ccan/timer:
   https://80x24.org/spew/20180616120544.28171-1-e / 80x24.org/raw
   git clone https://80x24.org/timeout_ext.git ]


For initial implementation, I chose naive insertion sort as
it still beats Thread.new in current timeout.rb.  But maybe we
can try other data structures in the future (maybe build a
skip list using ccan/list).

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