[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: RE: efficient timers
- From: Thijs Schreijer <thijs@...>
- Date: Mon, 13 Apr 2015 06:45:31 +0000
> -----Original Message-----
> From: email@example.com [mailto:firstname.lastname@example.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 <email@example.com> wrote:
> > I have seen the following timers in Lua:
> > * posix.unistd.sleep 
> > * posix.time.nanosleep 
> > * posix.curses.napms 
> > * ngx.sleep 
> >  https://luaposix.github.io/luaposix/modules/posix.unistd.html#sleep
> >  https://luaposix.github.io/luaposix/modules/posix.time.html#nanosleep
> >  https://luaposix.github.io/luaposix/modules/posix.curses.html#napms
> >  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,
> Large page of methods at <http://lua-users.org/wiki/SleepFunction>.
> Suspend/resume a Lua script using coroutines:
> --- 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
> -- 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
> if bFirstRead == true then
> repeat nSize, strChunk = net.read(nSocket)
> until strChunk ~= "" or os.difftime(os.time(), t1) >
> nSize, strChunk = net.read(nSocket)
> strReply = strReply .. strChunk
> bFirstRead = false
> until nSize <= 0
> Best regards,
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