On Sunday, 8 April 2007 01:42, Nigel Cunningham wrote: > 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" <[EMAIL > > > > PROTECTED]> 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.
Well, you use open-coded lists. If you used list.h lists, the numbers would be different. :-) > 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). Isn't the appending one actually linear worst-case? > If for some reason swap was allocated out of order, I might need to traverse > the whole chain from the start. Exactly. > 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. In swsusp the deletions are needed only if there's an error. > 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. The insertion also uses searching and in fact I don't really care for anything else. Greetings, Rafael - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/