[zeromq-dev] patch: handle idle connections

[Martin Sustrik]

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


What about doing something like database denormalisation i.e. adding 
redundant data to improve performance?

Say the pipe remembers the index it occupies in the array:

     //  Revive an idle pipe.
     pipes_t::size_type i = pipe_->index ();
     ...

Martin

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