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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 19 Feb 2007 17:25:05 +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 Mon, Feb 19, 2007 at 03:14:02PM +0100, Eric Dumazet (dada1@...mosbay.com) wrote:
> > Forget about cache misses and cache lines - we have a hash table, only
> > part of which is used (part for time-wait sockets, part for established
> > ones).
> 
> No you didnt not read my mail. Current ehash is not as decribed by you.

I did.
And I also said that my tests do not have timewait sockets at all - I
removed sk_for_each and so on, which should effectively increase lookup 
time twice on busy system with lots of created/removed sockets per
timeframe (that is theory from my side already).
Anyway, I ran the same test with increased table too.

> > Anyway, even with 2^20 (i.e. when the whole table is only used for
> > established sockets) search time is about 360-370 nsec on 3.7 GHz Core
> > Duo (only one CPU is used) with 2 GB of ram.
> 
> Your tests are user land, so unfortunatly are biased...
> 
> (Unless you use hugetlb data ?)

No I do not. But the same can be applied to trie test - it is also
performed in userspace and thus suffers from possible swapping/cache
flushing and so on.

And I doubt moving test into kernel will suddenly end up with 10 times 
increased rates.

Anyway, trie test (broken implementation) is two times slower than hash
table (resized already), and it does not include locking isses of the
hash table access and further scalability issues.

I think I need to fix my trie implementation to fully show its
potential, but original question was why tree/trie based implementation
is not considered at all although it promises better performance and
scalability.

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