From: Rik van Riel <riel@redhat.com>
To: Rajesh Venkatasubramanian <vrajesh@umich.edu>
Cc: Andrea Arcangeli <andrea@suse.de>, <akpm@osdl.org>,
<torvalds@osdl.org>, <hugh@veritas.com>, <mbligh@aracnet.com>,
<mingo@elte.hu>, <linux-kernel@vger.kernel.org>,
<linux-mm@kvack.org>
Subject: Re: [RFC][PATCH 1/3] radix priority search tree - objrmap complexity fix
Date: Sun, 21 Mar 2004 23:02:03 -0500 (EST) [thread overview]
Message-ID: <Pine.LNX.4.44.0403212258530.20045-100000@chimarrao.boston.redhat.com> (raw)
In-Reply-To: <Pine.LNX.4.58.0403212241120.8267@rust.engin.umich.edu>
On Sun, 21 Mar 2004, Rajesh Venkatasubramanian wrote:
> > what about the cost of a tree rebalance, is that O(log(N)) like with the
> > rbtrees?
>
> Currently the tree is not balanced, so the tree can be totally skewed
> in some corner cases. However, the maximum height of the tree can be
> only 2 * BITS_PER_LONG.
Fair enough for a radix tree. Andrea, remember that page
tables don't need to be balanced either, for obvious reasons ;)
> Moreover, I have added an optimization to increase the maximum height
> of the tree on demand. The tree height is controlled by keeping track
> of the maximum file offset mapped. If the number of bits required to
> represent the maximum file offset is B, then the height of the tree
> can be only 2 * B.
Nice touch. That should really help keep the cost of the
prio_tree down in the common case.
Your stuff is so much nicer than the kb-trees I was thinking
about a year or two ago ... ;)
--
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
next prev parent reply other threads:[~2004-03-22 4:02 UTC|newest]
Thread overview: 98+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <Pine.LNX.4.44.0403150527400.28579-100000@localhost.localdomain>
2004-03-21 22:10 ` [RFC][PATCH 1/3] radix priority search tree - objrmap complexity fix Rajesh Venkatasubramanian
2004-03-21 22:12 ` [RFC][PATCH 2/3] Dave & Hugh's objrmap patch Rajesh Venkatasubramanian
2004-03-21 22:13 ` [RFC][PATCH 3/3] Covert objrmap to use prio_tree Rajesh Venkatasubramanian
2004-03-21 22:26 ` URL typo Rajesh Venkatasubramanian
2004-03-22 0:46 ` [RFC][PATCH 1/3] radix priority search tree - objrmap complexity fix Andrea Arcangeli
2004-03-22 2:32 ` Rik van Riel
2004-03-22 3:49 ` Rajesh Venkatasubramanian
2004-03-22 4:02 ` Rik van Riel [this message]
2004-03-22 4:21 ` put_super for proc Abhishek Rai
2004-03-22 12:04 ` Maneesh Soni
2004-03-25 22:59 ` [RFC][PATCH 1/3] radix priority search tree - objrmap complexity fix Andrea Arcangeli
2004-03-26 4:06 ` Rajesh Venkatasubramanian
2004-03-26 7:53 ` Andrea Arcangeli
2004-03-26 15:43 ` Rajesh Venkatasubramanian
2004-03-26 17:58 ` Andrea Arcangeli
2004-03-27 19:51 ` Rajesh Venkatasubramanian
2004-03-29 17:22 ` Andrea Arcangeli
2004-03-29 17:50 ` Rajesh Venkatasubramanian
2004-03-29 18:01 ` Andrea Arcangeli
2004-03-29 20:40 ` Andrew Morton
2004-03-29 22:24 ` Hugh Dickins
2004-03-29 22:54 ` Andrea Arcangeli
2004-03-29 23:08 ` William Lee Irwin III
2004-03-29 22:39 ` Andrea Arcangeli
2004-03-29 22:42 ` Andrew Morton
2004-03-31 15:07 ` Andrea Arcangeli
2004-03-31 15:26 ` Andrea Arcangeli
2004-03-31 16:45 ` Hugh Dickins
2004-03-31 17:28 ` Andrea Arcangeli
2004-04-01 0:45 ` Andrea Arcangeli
2004-04-01 1:22 ` Andrew Morton
2004-04-01 1:26 ` Andrea Arcangeli
2004-04-01 1:51 ` Andrew Morton
2004-04-01 2:01 ` Andrea Arcangeli
2004-04-01 5:05 ` Hugh Dickins
2004-04-01 13:35 ` Andrea Arcangeli
2004-04-01 15:09 ` Andrea Arcangeli
2004-04-01 15:15 ` Andrea Arcangeli
2004-04-02 0:15 ` Andrea Arcangeli
2004-04-02 0:52 ` Andrew Morton
2004-04-02 1:06 ` Andrea Arcangeli
2004-04-02 1:03 ` Hugh Dickins
2004-04-02 1:16 ` Andrea Arcangeli
2004-04-02 1:36 ` Andrew Morton
2004-04-02 2:00 ` Andrea Arcangeli
2004-04-02 2:08 ` Andrew Morton
2004-04-02 2:22 ` Andrea Arcangeli
2004-04-02 6:05 ` Christoph Hellwig
2004-04-02 7:07 ` Paul Mackerras
2004-04-02 7:11 ` Christoph Hellwig
2004-04-02 15:28 ` Andrea Arcangeli
2004-04-02 15:22 ` Andrea Arcangeli
2004-04-02 15:27 ` Christoph Hellwig
2004-04-02 15:38 ` Andrea Arcangeli
2004-04-02 15:45 ` Andrea Arcangeli
2004-04-02 9:43 ` Christoph Hellwig
2004-04-02 10:21 ` Marc-Christian Petersen
2004-04-02 10:55 ` Hugh Dickins
2004-04-02 16:46 ` Andrea Arcangeli
2004-04-02 18:59 ` Christoph Hellwig
2004-04-02 19:29 ` Andrea Arcangeli
2004-04-02 19:54 ` Christoph Hellwig
2004-04-02 20:35 ` Andrea Arcangeli
2004-04-03 8:40 ` Christoph Hellwig
2004-04-03 15:20 ` Andrea Arcangeli
2004-04-03 15:59 ` Andrea Arcangeli
2004-04-03 17:02 ` Andrea Arcangeli
2004-04-05 9:59 ` Christoph Hellwig
2004-04-05 12:11 ` Christoph Hellwig
2004-04-05 16:08 ` Andrea Arcangeli
2004-04-06 4:22 ` Andrea Arcangeli
2004-04-06 4:43 ` Andrew Morton
2004-04-06 5:14 ` Christoph Hellwig
2004-04-06 21:54 ` Andrea Arcangeli
2004-04-07 1:39 ` Nathan Scott
2004-04-06 5:16 ` Christoph Hellwig
2004-04-06 16:01 ` Andrea Arcangeli
2004-04-07 1:33 ` Nathan Scott
2004-04-03 17:40 ` Andrea Arcangeli
2004-04-03 20:02 ` Andrew Morton
2004-04-03 23:27 ` Andrea Arcangeli
2004-04-03 23:46 ` Andrew Morton
2004-04-04 0:40 ` Andrea Arcangeli
2004-04-08 19:10 ` Bill Davidsen
2004-04-20 22:29 ` Pavel Machek
2004-04-02 20:13 ` Pavel Machek
2004-04-02 21:42 ` Andrea Arcangeli
2004-04-02 21:45 ` Pavel Machek
2004-04-02 21:49 ` Andrea Arcangeli
2004-03-29 18:12 ` Hugh Dickins
2004-03-29 18:20 ` Andrea Arcangeli
2004-03-29 18:38 ` Christoph Hellwig
2004-03-29 21:30 ` 2.6.5-rc2-aa5 Rajesh Venkatasubramanian
2004-03-29 22:50 ` 2.6.5-rc2-aa5 Andrea Arcangeli
2004-04-05 3:14 ` [RFC][PATCH 1/3] radix priority search tree - objrmap complexity fix Rajesh Venkatasubramanian
2004-04-05 4:42 ` Andrea Arcangeli
2004-03-26 12:26 ` William Lee Irwin III
2004-03-26 19:18 ` Andrea Arcangeli
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=Pine.LNX.4.44.0403212258530.20045-100000@chimarrao.boston.redhat.com \
--to=riel@redhat.com \
--cc=akpm@osdl.org \
--cc=andrea@suse.de \
--cc=hugh@veritas.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mbligh@aracnet.com \
--cc=mingo@elte.hu \
--cc=torvalds@osdl.org \
--cc=vrajesh@umich.edu \
/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;
as well as URLs for NNTP newsgroup(s).