diff options
| -rw-r--r-- | lib/list_sort.c | 113 |
1 files changed, 91 insertions, 22 deletions
diff --git a/lib/list_sort.c b/lib/list_sort.c index ba9431bcac0b..06e900c5587b 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -107,11 +107,6 @@ static void merge_final(void *priv, cmp_func cmp, struct list_head *head, * @head: the list to sort * @cmp: the elements comparison function * - * This function implements a bottom-up merge sort, which has O(nlog(n)) - * complexity. We use depth-first order to take advantage of cacheing. - * (E.g. when we get to the fourth element, we immediately merge the - * first two 2-element lists.) - * * The comparison funtion @cmp must return > 0 if @a should sort after * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should * sort before @b *or* their original order should be preserved. It is @@ -131,6 +126,60 @@ static void merge_final(void *priv, cmp_func cmp, struct list_head *head, * if (a->middle != b->middle) * return a->middle > b->middle; * return a->low > b->low; + * + * + * This mergesort is as eager as possible while always performing at least + * 2:1 balanced merges. Given two pending sublists of size 2^k, they are + * merged to a size-2^(k+1) list as soon as we have 2^k following elements. + * + * Thus, it will avoid cache thrashing as long as 3*2^k elements can + * fit into the cache. Not quite as good as a fully-eager bottom-up + * mergesort, but it does use 0.2*n fewer comparisons, so is faster in + * the common case that everything fits into L1. + * + * + * The merging is controlled by "count", the number of elements in the + * pending lists. This is beautiully simple code, but rather subtle. + * + * Each time we increment "count", we set one bit (bit k) and clear + * bits k-1 .. 0. Each time this happens (except the very first time + * for each bit, when count increments to 2^k), we merge two lists of + * size 2^k into one list of size 2^(k+1). + * + * This merge happens exactly when the count reaches an odd multiple of + * 2^k, which is when we have 2^k elements pending in smaller lists, + * so it's safe to merge away two lists of size 2^k. + * + * After this happens twice, we have created two lists of size 2^(k+1), + * which will be merged into a list of size 2^(k+2) before we create + * a third list of size 2^(k+1), so there are never more than two pending. + * + * The number of pending lists of size 2^k is determined by the + * state of bit k of "count" plus two extra pieces of information: + * - The state of bit k-1 (when k == 0, consider bit -1 always set), and + * - Whether the higher-order bits are zero or non-zero (i.e. + * is count >= 2^(k+1)). + * There are six states we distinguish. "x" represents some arbitrary + * bits, and "y" represents some arbitrary non-zero bits: + * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k + * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k + * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k + * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k + * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k + * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k + * (merge and loop back to state 2) + * + * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because + * bit k-1 is set while the more significant bits are non-zero) and + * merge them away in the 5->2 transition. Note in particular that just + * before the 5->2 transition, all lower-order bits are 11 (state 3), + * so there is one list of each smaller size. + * + * When we reach the end of the input, we merge all the pending + * lists, from smallest to largest. If you work through cases 2 to + * 5 above, you can see that the number of elements we merge with a list + * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to + * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1). */ __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, @@ -152,33 +201,53 @@ void list_sort(void *priv, struct list_head *head, * pointers are not maintained. * - pending is a prev-linked "list of lists" of sorted * sublists awaiting further merging. - * - Each of the sorted sublists is power-of-two in size, - * corresponding to bits set in "count". + * - Each of the sorted sublists is power-of-two in size. * - Sublists are sorted by size and age, smallest & newest at front. + * - There are zero to two sublists of each size. + * - A pair of pending sublists are merged as soon as the number + * of following pending elements equals their size (i.e. + * each time count reaches an odd multiple of that size). + * That ensures each later final merge will be at worst 2:1. + * - Each round consists of: + * - Merging the two sublists selected by the highest bit + * which flips when count is incremented, and + * - Adding an element from the input as a size-1 sublist. */ do { size_t bits; - struct list_head *cur = list; + struct list_head **tail = &pending; - /* Extract the head of "list" as a single-element list "cur" */ - list = list->next; - cur->next = NULL; + /* Find the least-significant clear bit in count */ + for (bits = count; bits & 1; bits >>= 1) + tail = &(*tail)->prev; + /* Do the indicated merge */ + if (likely(bits)) { + struct list_head *a = *tail, *b = a->prev; - /* Do merges corresponding to set lsbits in count */ - for (bits = count; bits & 1; bits >>= 1) { - cur = merge(priv, (cmp_func)cmp, pending, cur); - pending = pending->prev; /* Untouched by merge() */ + a = merge(priv, (cmp_func)cmp, b, a); + /* Install the merged result in place of the inputs */ + a->prev = b->prev; + *tail = a; } - /* And place the result at the head of "pending" */ - cur->prev = pending; - pending = cur; + + /* Move one element from input list to pending */ + list->prev = pending; + pending = list; + list = list->next; + pending->next = NULL; count++; - } while (list->next); + } while (list); + + /* End of input; merge together all the pending lists. */ + list = pending; + pending = pending->prev; + for (;;) { + struct list_head *next = pending->prev; - /* Now merge together last element with all pending lists */ - while (pending->prev) { + if (!next) + break; list = merge(priv, (cmp_func)cmp, pending, list); - pending = pending->prev; + pending = next; } /* The final merge, rebuilding prev links */ merge_final(priv, (cmp_func)cmp, head, pending, list); |