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:	Sat, 3 Mar 2007 13:46:21 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	"Michael K. Edwards" <medwards.linux@...il.com>
Cc:	Eric Dumazet <dada1@...mosbay.com>, akepner@....com,
	linux@...izon.com, davem@...emloft.net, netdev@...r.kernel.org
Subject: Re: Extensible hashing and RCU

On Fri, Mar 02, 2007 at 12:45:36PM -0800, Michael K. Edwards (medwards.linux@...il.com) wrote:
> On 3/2/07, Eric Dumazet <dada1@...mosbay.com> wrote:
> >Thank you for this report. (Still avoiding cache misses studies, while they
> >obviously are the limiting factor)
> 
> 1)  The entire point of going to a tree-like structure would be to
> allow the leaves to age out of cache (or even forcibly evict them)
> when the structure bloats (generally under DDoS attack), on the theory
> that most of them are bogus and won't be referenced again.  It's not
> about the speed of the data structure -- it's about managing its
> impact on the rest of the system.
> 
> 2)  The other entire point of going to a tree-like structure is that
> they're drastically simpler to RCU than hashes, and more generally
> they don't involve individual atomic operations (RCU reaping passes,
> resizing, etc.) that cause big latency hiccups and evict a bunch of
> other stuff from cache.
> 
> 3)  The third entire point of going to a tree-like structure is to
> have a richer set of efficient operations, since you can give them a
> second "priority"-type index and have "pluck-highest-priority-item",
> three-sided search, and bulk delete operations.  These aren't that
> much harder to RCU than the basic modify-existing-node operation.
> 
> Now can we give these idiotic micro-benchmarks a rest until Robert's
> implementation is tuned and ready for stress-testing?

Mmm, you have learnt new words from other threads :)
It is not a benchmark, it is analysis of the structure processing.
All you have written above is correct, since it was said in this thread
multiple times, but it does not change the fact, that tree traversal is
slower than list one, so to compete tree (or another algo, which would 
be even more interesting) implementation must have that in mind and be 
faster in any (the most) load. As is tree/trie does not have it (it is
feature of algorithm), but has another advantages (extremely suitable in
routing cache whihc requires wildcard support and scaling) you did not
mention - ability to scale without structure recreations.

Btw, you could try to implement something you have written above to show
its merits, so that it would not be an empty words :)

> Cheers,
> - Michael

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