[prev in list] [next in list] [prev in thread] [next in thread] 

List:       linux-ext4
Subject:    [Ext2-devel] Re: [PATCH 1/3] ext3 reservation remove stale window fix
From:       Matt Mackall <mpm () selenic ! com>
Date:       2004-10-19 1:32:39
Message-ID: 20041019013239.GT31237 () waste ! org
[Download RAW message or body]

On Mon, Oct 18, 2004 at 06:11:16PM -0700, Mingming Cao wrote:
> On Mon, 2004-10-18 at 16:41, Matt Mackall wrote:
> > On Mon, Oct 18, 2004 at 03:55:04PM -0700, Mingming Cao wrote:
> > > 
> > > Before we changed the per-filesystem reservations from a linked list
> > > to a red-black tree, in order to speed up the linear search from the
> > > list head, we keep the current(stale) reservation window as a
> > > reference pointer to skip the nodes prior to the current/stale
> > > window node, when failed to allocate a new window in current group
> > > and try to do allocation in next group.
> > 
> > One wonders whether a prio tree of the sort used by the current VMA
> > searching code would be a better match to the problem than the
> > red-black approach.
> 
> Could you please elaborate more? I think the current VMA code is using
> red-black tree in their searching code(find_vma()).

I was thinking of the priority search tree stuff in mm/prio_tree.c.
But on further reflection, they're not really advantageous here as the
windows in question are non-overlapping and the RB approach looks
perfectly sensible.

-- 
Mathematics is the supreme nostalgia of our time.


-------------------------------------------------------
This SF.net email is sponsored by: IT Product Guide on ITManagersJournal
Use IT products in your business? Tell us what you think of them. Give us
Your Opinions, Get Free ThinkGeek Gift Certificates! Click to find out more
http://productguide.itmanagersjournal.com/guidepromo.tmpl
_______________________________________________
Ext2-devel mailing list
Ext2-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/ext2-devel
[prev in list] [next in list] [prev in thread] [next in thread]