From: Andrea Arcangeli <aarcange@redhat.com>
To: Andrew Morton <akpm@linux-foundation.org>
Cc: Rik van Riel <riel@redhat.com>,
linux-mm@kvack.org, linux-kernel@vger.kernel.org,
Mel Gorman <mel@csn.ul.ie>, Johannes Weiner <hannes@cmpxchg.org>,
KOSAKI Motohiro <kosaki.motohiro@gmail.com>,
hughd@google.com
Subject: Re: [PATCH -mm 2/2] mm: do not reset mm->free_area_cache on every single munmap
Date: Tue, 20 Mar 2012 20:00:55 +0100 [thread overview]
Message-ID: <20120320190055.GZ24602@redhat.com> (raw)
In-Reply-To: <20120223135614.7c4e02db.akpm@linux-foundation.org>
On Thu, Feb 23, 2012 at 01:56:14PM -0800, Andrew Morton wrote:
> We've been playing whack-a-mole with this search for many years. What
> about developing a proper data structure with which to locate a
> suitable-sized hole in O(log(N)) time?
I intended to implement it a couple of years ago.
It takes a change to the rbtree code so that when rb_erase and
rb_insert_color are called, proper methods are called to notify the
caller that there's been a rotation (probably calling a new
rb_insert_color_with_metadata(&method(left_rot, right_rot)) ). So that
these methods can update the new status of the tree. So you can keep
the "max" hole information for the left and right side of the tree at
the top node, and if the left side of the tree from the top doesn't
have a big enough max hole you take the right immediately (if if fits)
skipping over everything that isn't interesting and you keep doing so
until the max hole on right or left fits the size of the allocation
request (and then you find what you were searching for in vma and
vma->vm_next). It's very tricky but it should be possible. Still it
would remain generic code in rbtree.c, not actually knowing it's the
max hole info we're collecting at the root node for left and right
nodes. Maybe only the left side of the tree max hole needs to be
collected, not having the right size only means a worst case O(log(N))
walk on the tree (taking ->right all the time 'till the leaf) so it'd
be perfectly ok and it may simplify things a lot having only the max
hole on the left.
I'm too busy optimizing AutoNUMA even further to delve into this but I
hope somebody implements it. I thought about exactly this when I've
seen these patches floating around, so I'm glad you mentioned it.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2012-03-20 19:01 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-02-23 19:54 [PATCH -mm 0/2] speed up arch_get_unmapped_area Rik van Riel
2012-02-23 19:56 ` [PATCH -mm 1/2] mm: fix quadratic behaviour in get_unmapped_area_topdown Rik van Riel
2012-02-23 21:50 ` Andrew Morton
2012-02-23 21:57 ` Johannes Weiner
2012-02-23 20:00 ` [PATCH -mm 2/2] mm: do not reset mm->free_area_cache on every single munmap Rik van Riel
2012-02-23 21:56 ` Andrew Morton
2012-02-27 16:12 ` Rik van Riel
2012-03-20 18:32 ` Rik van Riel
2012-03-20 19:00 ` Andrea Arcangeli [this message]
2012-03-20 19:06 ` Rik van Riel
2012-02-23 21:57 ` Andi Kleen
2012-02-27 16:13 ` Rik van Riel
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=20120320190055.GZ24602@redhat.com \
--to=aarcange@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=hannes@cmpxchg.org \
--cc=hughd@google.com \
--cc=kosaki.motohiro@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mel@csn.ul.ie \
--cc=riel@redhat.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;
as well as URLs for NNTP newsgroup(s).