My version - Re: Still working on a performance patch for conntrack, need some inp ut

[Daniel Stone]

Gidday!
Well, I'm still working on ip_conntrack_irc. It OOPSed the system so frequently 
that I decided it was out of control, wiped it, and I have now started again. 
The only problem now is that I've blown two motherboards, one being my 
sister's, and she's in Year 12 and needs it desperately for assignments, so my 
computer (minus, of course my hard drives) is now hers until I can get up 
enough cash for another Pentium mobo =( - I'm writing this on web mail from an 
NT box in the study.

Rusty, I need your input on this one. On IRC, multiple ports are used, the most 
general ones being 6660-7010. The ip_conntrack_helper structure only provides 
for monitoring one __constant_htons() port. How would I go about doing this 
without having 21 structs? I mean, I can do it with 21 if necessary, just it 
would get bloody messy.

Regards,
Daniel :)

Quoting Ryan Hoegg <RHoegg@CCEX.COM>:

> Hi all,
> 
> Some of you may remember some talk a couple months ago about applying a
> performance enhancement to the way conntrack stuffs lots and lots of
> entries
> in a hash table who's size is specified at compile time.  I proposed to
> implement this by sending hash table collisions to a binary tree instead of
> a linked list.  I am about 60% through coding this (I have a completely
> unrelated full time job.  Excuses, excuses.)  Anyhow, I wanted your input
> on
> a few things.
> 
> 1.  If anyone else is working on this independently (Rusty?) PLEASE e-mail
> me personally (hoegg@erols.com) so we can collaborate.
> 
> 2. What do you think about the performance benefit to balancing the trees?
> Here's my thoughts so far:
> 
> The reason for implementing trees in the first place is that we will be
> doing far more searches on these than inserts.  Therefore we take a small
> performance hit on insertion for a significant performance benefit on
> searches.  Now, balancing the tree on each insertion will distribute the
> additional overhead of keeping them balanced over all insertions but will
> add the isBalanced check plus the reBalancing(which will only be one level
> deep since we're doing it each insertion) to each insertion.  The advantage
> is that in high collision situations (where the size of the hashtable is
> much smaller than the number of simultaneous connections) searches will be
> guaranteed to be O(N log 2) where N is the number of connections stuffed
> into one hash entry.  If we don't balance at all, worst case for searches
> is
> still O(N), identical to linked list implementation.
> 
> One other option that occurred to me is to balance all trees of depth > x
> every y minutes, but only if processor time < z%.
> 
> Any suggestions, input, or flames will be greatly appreciated.
> 
> 2 out of 3 ain't bad,
> --ryan
>