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 Daurnimator
> Sent: maandag 13 april 2015 11:44
> To: Lua mailing list
> Subject: Re: efficient timers
> 
> 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/


Thx for the input everyone. I dropped the timingwheel for now, and went for the Binary tree, though probably slightly slower, it is more flexible and consumes less memory.

So I took Oliver Kroths core and added the concept by Sean Conner of the reverse lookup and came up with a module that allows creation of min/max-heaps and min/max-'unique heaps' where the payload is a unique value that can be used for the reverse lookup.

Need to add more tests still, but please have a look. Feedback is most welcome!

Code: https://github.com/Tieske/binaryheap.lua 

Thijs

Ps. Requires busted for testing and docs are in './doc'