[zeromq-dev] patch: handle idle connections

[Martin Sustrik]

Dhammika Pathirana wrote:
> 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)

I believe you can get all three to O(1) - except of possible array 
resizing when new connection is created.

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

I believe you can go on with a single array. Nodes are deleted only when 
connection ends, thus the performance of the operation is not critical.

Here's a diagram of flipping active to passive (or vice versa)...

Comments are welcome.
Martin

-------------- next part --------------
A non-text attachment was scrubbed...
Name: swap.png
Type: image/png
Size: 17901 bytes
Desc: not available
URL: <https://lists.zeromq.org/pipermail/zeromq-dev/attachments/20090326/b6c49d09/attachment.png>