Re: [PATCH 2.6.28 1/2] memory: improve find_vma

[Hugh Dickins]

On Thu, 22 Jan 2009, Daniel Lowengrub wrote:
> The goal of this patch is to improve the efficiency of the find_vma
> function in mm/mmap.c. The function first checks whether the vma
> stored in the cache is the one it's looking for. Currently, it's
> possible for the cache to be correct and still get rejected because
> the function checks whether the given address is inside the vma in the
> cache, not whether the cached vma is the smallest one that's bigger
> than the address.  To solve this problem I turned the list of vma's
> into a doubly linked list, and using that list made a function that
> can check if a given vma is the one that find_vma is looking for.
> This gives a greater number of cache hits than the standerd method.
> The doubly linked list can be used to optimize other parts of the
> memory management as well.  I'll implement some of those possibilities
> in the next patch.
> Signed-off-by: Daniel Lowengrub <lowdanie@xxxxxxxxx>

Do you have some performance figures to support this patch?
Some of the lmbench tests may be appropriate.

The thing is, expanding vm_area_struct to include another pointer
will have its own cost, which may well outweigh the efficiency
(in one particular case) which you're adding.  Expanding mm_struct
for this would be much more palatable, but I don't think that flies.

And it seems a little greedy to require both an rbtree and a doubly
linked list for working our way around the vmas.

I suspect that originally your enhancement would only have hit when
extending the stack: which I guess isn't enough to justify the cost.
But it could well be that unmapped area handling has grown more
complex down the years, and you get some hits now from that.

You mention using the doubly linked list to optimize some other parts
of mm too: I guess those interfaces where we have to pass around prev
would be simplified, are you thinking of those, or something else?

(I don't think we need unmap_vmas to go backwards!)

Hugh
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/