linux-kernel - Re: [RFC] 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: <20081031201745.GA93714@atlantis.8hz.com>
Date:	Fri, 31 Oct 2008 20:17:45 +0000
From:	Sean Young <sean@...s.org>
To:	linux-kernel@...r.kernel.org
Cc:	Joern Engel <joern@...fs.org>
Subject: Re: [RFC] B+Tree library

On Sun, Oct 26, 2008 at 01:46:44PM +0100, Joern Engel wrote:
> General advantages of btrees are memory density and efficient use of
> cachelines.  Hashtables are either too small and degrade into linked
> list performance, or they are too large and waste memory.  With changing
> workloads, both may be true on the same system.  Rbtrees have a bad
> fanout of less than 2 (they are not actually balanced binary trees),
> hence reading a fairly large number of cachelines to each lookup.

Which reminds me:

find_vma() uses rbtrees. Now I assume find_vma() is called far more than
mmap() and friends. Since avltree are balanced (unlike rbtrees) lookups
will be faster at the expense of extra rotations during updates.

Would patches for avltrees be accepted?

Thanks
Sean
--
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/