RE: efficient timers

[Thijs Schreijer <thijs@...>]

> -----Original Message-----
> From: lua-l-bounces@lists.lua.org [mailto:lua-l-bounces@lists.lua.org] On
> Behalf Of Paul Merrell
> Sent: maandag 13 april 2015 2:52
> To: Lua mailing list
> Subject: Re: efficient timers
> 
> On Sun, Apr 12, 2015 at 12:49 PM, Nagaev Boris <bnagaev@gmail.com> wrote:
> > I have seen the following timers in Lua:
> >
> >  * posix.unistd.sleep [1]
> >  * posix.time.nanosleep [2]
> >  * posix.curses.napms [3]
> >  * ngx.sleep [4]
> >
> > [1] https://luaposix.github.io/luaposix/modules/posix.unistd.html#sleep
> > [2] https://luaposix.github.io/luaposix/modules/posix.time.html#nanosleep
> > [3] https://luaposix.github.io/luaposix/modules/posix.curses.html#napms
> > [4] http://wiki.nginx.org/HttpLuaModule#ngx.sleep
> 
> More that I've snipped from here and there:
> 
> Clean sleep method using a repeat … until loop, by Peter Odding,
> <http://lua-users.org/lists/lua-l/2008-03/msg00213.html>
> 
> Large page of methods at <http://lua-users.org/wiki/SleepFunction>.
> 
> Suspend/resume a Lua script using coroutines:
> <http://stackoverflow.com/questions/6145059/how-to-suspend-resume-
> processing-of-a-lua-command>
> 
> --- Delay for a number of seconds.
> -- @param delay Number of seconds
> function delay_s(delay)
>     delay = delay or 1
>     local time_to = os.time() + delay
>     while os.time() < time_to do end
> end
> 
> -- wait for a reply, using a custom timeout (set to 5 seconds here):
> 
> 
> -- send HTTP request
> strQuery =  "GET " .. strVersionUrlUri .. " HTTP/1.1\r\nHost: " ..
> strVersionUrlHost .. "\r\n\r\n"
>    net.write(nSocket, strQuery)
>      t1 = os.time()
>         -- read HTTP response
>         strReply = ""
>         bFirstRead = true
>         nTimeoutSec = 5
> 
>         repeat
>           if bFirstRead == true then
>             repeat nSize, strChunk = net.read(nSocket)
>               until strChunk ~= "" or os.difftime(os.time(), t1) >
> nTimeoutSec
>           else
>             nSize, strChunk = net.read(nSocket)
>           end
>           strReply = strReply .. strChunk
>           bFirstRead = false
>         until nSize <= 0
> 
> Best regards,
> 
> Paul
> 

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).
A timing-wheel is such an algorithm. See (link by Nathan) http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf 

Thijs