Re: efficient timers

[Daurnimator <quae@...>]

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/