Merge pull request #803 from hintjens/master

Problem: man page example code was truncated at any '@'
Merge pull request #804 from hintjens/master

Small cleanups
Merge pull request #805 from hintjens/master

Problem: list and hash container APIs are messed up
Merge pull request #806 from hintjens/master

Redesigning zlistx API
Problem: src/zloop.c:287: assertion failure

zloop_destroy: Assertion `zlistx_size (self->zombies) == 0' failed.

Caused by creating / destroying a timer without actually starting
the reactor. The reactor only cleans up the zombie list when it's
running.

Solution: clean up the zombie list in the destructor, in any case.
Problem: code contains __WINDOWS__

Solution: fix to make work without platform dependencies.
Problem: move methods cause list corruption

If the node is already at the start or end, then move drops it off
the list completely.

Solution: don't move node if it's already in the right place.
Problem: zlistx_move_start/end was scanning list, on equality

Insertion sort did not stop on an item with the same value, so in
the worst case (a list of all identitical items), it scanned the
whole list.

Solution: insert before/after an item greater/less or equal to
new item.
Problem: zloop timers do not scale

This test case https://gist.github.com/hintjens/795ddedd577e3e0f00fc
shows the cost of inserting and deleting timers in larger-scale cases.
This test simulates a number of clients, each randomly getting messages.
At each message, the client's expiry timer is deleted and recreated.
This is currently how zproto_server works. We run 1M messages, to get
realistic figures:

    Testing zloop_timer insert/reset (1M simulated messages)
    125 clients => 487 msecs
    250 clients => 792 msecs
    500 clients => 1499 msecs
    1000 clients => 3623 msecs
    2000 clients => 7779 msecs
    4000 clients => 24761 msecs

The problem is when you have large numbers of DEALER clients talking to
a ROUTER server, and the server wants to expire idle clients with some
timeout, e.g. 30 seconds. Using zloop timers, this means deleting and
then recreating a timer for each received message. zloop does not order
its timers, and even if it did, finding a timer means searching the list,
an O(N) cost.

There are additional problems with the timer design of zloop, e.g. zloop
scans all timers each time it does a poll, which is potentially for each
recv operation. I will look at that later. For now my focus is managing
large sets of expiry timers.

There are various possible solutions to this problem, which get rather
complex. This was one proposal:

> The normal approach to timeouts is to have a priority queue based on a
> heap or balanced tree. This makes creating, canceling and restarting a
> timeout an O(log n) operation while finding the next timeout is O(1).

> My timeout queue uses a different approach taken from the Linux kernels
> network code. Most timeouts get canceled early. So the idea is to delay
> work for each timeout as long as possible in the hope that it gets
> canceled and you don't have to spend time on it at all. For this I have
> an array of buckets (zring). Bucket N holds timeouts that expire
> between 2^N and 2^(N+1) ticks from now. Every 2^N ticks all timeouts in
> bucket N are inspected and resorted into new buckets.

> Over time timeouts migrate from the highest bucket to the lowest and
> then expire. That is unless they get canceled. A timeout also only gets
> inspected a maximum number of times [iirc number of buckets + 1], less
> if canceled. The overall work is therefore comparable to a heap or
> sorted tree if all timeouts expire. But much less if they get canceled.

While the intention is good, that seems like far too much work. We can
keep things simple by observing that a sane server uses the same expiry
period for all clients. Thus, our basic data structure is an ordered list
of client timers. The oldest client timer is at the list head, the
youngest at the tail. Each time we have a message from a client we take
its timer out of the list and move it to the tail.

To support this, zxlist works with node "handles" which let us move nodes
without searching the list.

Solution: zloop implements client timers as "tickets", where a new ticket
always expires after the last ticket held so far, if any. It enforces
this by using a single value for all ticket delays, which you set via
zloop_set_ticket_delay (). The existing zloop timers are then used for
low-volume timers, and zloop lets you enforce this with a
zloop_set_timer_max () method.

The difference in performance is pretty decent:

    Testing zloop_ticket insert/reset (1M simulated messages)
    125 clients => 45 msecs
    250 clients => 45 msecs
    500 clients => 46 msecs
    1000 clients => 50 msecs
    2000 clients => 56 msecs
    4000 clients => 66 msecs
Problem: zlistx_delete does not check node is valid

This is an easy thing to check and assert, it helps calling code
that is switching from zlist, where zlist_remove takes an item
argument, and zlistx_delete takes a node handle.

Solution: check node tag, and assert if it's invalid.