[zeromq-dev] patch: handle idle connections

[Dhammika Pathirana]

Hi Martin,

On Sat, Apr 11, 2009 at 11:48 AM, Martin Sustrik <sustrik at fastmq.com> wrote:
> Hi Dhammika,
>
> I was trying to merge in your O(1) scheduler and in the process of doing so
> I've found one more place where the complexity is still O(n):
>
> +void zmq::mux_t::revive (pipe_t *pipe_)
> +{
> +    //  Revive an idle pipe.
> +    for (pipes_t::size_type i = pipes.size (); i-- > active; ) {
> +        if (pipes [i] == pipe_) {
> +            std::swap(pipes [i], pipes [active]);
> +            ++active;
> +            return;
> +        }
> +    }
>
> We should convert the pointer into array index in constant time somehow.
>
> Any ideas?


I see, if we have only few idle pipes then it wouldn't be bad.
We could traverse from the beginning though. This will probably
improve it for pipes which go idle for a fraction.
But still worst case is O(n).

+    //  Revive an idle pipe.
+    pipes_t::size_type j = active;
+    pipes_t::size_type i = pipes.size ();
+
+    for ( ; i > j; j++) {
+        if (pipes [j] == pipe_) {
+            std::swap(pipes [j], pipes [active]);
+            ++active;
+            return;
+        }
+    }

What do you think?


Dhammika



> Martin
>
> Dhammika Pathirana wrote:
>>
>> On Mon, Mar 30, 2009 at 12:45 AM, Martin Sustrik <sustrik at fastmq.com>
>> wrote:
>>>
>>> Dhammika,
>>>
>>> Great! We'll give it a try on all the different platforms. We'll do some
>>> performance tests as well (1,10,100,1000,10000 idle connections +
>>> ping-pong
>>> latency test). However, it won't get into version 0.6 as that one is
>>> already
>>> closed for new functionality.
>>>
>>> Also, we need you to state that the patch is submitted under MIT license
>>> to
>>> be able to merge it into the trunk.
>>>
>>
>>
>> Sure, patch is submitted under MIT license.
>>
>> Dhammika
>
>