RE: efficient timers
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: RE: efficient timers
- From: Thijs Schreijer <thijs@...>
- Date: 2015年4月13日 06:45:31 +0000
> -----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