netdev - Re: Extensible hashing and RCU

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 linux-hardening linux-cve-announce 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 14:29:02 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	akepner@....com, linux@...izon.com, davem@...emloft.net,
	netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

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.

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.

-- 
	Evgeniy Polyakov
-
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