[zeromq-dev] patch: handle idle connections

[Pieter Hintjens]

On Wed, Mar 25, 2009 at 9:33 AM, Martin Sustrik <sustrik at fastmq.com> wrote:

> 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.  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.

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).

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.

-Pieter