• Subject: Re: efficient timers
• From: Sean Conner <sean@...>
• Date: Mon, 13 Apr 2015 03:59:12 -0400

```It was thus said that the Great Thijs Schreijer once stated:
>
> Thx for the info, but maybe my question should have been clearer. Timer
> functionality basically consists of 3 parts;
>
> 1 - a ticking clock
> 2 - a task execution method
> 3 - timer management (scheduling and cancelling of timers)
>
> The methods listed above concern mostly 1, and a bit of 2. Whilst I'm
> looking for an efficient way to do 3.
>
> Consider a server with 1000 connections, each having a timeout timer. Most
> timers never execute, they are just fallbacks. Having a sorted linked list
> in this situation, would require traversal of that linked list for each
> timer added (called an O(n) operation if I'm not mistaken), which is
> costly performance wise. I would like an algorithm that has O(1) for both
> scheduling and cancellation of timers (once again if I'm not mistaken, I'm
> not that familiar with this O notation stuff).

I solved this at work by using a binary heap (sorted by timeout---the
algorithm I used was straight off the Wikipedia) in an array portion of a
table (the node at index 1 contains the next coroutine to expire) and in the
normal associative portion of the table, the information node indexed by
coroutine.  The code is:

function SQUEUE:insert(when,co)
local function bubble_up(parent,child) ... end

local idx     = #self + 1
local parent  = math.floor(idx / 2)
local info    = {
awake   = clock.get('monotonic') + when,
co      = co,
trigger = true
}

self[idx] = info
self[co]  = info
bubble_up(parent,idx)
end

The timeout function is:

function timeout(when)
local co = coroutine.running()

if when == 0 then
if SQUEUE[co] then
SQUEUE[co].trigger = false
end
else
SQUEUE:insert(when,co)
end
end

In my main routine running the event loop, at the appropriate place,

while #SQUEUE > 0 do
local obj = SQUEUE[1] -- potential coroutine to run

if obj.trigger then	-- it hasn't been canceled
timeout = obj.awake - now
if timeout > 0 then	-- not yet time to run this
break
end

schedule(obj.co,...)
end

-- -------------------------------------------------
-- here, the node is either scheduled, or cancelled,
-- so it's removed
-- -------------------------------------------------

SQUEUE:delete() -- left as exercise for the reader
end

A definite limitation is only having one timeout per coroutine active, but
that's all I need currently.  I may want to check up on the timing-wheel and
see if it's better than what I have now.

-spc

```