[zeromq-dev] patch: handle idle connections

[Martin Sustrik]

Pieter,

>> On the other hand, the goal of this patch is to turn O(n) algorithm of
>> finding next active pipe to O(1) algorithm. I'm not sure whether it can
>> be achieved with bitmap. There are several clever bitmap lookup
>> algorithms, however, all of them are O(n) AFAIK.
> 
> It depends a lot on the maximum size and expected density of your
> bitmap and the proportion of scans compared to updates.

Scenario: 10,000s of connections, only few of them being active at any 
specific time.

Requirements:
- connections are sorted into two disjunct sets (active, idle)
- moving element from one set to another should be O(1)
- getting next element in a set (browsing) should be O(1)
- no memory allocation should happen in either of the two functions above
- minimal number of memory accesses should be done in both functions

> There's a
> decent bit map algorithm in IPR (OpenAMQ's library) which is still
> O(n) however.  It's not compressed, and optimized for frequent changes
> rather than scans.

Yes, I had that one on the mind. Still, it's O(n) so it won't scale.

> If you have a very sparse bitmap or you do few changes and many scans,
> you could use compression (run length or next bit) which would give
> you O(1).

Not an option. Bit flip has to occur in nanoseconds.

> You could also just store your bits as an array of positions, giving
> you very fast scanning but at the cost of orders of magnitude extra
> space.  Fine for small bitsets and trivial to implement.

The bitsets are large (10k). If positions are stored in array, removing 
a single position would cause subsequent positions to move in the memory 
=> lot of memory access => slow. If stored in linked list each new 
position requires new memory allocation => malloc => slow.

Actually, I have an idea. The algorithm is completely domain specific, 
but simple and very fast:

Imagine all the connections (N of them) stored in a single array. We 
also store a number of active connections (A). Active connections are 
stored on positions [0,A-1] of the array. Idle connections are stored on 
positions [A, N-1].

Moving to next active connection:

current = (current + 1) % A;

Moving connection from active to idle:

std::swap (connections [current], connections [A-1]);
A = A - 1;

Moving connection from idle to active:

std::swap (connections [current], connections [A]);
A = A + 1;

What about this approach?
Martin