linux-kernel - Re: [Slightly off topic] A question about R/B trees.

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]

Message-ID: <84144f020810180145p68a89d17y7609644f7b9d21bf@mail.gmail.com>
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/