All of lore.kernel.org
 help / color / mirror / Atom feed
From: Patrick McHardy <kaber@trash.net>
To: Simon Lodal <simonl@parknet.dk>
Cc: netdev@vger.kernel.org, lartc@mailman.ds9a.nl
Subject: [LARTC] Re: [PATCH] HTB O(1) class lookup
Date: Thu, 01 Feb 2007 06:08:47 +0000	[thread overview]
Message-ID: <45C183EF.2040701@trash.net> (raw)
In-Reply-To: <200702010618.48692.simonl@parknet.dk>

Simon Lodal wrote:
> This patch changes HTB's class storage from hash+lists to a two-level linear 
> array, so it can do constant time (O(1)) class lookup by classid. It improves 
> scalability for large number of classes.
> 
> Without the patch, ~14k htb classes can starve a Xeon-3.2 at only 15kpps, 
> using most of it's cycles traversing lists in htb_find(). The patch 
> eliminates this problem, and has a measurable impact even with a few hundred 
> classes.
> 
> Previously, scalability could be improved by increasing HTB_HSIZE, modify the 
> hash function, and recompile, but this patch works for everyone without 
> recompile and scales better too.

I agree that the current fixed sized hashes (additionally quite
small by default) are a big problem with many classes, for all of
HTB/HFSC/CBQ. But I think your approach is a bit wasteful, with
unfortunately chosen classids 128 classes are enough to reach the
maximum memory usage of ~512kb (with 4k pages and 8 byte pointers).

I have a patch for HFSC which introduces dynamic resizing of the
class hash. I have planned to generalize it (similar to tcf_hashinfo)
and convert HTB and CBQ as well, which as a nice side effect will
allow to get rid of some duplicated code, like hash walking.

If you give me a few days I'll try to finish and post it.
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

WARNING: multiple messages have this Message-ID (diff)
From: Patrick McHardy <kaber@trash.net>
To: Simon Lodal <simonl@parknet.dk>
Cc: netdev@vger.kernel.org, lartc@mailman.ds9a.nl
Subject: Re: [PATCH] HTB O(1) class lookup
Date: Thu, 01 Feb 2007 07:08:47 +0100	[thread overview]
Message-ID: <45C183EF.2040701@trash.net> (raw)
In-Reply-To: <200702010618.48692.simonl@parknet.dk>

Simon Lodal wrote:
> This patch changes HTB's class storage from hash+lists to a two-level linear 
> array, so it can do constant time (O(1)) class lookup by classid. It improves 
> scalability for large number of classes.
> 
> Without the patch, ~14k htb classes can starve a Xeon-3.2 at only 15kpps, 
> using most of it's cycles traversing lists in htb_find(). The patch 
> eliminates this problem, and has a measurable impact even with a few hundred 
> classes.
> 
> Previously, scalability could be improved by increasing HTB_HSIZE, modify the 
> hash function, and recompile, but this patch works for everyone without 
> recompile and scales better too.

I agree that the current fixed sized hashes (additionally quite
small by default) are a big problem with many classes, for all of
HTB/HFSC/CBQ. But I think your approach is a bit wasteful, with
unfortunately chosen classids 128 classes are enough to reach the
maximum memory usage of ~512kb (with 4k pages and 8 byte pointers).

I have a patch for HFSC which introduces dynamic resizing of the
class hash. I have planned to generalize it (similar to tcf_hashinfo)
and convert HTB and CBQ as well, which as a nice side effect will
allow to get rid of some duplicated code, like hash walking.

If you give me a few days I'll try to finish and post it.

  reply	other threads:[~2007-02-01  6:08 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-02-01  5:18 [LARTC] [PATCH] HTB O(1) class lookup Simon Lodal
2007-02-01  5:18 ` Simon Lodal
2007-02-01  6:08 ` Patrick McHardy [this message]
2007-02-01  6:08   ` Patrick McHardy
2007-02-01  7:08   ` [LARTC] " Simon Lodal
2007-02-01  7:08     ` Simon Lodal
2007-02-01 11:30     ` Andi Kleen
2007-02-05 10:16       ` [LARTC] " Jarek Poplawski
2007-02-05 10:16         ` Jarek Poplawski
2007-02-05 11:24         ` Andi Kleen
2007-02-05 12:45           ` Ingo Oeser
2007-02-05 17:14         ` [LARTC] " Simon Lodal
2007-02-05 17:14           ` Simon Lodal
2007-02-06  8:08           ` [LARTC] " Jarek Poplawski
2007-02-06  8:08             ` Jarek Poplawski
2007-02-08  7:36           ` [LARTC] " Jarek Poplawski
2007-02-08  7:36             ` Jarek Poplawski
2007-02-05 18:21       ` [LARTC] " Simon Lodal
2007-02-05 18:21         ` Simon Lodal
2007-02-01 13:06   ` jamal
2007-02-01 22:44 ` [LARTC] " Konrad Cempura

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=45C183EF.2040701@trash.net \
    --to=kaber@trash.net \
    --cc=lartc@mailman.ds9a.nl \
    --cc=netdev@vger.kernel.org \
    --cc=simonl@parknet.dk \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.