Re: Fw: hfsc and huge set of rules

[Patrick McHardy <kaber@trash.net>]

devik wrote:

>Also IIRC class lookup is done before each remove. With
>hashing size a few tens of buckets the complexity
>starts to be very near to O(n^2).
>  
>
I think the hash size of HTB, HFSC and CBQ should be increased,
the hash function performs well even with 2^16. With HFSC using
many classes doesn't scale well right now, but with the rbtree patches
it will.

Regards
Patrick

>devik
>
>On Fri, 30 Jul 2004, Patrick McHardy wrote:
>
>  
>
>>David S. Miller wrote:
>>    
>>
>>>Looks like qdisc destruction has some expensive algorithms.
>>>Any quick ideas about the root culprit at least in the hfsc
>>>case?  He says htb does it too.
>>>      
>>>
>>hfsc_destroy_qdisc takes O(n) time wrt. the number of classes,
>>but 5-6 seconds is still long. If all these classes contain inner
>>qdiscs other than the default, I guess removing the classes from
>>dev->qdisc_list in qdisc_destroy takes up most of the time, with
>>n O(n) operations. The __qdisc_destroy rcu callback also calls
>>reset before destroy, I don't know any qdisc where this is really
>>neccessary. Without inner qdiscs, I need to see the script first to
>>judge what's going wrong. Tomasz ?
>>    
>>