From: Eric Wong Date: 2018-07-22T07:36:43+00:00 Subject: [ruby-core:88044] Re: [Ruby trunk Feature#14859] [PATCH] implement Timeout in VM 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: