From: "H. Peter Anvin" <hpa@zytor.com>
To: Eric Paris <eparis@redhat.com>
Cc: Kyle McMartin <kyle@mcmartin.ca>,
James Morris <jmorris@namei.org>,
Christoph Hellwig <hch@infradead.org>,
kernel@lists.fedoraproject.org, Mimi Zohar <zohar@us.ibm.com>,
warthog9@kernel.org, Dave Chinner <david@fromorbit.com>,
linux-kernel@vger.kernel.org, Serge Hallyn <serue@us.ibm.com>,
Linus Torvalds <torvalds@linux-foundation.org>,
Andrew Morton <akpm@linux-foundation.org>,
mingo@elte.hu
Subject: Re: ima: use of radix tree cache indexing == massive waste of memory?
Date: Mon, 18 Oct 2010 11:06:16 -0700 [thread overview]
Message-ID: <4CBC8C98.1090802@zytor.com> (raw)
In-Reply-To: <1287420534.2530.67.camel@localhost.localdomain>
On 10/18/2010 09:48 AM, Eric Paris wrote:
>
> 1) IMA uses radix trees which end up wasting 500 bytes per inode because
> the key is too sparse. I've got a patch which uses an rbtree instead
> I'm testing and will send along shortly. I found it funny working on
> the patch to see that Documentation/rbtree.txt says "This differs from
> radix trees (which are used to efficiently store sparse arrays and thus
> use long integer indexes to insert/access/delete nodes)" Which flys in
> the face of this report.
>
Radix trees can efficiently store data associated with sparse keys *as
long as the keys are clustered*. For random key distributions, they
perform horribly.
-hpa
next prev parent reply other threads:[~2010-10-18 18:08 UTC|newest]
Thread overview: 52+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-10-16 6:52 ima: use of radix tree cache indexing == massive waste of memory? Dave Chinner
2010-10-16 19:20 ` Christoph Hellwig
2010-10-16 21:10 ` H. Peter Anvin
2010-10-17 0:35 ` Dave Chinner
2010-10-17 0:54 ` J.H.
2010-10-17 2:11 ` Dave Chinner
2010-10-18 18:12 ` J.H.
2010-10-17 0:49 ` Christoph Hellwig
2010-10-17 1:09 ` Kyle McMartin
2010-10-17 1:13 ` Christoph Hellwig
2010-10-17 5:49 ` Ingo Molnar
2010-10-17 5:40 ` Ingo Molnar
2010-10-17 18:46 ` Christoph Hellwig
2010-10-18 0:49 ` James Morris
2010-10-18 6:25 ` Kyle McMartin
2010-10-18 6:36 ` Andrew Morton
2010-10-18 9:29 ` Dave Chinner
2010-10-18 13:31 ` Mimi Zohar
2010-10-18 20:50 ` Ware, Ryan R
2010-10-26 7:31 ` Pavel Machek
2010-10-18 16:03 ` Mimi Zohar
2010-10-18 19:24 ` John Stoffel
2010-10-18 16:46 ` Ryan Ware
2010-10-18 16:48 ` Eric Paris
2010-10-18 17:10 ` Kyle McMartin
2010-10-18 17:34 ` Kyle McMartin
2010-10-18 17:56 ` Linus Torvalds
2010-10-18 18:13 ` Eric Paris
2010-10-18 18:19 ` Ingo Molnar
2010-10-18 18:43 ` Eric Paris
2010-10-19 0:58 ` Eric Paris
2010-10-18 18:06 ` H. Peter Anvin [this message]
2010-10-18 18:11 ` Ingo Molnar
2010-10-18 18:13 ` H. Peter Anvin
2010-10-25 13:18 ` Pavel Machek
2010-10-17 5:57 ` Mimi Zohar
2010-10-17 11:02 ` Peter Zijlstra
2010-10-17 13:12 ` Eric Paris
2010-10-17 13:59 ` Peter Zijlstra
2010-10-17 14:04 ` Peter Zijlstra
2010-10-17 14:16 ` Eric Paris
2010-10-18 11:57 ` Peter Zijlstra
2010-10-18 14:59 ` Ted Ts'o
2010-10-18 15:02 ` Peter Zijlstra
2010-10-18 15:02 ` Eric Paris
2010-10-17 18:52 ` Christoph Hellwig
2010-10-18 16:44 ` Ryan Ware
2010-10-18 0:07 ` Dave Chinner
2010-10-17 14:09 ` Mimi Zohar
2010-10-17 18:49 ` Christoph Hellwig
2010-10-17 19:39 ` Pavel Machek
-- strict thread matches above, loose matches on Subject: below --
2010-10-18 15:09 Christoph Hellwig
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4CBC8C98.1090802@zytor.com \
--to=hpa@zytor.com \
--cc=akpm@linux-foundation.org \
--cc=david@fromorbit.com \
--cc=eparis@redhat.com \
--cc=hch@infradead.org \
--cc=jmorris@namei.org \
--cc=kernel@lists.fedoraproject.org \
--cc=kyle@mcmartin.ca \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
--cc=serue@us.ibm.com \
--cc=torvalds@linux-foundation.org \
--cc=warthog9@kernel.org \
--cc=zohar@us.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox