Re: [ANN] cqueues 20140729

[William Ahern <william@...>]

On Mon, Aug 04, 2014 at 10:54:26AM +0200, Christian A. Steiner wrote:
> > making it the only open source event
> > framework in any language to have O(1) timeouts.
> 
> could you elaborate a bit more on this? do you mean custom timeouts .. aka
> timers .. or just a timeout for an i/o operation?

Custom timeouts. Currently the scheduler uses a red-black tree for timeouts.
libevent, libev, and libuv use a min-heap. But I finished a hierarchical
timing wheel a few months ago and am almost done with testing.

	http://25thandclement.com/~william/projects/timeout.c.html

The algorithm is complex. Not the timing wheel per se. I use some novel bit
arrays and bit-wise operations so that the timing wheel doesn't need a
periodic timer, nor does the library need to scan the wheels in order to
make progress. That makes it extremely cache friendly, in addition to being
O(1) worst-cast for all operations.

Not only is it O(1), it's also faster in real-world performance than
libevent's min-heap by a factor of at least 2x even on things like insert,
where a min-heap has O(1) average complexity. And min-heap has O(log N) for
deletes, which is not great for network software because most timeouts will
be deleted before they expire, so deletes matter.

Anyhow, in cqueues you can sleep a coroutine by just doing

	cqueues.sleep(timeout)

where timeout can have fractional seconds. cqueues.sleep(timeout) is
equivalent to cqueues.poll(timeout), because Lua numbers are treated as
timeouts (note that you can pass multiple arguments of different types to
.poll). To poll on sockets you must pass an object (table, userdata) with
a :pollfd method to return the descriptor number, an :events method to
return the event mask, and an optional :timeout for the object timeout. I
use :pollfd rather than :fileno because objects could have multipe different
descriptors. For example my socket objects support non-blocking DNS lookup
internally, so :pollfd will return the DNS socket initially before
switching over to returning another socket descriptor during connect and I/O
phases.

cqueues doesn't rely on the kernel's socket timeout at all. For one thing,
that makes it difficult and inefficient to do timeouts for operations which
span multiple socket I/O calls.

My goal is to make cqueues _faster_ than even pure C non-blocking socket
frameworks. And it's getting there. By leverage Lua's memory management I
can optimize use of epoll, kqueue, and Solaris ports in ways that are
extremely difficult or impossible to do using generic C or C++ libraries.