[PATCH] low performance of lib/sort.c , kernel 2.6.18

* [PATCH] low performance of lib/sort.c , kernel 2.6.18
@ 2006-09-28 15:18 keios
  2006-09-28 22:33 ` Matt Mackall
  0 siblings, 1 reply; 4+ messages in thread
From: keios @ 2006-09-28 15:18 UTC (permalink / raw)
  To: linux-kernel; +Cc: Andrew Morton, Matt Mackall

It is a non-standard heap-sort algorithm implementation because the
index of child node is wrong . The sort function still outputs right
result, but the performance is O( n * ( log(n) + 1 ) ) , about 10% ~
20% worse than standard algorithm .

Signed-off-by: keios <keios.cn@gmail.com>
-----
diff -Nraup a/lib/sort.c b/lib/sort.c

--- a/lib/sort.c	2006-09-20 11:42:06.000000000 +0800
+++ b/lib/sort.c	2006-09-27 21:26:38.000000000 +0800
@@ -49,15 +49,15 @@ void sort(void *base, size_t num, size_t
 	  void (*swap)(void *, void *, int size))
 {
 	/* pre-scale counters for performance */
-	int i = (num/2) * size, n = num * size, c, r;
+	int i = (num/2 - 1) * size, n = num * size, c, r;

 	if (!swap)
 		swap = (size == 4 ? u32_swap : generic_swap);

 	/* heapify */
 	for ( ; i >= 0; i -= size) {
-		for (r = i; r * 2 < n; r  = c) {
-			c = r * 2;
+		for (r = i; r * 2 + size < n; r  = c) {
+			c = r * 2 + size;
 			if (c < n - size && cmp(base + c, base + c + size) < 0)
 				c += size;
 			if (cmp(base + r, base + c) >= 0)
@@ -69,8 +69,8 @@ void sort(void *base, size_t num, size_t
 	/* sort */
 	for (i = n - size; i >= 0; i -= size) {
 		swap(base, base + i, size);
-		for (r = 0; r * 2 < i; r = c) {
-			c = r * 2;
+		for (r = 0; r * 2 + size < i; r = c) {
+			c = r * 2 + size;
 			if (c < i - size && cmp(base + c, base + c + size) < 0)
 				c += size;
 			if (cmp(base + r, base + c) >= 0)

^ permalink raw reply	[flat|nested] 4+ messages in thread