Hi. On Sun, 2007-04-08 at 18:47 +0200, Rafael J. Wysocki wrote: > 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. :-)
Yes, but I don't need doubly linked lists. > > 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? Worst case would be the swap allocator returning swap pages in reverse order. As you and I both know, that doesn't happen. I first implemented this in 2003. If the worst case actually happened, I would have seen the effect by now :) > > 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. When freeing swap at the end of the cycle? > > 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. Ok :) Nigel - 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/