From: Eric Dumazet <dada1@cosmosbay.com>
To: Robert Olsson <Robert.Olsson@data.slu.se>
Cc: David Miller <davem@davemloft.net>,
netdev@vger.kernel.org, robert.olsson@its.uu.se, npiggin@suse.de
Subject: Re: [RFC PATCH]: Dynamically sized routing cache hash table.
Date: Tue, 6 Mar 2007 15:18:09 +0100 [thread overview]
Message-ID: <200703061518.09309.dada1@cosmosbay.com> (raw)
In-Reply-To: <17901.28634.359369.341093@robur.slu.se>
On Tuesday 06 March 2007 14:42, Robert Olsson wrote:
> Eric Dumazet writes:
> > Well, maybe... but after looking robert's trash, I discovered its model
> > is essentially a big (2^18 slots) root node (our hash table), and very
> > few order:1,2,3 nodes.
>
> It's getting "hashlike" yes. I guess all effective algorithms today is
> doing some sort of "index" lookup and for large number of entries we cannot
> expect to find the next node in the same cache line so the "tree depth"
> becomes a crucial performance factor. IMO nothing can beat a prefect
> distributed and perfect sized hash. The trash work is an effort to get
> close with dynamic data structure.
Indeed. It would be nice to see how it performs with say 2^20 elements...
Because with your data, I wonder if the extra complexity of the trash is worth
it (since most lookups are going to only hit the hash and give the answer
without intermediate nodes)
next prev parent reply other threads:[~2007-03-06 14:18 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-03-06 4:26 [RFC PATCH]: Dynamically sized routing cache hash table David Miller
2007-03-06 7:14 ` Eric Dumazet
2007-03-06 7:23 ` David Miller
2007-03-06 7:58 ` Eric Dumazet
2007-03-06 9:05 ` David Miller
2007-03-06 10:33 ` [PATCH] NET : Optimizes inet_getpeer() Eric Dumazet
2007-03-07 4:23 ` David Miller
2007-03-06 13:42 ` [RFC PATCH]: Dynamically sized routing cache hash table Robert Olsson
2007-03-06 14:18 ` Eric Dumazet [this message]
2007-03-06 17:05 ` Robert Olsson
2007-03-06 17:20 ` Eric Dumazet
2007-03-06 18:55 ` Robert Olsson
2007-03-06 9:11 ` Nick Piggin
2007-03-06 9:17 ` David Miller
2007-03-06 9:22 ` Nick Piggin
2007-03-06 9:23 ` Eric Dumazet
2007-03-06 9:41 ` Nick Piggin
2007-03-06 13:26 ` Robert Olsson
2007-03-06 22:20 ` David Miller
2007-03-08 6:26 ` Nick Piggin
2007-03-08 13:35 ` Robert Olsson
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=200703061518.09309.dada1@cosmosbay.com \
--to=dada1@cosmosbay.com \
--cc=Robert.Olsson@data.slu.se \
--cc=davem@davemloft.net \
--cc=netdev@vger.kernel.org \
--cc=npiggin@suse.de \
--cc=robert.olsson@its.uu.se \
/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).