From: David Miller <davem@davemloft.net>
To: xiaosuo@gmail.com
Cc: eric.dumazet@gmail.com, netdev@vger.kernel.org
Subject: Re: inetpeer with create==0
Date: Wed, 02 Mar 2011 21:36:34 -0800 (PST) [thread overview]
Message-ID: <20110302.213634.189680857.davem@davemloft.net> (raw)
In-Reply-To: <AANLkTimwaUaC7Xu2djSNR9k98sYbSM0V88sCAc34R6Ac@mail.gmail.com>
From: Changli Gao <xiaosuo@gmail.com>
Date: Thu, 3 Mar 2011 13:30:03 +0800
> I am just wondering why we need a trie(radix tree) here, we don't have
> to do LPM since the lengths of the keys are always fixed(ether 4 or
> 16). Maybe a hash table is enough and simpler, and it is RCU
> compatible.
Because trie eliminates all of the issues of having to size a hash
table, dynamically resize it, etc.
Trie gives well bounded performance dependent solely upon size of
the table, rather than access patterns, distribution of keys, and
how perfect hash function is.
We used to use a hash table for the page cache too, but now we use
a trie structure there as well, and that uses full long word sized
keys and the generic raidx-tree code.
Using hash tables is really foolish for potentially large data sets.
next prev parent reply other threads:[~2011-03-03 5:35 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-03-03 4:45 inetpeer with create==0 David Miller
2011-03-03 5:30 ` Changli Gao
2011-03-03 5:36 ` David Miller [this message]
2011-03-03 6:27 ` Changli Gao
2011-03-03 6:42 ` David Miller
2011-03-03 7:39 ` Eric Dumazet
2011-03-03 8:32 ` David Miller
2011-03-04 15:09 ` [PATCH net-next-2.6] inetpeer: seqlock optimization Eric Dumazet
2011-03-04 19:17 ` David Miller
2011-03-04 20:45 ` David Miller
2011-03-04 22:13 ` Eric Dumazet
2011-03-04 22:44 ` David Miller
2011-03-04 23:02 ` Eric Dumazet
2011-03-03 8:07 ` inetpeer with create==0 Changli Gao
2011-03-03 8:34 ` David Miller
2011-03-03 6:51 ` Eric Dumazet
2011-03-03 8:30 ` 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=20110302.213634.189680857.davem@davemloft.net \
--to=davem@davemloft.net \
--cc=eric.dumazet@gmail.com \
--cc=netdev@vger.kernel.org \
--cc=xiaosuo@gmail.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).