Re: efficient timers

[Andrew Starks <andrew.starks@...>]

On Monday, April 13, 2015, Daurnimator <quae@daurnimator.com> wrote:
> On 13 April 2015 at 18:17, Oliver Kroth <oliver.kroth@nec-i.de> wrote:
> > Hi Thijs,
> >
> > not sure if someone else referred to a solution like mine:
> > I used in one of my projects a so called binary heap as "queue". New events
> > are inserted at the end and bubbled up. Deleted timers leave a hole that is
> > filled by inserting the last element and resort the heap. Checking whether
> > the first (earliest) event is due can be done in O(1) by looking on the
> > heap's root. Inserting and deleting events can be done in O(log n). The
> > funny thing is that the heap does not use pointers but is stored in a
> > contiguous array using the event's index to calculate the parent's and
> > children's indexes.
> >
> > May not be the most efficient solution but had the smallest overhead on
> > checking the due events, and has reasonable effort on queue management.
> > The Lua implementations is about 100 LOC.
> >
> > If someone is interested, I may post it.
> >
> > --
> > Oliver Kroth
> >
> >
> > Am 12.04.2015 um 21:29 schrieb Thijs Schreijer:
> >
> > I’m looking for an efficient timer mechanism in Lua. Does anyone know of any
> > Lua based timing-wheel implementations? (before I roll my own)
> >
> >
> >
> > Thx.
> >
> > Thijs
> >
> >
>
> I know prosody has an indexed binary heap implementation:
> https://hg.prosody.im/trunk/file/071611bc4f1d/util/indexedbheap.lua
>
> I think already mentioned in this thread is william ahearn's timing
> wheel implementation:
> http://25thandclement.com/~william/projects/timeout.c.html
>
> Algorithmcally it's worth mentioning elastic binary trees (as used by
> Willy Tareau in haproxy): https://1wt.eu/articles/ebtree/

I've been reading these links and will continue to go through them. Great info here, at least for me. 

I made a run at these issues in my concurrency library, which I made as a method of getting my mind around concurrency, as a concept. 

After 5 or so attempts, my last approach copies and extends the coroutines API by wrapping each thread in a table, so that the thread becomes an object. That way, the thread can carry its own time out info. My wrapped 'resume' and 'yield' methods check for time out (and in yield, for signal tokens like "shutdown"). 

An example of using it is my "await" method, which is like a create + "while not timeout > now resume until co ~= suspended return success, ...", using a short chain of functions, in order to preserve the varargs.

I don't know if this approach is fast or not. I did try to reuse threads by pooling them, but it was way slower than just having lua deal with the creation/collecting. 

The upshot, I think, is that I don't have to search a timeout tree and I can build up unique timeout delegates, or whathaveyou, on a per-thread basis. 

-Andrew