linux-kernel - Re: [PATCH] add b+tree library

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: <20090110222656.GJ26290@one.firstfloor.org>
Date:	Sat, 10 Jan 2009 23:26:56 +0100
From:	Andi Kleen <andi@...stfloor.org>
To:	Theodore Tso <tytso@....edu>,
	Jörn Engel <joern@...fs.org>,
	Andi Kleen <andi@...stfloor.org>,
	Johannes Berg <johannes@...solutions.net>,
	KOSAKI Motohiro <kosaki.motohiro@...fujitsu.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Linux Kernel list <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] add b+tree library

> Finally, are b+tree so much better than rbtrees that it would be
> worthwhile to just *replace* rbtrees with b+trees?  Or is the problem

There've been a couple of proposals like this over the years, also
with other data structures like judy trees (which seem to bring
the cache line optimization Joern talks about to even more extreme).
splay trees seem to be also a popular suggestion, although they've
considered dubious by other people (including me). Another
alternative would be skip lists. 

Also I don't remember there was ever a big discussion about
rbtrees vs other trees -- it was just that Andrea liked
them and added a convenient library and some point and other
people found it convenient too and started using it.

But it's unclear how much all that would really help.

I always thought it might be advanteous to look at a little
more abstract interface for the existing rbtree users (shouldn't
be that hard, the interface is already not too bad) and then just 
let some students implement a couple of backend data structures
for that interface and then run some benchmarks.

I don't think it's a good idea to add a b*tree library
and use it only from a few users though. After all it's
a lot of code and that should have a clear benefit.

-Andi
-- 
ak@...ux.intel.com
--
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/