Re: efficient timers

[Sean Conner <sean@...>]

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