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:	Sat, 18 Oct 2008 11:45:50 +0300
From:	"Pekka Enberg" <penberg@...helsinki.fi>
To:	"Andi Kleen" <andi@...stfloor.org>
Cc:	"Chris Snook" <csnook@...hat.com>,
	"Maxim Levitsky" <maximlevitsky@...il.com>,
	linux-kernel@...r.kernel.org
Subject: Re: [Slightly off topic] A question about R/B trees.

Hi Andi,

On Sat, Oct 18, 2008 at 10:53 AM, Andi Kleen <andi@...stfloor.org> wrote:
> The problem with hash tables is that if they're big enough
> or if the rest of the workload is memory intensive
> each hit will be a cache miss. And you can do a lot of branch
> mispredicts in the time of a single cache miss.
>
> In general trees can be much better for cache usage, although
> it's generally better to use some tree that has nodes near
> the cache line size. Binary trees like RB are too small for that.

Right, but even for binary trees, you can get some of the benefits by
packing all the nodes in a slab cache of their own. That way many of
the neighboring nodes will share the same cache line if you're
allocating memory for the nodes in a top-down order. Of course, you
lose the benefits if the tree is updated a lot because you're back to
worst case allocation again.

                       Pekka
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists