Re: [RFC][PATCH -mm] swsusp: Use rbtree for tracking allocated swap

[Nigel Cunningham <nigel@nigel.suspend2.net>]

Hi.

On Sun, 2007-04-08 at 01:13 +0200, Rafael J. Wysocki wrote:
> On Sunday, 8 April 2007 00:31, Nigel Cunningham wrote:
> > Hi.
> > 
> > On Sat, 2007-04-07 at 15:06 -0700, Andrew Morton wrote:
> > > On Sat, 7 Apr 2007 23:20:39 +0200 "Rafael J. Wysocki" <rjw@sisk.pl> wrote:
> > > 
> > > > This should allow us to reduce the memory usage, practically always, and
> > > > improve performance.
> > > 
> > > And does it?
> 
> Yes.  There are theoretical corner cases in which it may be less efficient
> than the current approach, but in the usual situation it is _much_ better.
> 
> > It will. I've been using extents for ages, for the same reasons. I don't
> > put them in an rb_tree because I view it as less than most efficient,
> 
> Actually, I don't agree with that.  In the normal situation (ie. one extent is
> needed) there is no difference as far as the memory usage or performance
> are concerned, but if there are more extents, the rbtree should be more
> efficient.

I don't think it's worth having a big discussion over, but let me give
you the details, which you can then feel free to ignore :)

The rb_node struct adds an unsigned long and two struct rb_node *
pointers. My extents use one struct extent * pointer. The difference is
thus 12/24 bytes per extent (32/64 bits) vs 20/40. In the normal
situation, not worth worrying about, but I'm also using these for
recording the sectors we write too, and thinking about swap files and
multiple swap devices. Nearly double the memory use bites more as you
get more extents.

Insertion cost for rb_node includes keeping the tree balanced. For
extents, I start with the location of the last insertion to minimise the
cost, so insertion time is usually virtually zero (inc max of last
extent or append a new one). If for some reason swap was allocated out
of order, I might need to traverse the whole chain from the start.

Normal usage in both cases is simply iterating through the list, so I
guess the cost would be approximately the same.

Deletion could would include rebalancing for the rb_nodes.

Code cost is a gain for you - you're leveraging existing code, I'm
adding a bit more. extent.c is 300 lines including code for serialising
the chains in an image header and iterating through a group of chains
(multiple swap devices support).

rb_nodes seem to be the wrong solution to me because we generally don't
care about searching. We care about minimising memory usage and
maximising the speed of iteration, insertion and deletion. I believe
I've managed to do that with a singly linked, sorted list.

That said, we've agreed that we're normally talking about a small number
of extents, so it's probably not worth the bandwidth I've already
spent :)

Regards,

Nigel

Attachment: signature.asc
Description: This is a digitally signed message part