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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.