From: Patrick McHardy <kaber@trash.net>
To: jdb@comx.dk
Cc: Netfilter Developers <netfilter-devel@vger.kernel.org>,
Harald Welte <laforge@netfilter.org>,
"Paul C. Diem" <PCDiem@FoxValley.net>,
Martin Josefsson <gandalf@netfilter.org>
Subject: Re: [PATCH 1/2] iptables/libiptc perf issue: Sorting chain during pull-out
Date: Wed, 28 Nov 2007 09:32:04 +0100 [thread overview]
Message-ID: <474D2784.3060303@trash.net> (raw)
In-Reply-To: <1196085397.3866.58.camel@localhost.localdomain>
Jesper Dangaard Brouer wrote:
> Performance optimize scalability issue:
> Sorting chain during pull-out give worst-case runtime O(Chains^2).
>
> When pulling out the blob, every chain name is inserted alphabetically
> into a linked list (by function iptc_insert_chain()). The problem
> with this approach is that the chain names delivered in the blob is
> already sorted (as we push it back to the kernel sorted).
>
> This cause chain parsing to always process every element in the chain
> list and finish with a tail add. Causing worst-case runtime O(C^2/2)
> for alphabetically sorting of chains.
>
> The patch solves this by only calling iptc_insert_chain() when
> creating new chains.
Applied, thanks a lot.
prev parent reply other threads:[~2007-11-28 8:32 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-11-26 13:56 [PATCH 1/2] iptables/libiptc perf issue: Sorting chain during pull-out Jesper Dangaard Brouer
2007-11-28 8:32 ` Patrick McHardy [this message]
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=474D2784.3060303@trash.net \
--to=kaber@trash.net \
--cc=PCDiem@FoxValley.net \
--cc=gandalf@netfilter.org \
--cc=jdb@comx.dk \
--cc=laforge@netfilter.org \
--cc=netfilter-devel@vger.kernel.org \
/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.