[zeromq-dev] patch: handle idle connections

[Dhammika Pathirana]

On Wed, Mar 25, 2009 at 7:47 AM, Martin Sustrik <sustrik at fastmq.com> wrote:
>
>>> Actually, I have an idea. The algorithm is completely domain specific,
>>> but
>>> simple and very fast...
>>
>> You don't care about ordering active connections, and you have a fixed
>> limit for A?  Then it would work nicely.
>>
>> There is still a problem that you'll get gaps in the A table when
>> connections go inactive.  You either need to scan over holes, or
>> compress.
>>
>> What I'd do is use linked lists but without memory allocation.  That
>> is, you allocate a block and in that, make linked lists.  I.e. array
>> of structures containing next pointer, and data.  Use two blocks, one
>> for active, one for idle.  Use offset pointers (i.e. byte offset from
>> start of block) rather than real memory pointers.  Then if you need to
>> expand the table you reallocate and copy.
>>
>> This lets you do everything rapidly with no copying, allocation,
>> scanning, compression...
>
> That was the original idea (see the diagram at the beginning of this
> thread). It requires 6 memory accesses per flip. However, look at the
> algorithm I've proposed once more. It creates no gaps. Ever. And it requires
> only 2 memory accesses per flip.
>


In this case we retain all associated pipes in idle list, right?
And we append/delete from active list.

Suppose we'll have something like,

struct my_node_t {
      pipe_t *pipe;    // associated pipe.
      size_t next;      // array index.
};

my_node_t *my_nodes = calloc (256, sizeof (my_node_t));
my_node_t *my_active_nodes = calloc (256, sizeof (my_node_t));

Moving in/out from active list : O(1)
Removing/reviving from idle list : O(n)
Adding to idle list : O(1) (could possibly involve array resizing)

We could do with just a one array but that'd require actually deleting nodes.


Dhammika