Re: [PATCH] schedule connect timeouts via eventAdd

On 01/23/2013 08:45 PM, Amos Jeffries wrote:
> On 24/01/2013 1:50 p.m., Alex Rousskov wrote:

>> To simplify your analysis and make it more meaningful, please consider a
>> typical steady state, where you have R new connections per second, t
>> second connection establishment delay, T second timeout, and negligible
>> number of actual timeouts. In that state, one event-based approach gives
>> you R*t timeouts and the second event-based approach gives you R*T
>> timeouts registered with Squid at any time.
>>
>> What are the cost of handling one event-based timeout in the first (add
>> and forget) and second (add and remove) event-based approaches? Since we
>> start search from the oldest event and all timeouts will go to the very
>> end of the list, I think the costs are:
>>
>> add-and-forget: R*T
>> add-and-remove: 2*R*t
>>
>> (*) The 2 multiplier for add-and-remove is kind of the worst case -- in
>> general, the event we want to cancel will be in the beginning of the
>> queue, not the end of it!
>
> I think there is a ^ calculation missing in the add-and-forget formula.
> Because the list growth is exponential the add() cost rises
> exponentially for each R+1.

I do not think the list grows in a steady state that I am considering
here: What we add to the list (at rate R per second) is then removed
from that list (at the same rate). The length of the list is "constant"
and determined by the time an event spends inside the list (T or t).

If the list grows, Squid will run out of RAM so there is no steady state
(an overload case that is not relevant to this discussion).

> The different length of timer values on each event type above means we
> cannot easily convert the list type to dlink_list. At least a full
> analysis of the queue usage. Possibly implementation of both front and
> back push ops switched by a check for which end is best to inject from
> (more cycles spent doing the check etc).

I think it would be easy to make the list work in both directions and
the decision which direction to use would be either up to the caller or
based on a simple comparison with the first and last event timestamp
(which one is closer to the new event?). However, that does not address
the RAM usage concern that both of us share (among other things).

Thank you,

Alex.
Received on Thu Jan 24 2013 - 07:01:53 MST