From: ebiederm@xmission.com (Eric W. Biederman)
To: "David Laight" <David.Laight@ACULAB.COM>
Cc: "Eric Dumazet" <eric.dumazet@gmail.com>,
"David Miller" <davem@davemloft.net>,
<paul.gortmaker@windriver.com>, <tim.bird@am.sony.com>,
<kuznet@ms2.inr.ac.ru>, <linux-kernel@vger.kernel.org>,
<netdev@vger.kernel.org>
Subject: Re: RFC: memory leak in udp_table_init
Date: Wed, 29 Feb 2012 10:28:13 -0800 [thread overview]
Message-ID: <877gz5ze82.fsf@xmission.com> (raw)
In-Reply-To: <AE90C24D6B3A694183C094C60CF0A2F6026B6E7D@saturn3.aculab.com> (David Laight's message of "Mon, 27 Feb 2012 11:33:07 -0000")
"David Laight" <David.Laight@ACULAB.COM> writes:
>> It was to match the comment we have few lines above :
>>
>> /*
>> * The pid hash table is scaled according to the amount of memory in
> the
>> * machine. From a minimum of 16 slots up to 4096 slots at one
> gigabyte or
>> * more.
>> */
The comment was actually correct until someone converted the code to use
alloc_large_system_hash.
> These large hash tables are, IMHO, an indication that the
> algorithm used is, perhaps, suboptimal.
>
> Not least of the problems is actually finding a suitable
> (and fast) hash function that will work with the actual
> real-life data.
>
> The pid table is a good example of something where a hash
> table is unnecessary.
> Linux should steal the code I put into NetBSD :-)
On this unrelated topic. What algorithm did you use on NetBSD for
dealing with pids?
A hash chain length of 1 for common sizes is a pretty attractive
algorithm, as it minimizes the number of cache line misses. Ages ago
when I modeled the linux situation that is what I was seeing.
The normal case for the linux pid hash table is that it has 4096
entries taking 16k or 32k of memory and the typical process load
has about 200 or so processes. Making it very easy in the common
case to have a single entry hash chain.
All of the other algorithms I know have a tree structure and thus
more cache misses (as you traverse the tree) and ultimately worse
real world performance.
Eric
next prev parent reply other threads:[~2012-02-29 18:28 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-02-25 0:55 RFC: memory leak in udp_table_init Tim Bird
2012-02-25 1:27 ` Paul Gortmaker
2012-02-25 5:19 ` Eric Dumazet
2012-02-26 19:20 ` David Miller
2012-02-27 5:40 ` Eric Dumazet
2012-02-27 5:44 ` David Miller
2012-02-27 11:33 ` David Laight
2012-02-29 18:28 ` Eric W. Biederman [this message]
2012-03-01 8:55 ` David Laight
2012-03-01 12:33 ` Eric Dumazet
2012-03-15 17:44 ` Paul E. McKenney
2012-03-02 0:12 ` Eric W. Biederman
2012-02-27 6:03 ` [PATCH v2] mm: add a low limit to alloc_large_system_hash Eric Dumazet
2012-02-27 6:45 ` David Miller
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=877gz5ze82.fsf@xmission.com \
--to=ebiederm@xmission.com \
--cc=David.Laight@ACULAB.COM \
--cc=davem@davemloft.net \
--cc=eric.dumazet@gmail.com \
--cc=kuznet@ms2.inr.ac.ru \
--cc=linux-kernel@vger.kernel.org \
--cc=netdev@vger.kernel.org \
--cc=paul.gortmaker@windriver.com \
--cc=tim.bird@am.sony.com \
/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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).