lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Tue, 20 Feb 2007 12:34:59 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Evgeniy Polyakov <johnpol@....mipt.ru>
Cc:	akepner@....com, linux@...izon.com, davem@...emloft.net,
	netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

On Tuesday 20 February 2007 12:29, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 12:09:51PM +0100, Eric Dumazet (dada1@...mosbay.com) 
wrote:
> > If we want to optimize tcp, we should reorder fields to reduce number of
> > cache lines, not change algos. struct sock fields are currently placed to
> > reduce holes, while they should be grouped by related fields sharing
> > cache lines.
>
> Getting into account that network stack with NAPI schedules several
> packets to be queued into socket and all that happens without any
> infuence from userspace, trie/tree wins again in that regard that
> majority of the tree will be in the cache already.

Nope, you receive 100 packets for 100 different flows. Only the code may be in 
cache (minus for the first packet), and the very top of the tree...

Forget cache. Forget it.

>
> Hash table has its fast access only in theory, practice adds caches,
> NAPI and a lot of other stuff. Even simple test (maybe broken, but it
> is equally broken for both trie and hash, even worse for trie))
> whows that hash table does not behave as good as expected and close to
> trie.
>
> I'm going back to drawing board to design simple trie algo/patch
> suitable for hash table selection replacement, so that we would test it
> in a real life examples.
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists