From: George Spelvin <lkml@sdf.org>
To: linux-kernel@vger.kernel.org
Cc: George Spelvin <lkml@sdf.org>,
Andrew Morton <akpm@linux-foundation.org>,
Andrey Abramov <st5pub@yandex.ru>,
Geert Uytterhoeven <geert@linux-m68k.org>,
Daniel Wagner <daniel.wagner@siemens.com>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Don Mullis <don.mullis@gmail.com>,
Dave Chinner <dchinner@redhat.com>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Subject: [PATCH 3/5] lib/sort: Avoid indirect calls to built-in swap
Date: Thu, 21 Feb 2019 08:21:42 +0000 [thread overview]
Message-ID: <a98fba2d48042fa5a2defca4ef694a35ee227510.1552097842.git.lkml@sdf.org> (raw)
In-Reply-To: <cover.1552097842.git.lkml@sdf.org>
Similar to what's being done in the net code, this takes advantage of
the fact that most invocations use only a few common swap functions, and
replaces indirect calls to them with (highly predictable) conditional
branches. (The downside, of course, is that if you *do* use a custom
swap function, there are a few additional (highly predictable) conditional
branches on the code path.)
This actually *shrinks* the x86-64 code, because it inlines the various
swap functions inside do_swap, eliding function prologues & epilogues.
x86-64 code size 770 -> 709 bytes (-61)
Signed-off-by: George Spelvin <lkml@sdf.org>
---
lib/sort.c | 45 ++++++++++++++++++++++++++++++++++++---------
1 file changed, 36 insertions(+), 9 deletions(-)
diff --git a/lib/sort.c b/lib/sort.c
index 2aef4631e7d3..226a8c7e4b9a 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -117,6 +117,33 @@ static void generic_swap(void *a, void *b, int size)
} while (n);
}
+typedef void (*swap_func_t)(void *a, void *b, int size);
+
+/*
+ * The values are arbitrary as long as they can't be confused with
+ * a pointer, but small integers make for the smallest compare
+ * instructions.
+ */
+#define U64_SWAP (swap_func_t)0
+#define U32_SWAP (swap_func_t)1
+#define GENERIC_SWAP (swap_func_t)2
+
+/*
+ * The function pointer is last to make tail calls most efficient if the
+ * compiler decides not to inline this function.
+ */
+static void do_swap(void *a, void *b, int size, swap_func_t swap_func)
+{
+ if (swap_func == U64_SWAP)
+ u64_swap(a, b, size);
+ else if (swap_func == U32_SWAP)
+ u32_swap(a, b, size);
+ else if (swap_func == GENERIC_SWAP)
+ generic_swap(a, b, size);
+ else
+ swap_func(a, b, size);
+}
+
/**
* parent - given the offset of the child, find the offset of the parent.
* @i: the offset of the heap element whose parent is sought. Non-zero.
@@ -151,10 +178,10 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
* @cmp_func: pointer to comparison function
* @swap_func: pointer to swap function or NULL
*
- * This function does a heapsort on the given array. You may provide a
- * swap_func function if you need to do something more than a memory copy
- * (e.g. fix up pointers or auxiliary data), but the built-in swap isn't
- * usually a bottleneck.
+ * This function does a heapsort on the given array. You may provide
+ * a swap_func function if you need to do something more than a memory
+ * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
+ * avoids a slow retpoline and so is significantly faster.
*
* Sorting time is O(n log n) both on average and worst-case. While
* qsort is about 20% faster on average, it suffers from exploitable
@@ -174,11 +201,11 @@ void sort(void *base, size_t num, size_t size,
if (!swap_func) {
if (alignment_ok(base, size, 8))
- swap_func = u64_swap;
+ swap_func = U64_SWAP;
else if (alignment_ok(base, size, 4))
- swap_func = u32_swap;
+ swap_func = U32_SWAP;
else
- swap_func = generic_swap;
+ swap_func = GENERIC_SWAP;
}
/*
@@ -194,7 +221,7 @@ void sort(void *base, size_t num, size_t size,
if (a) /* Building heap: sift down --a */
a -= size;
else if (n -= size) /* Sorting: Extract root to --n */
- swap_func(base, base + n, size);
+ do_swap(base, base + n, size, swap_func);
else /* Sort complete */
break;
@@ -221,7 +248,7 @@ void sort(void *base, size_t num, size_t size,
c = b; /* Where "a" belongs */
while (b != a) { /* Shift it into place */
b = parent(b, lsbit, size);
- swap_func(base + b, base + c, size);
+ do_swap(base + b, base + c, size, swap_func);
}
}
}
--
2.20.1
next prev parent reply other threads:[~2019-03-09 3:21 UTC|newest]
Thread overview: 44+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-03-09 2:17 [PATCH 0/5] lib/sort & lib/list_sort: faster and smaller George Spelvin
2019-02-21 6:30 ` [PATCH 1/5] lib/sort: Make swap functions more generic George Spelvin
[not found] ` <20190309140653.GO9224@smile.fi.intel.com>
2019-03-09 15:53 ` lkml
2019-03-09 20:19 ` Andrey Abramov
2019-03-14 9:29 ` Andy Shevchenko
2019-03-14 10:09 ` George Spelvin
2019-03-14 10:41 ` Geert Uytterhoeven
2019-03-14 11:53 ` George Spelvin
2019-03-14 12:18 ` Andy Shevchenko
2019-03-14 19:59 ` Andrey Abramov
2019-03-15 3:35 ` George Spelvin
2019-03-15 8:27 ` Geert Uytterhoeven
2019-03-14 10:11 ` George Spelvin
2019-03-09 21:02 ` George Spelvin
2019-03-13 21:23 ` Rasmus Villemoes
2019-03-13 22:02 ` Geert Uytterhoeven
2019-03-13 23:15 ` George Spelvin
2019-02-21 8:21 ` [PATCH 2/5] lib/sort: Use more efficient bottom-up heapsort variant George Spelvin
2019-03-13 22:29 ` Rasmus Villemoes
2019-03-14 0:03 ` George Spelvin
2019-03-14 0:15 ` Rasmus Villemoes
2019-02-21 8:21 ` George Spelvin [this message]
2019-03-05 3:06 ` [PATCH 4/5] lib/list_sort: Simplify and remove MAX_LIST_LENGTH_BITS George Spelvin
2019-03-10 21:54 ` Rasmus Villemoes
2019-03-10 22:29 ` George Spelvin
2019-03-14 9:10 ` Andy Shevchenko
2019-03-14 9:41 ` George Spelvin
2019-03-15 4:33 ` George Spelvin
2019-03-15 8:20 ` Geert Uytterhoeven
2019-03-15 10:23 ` George Spelvin
2019-03-15 12:57 ` Geert Uytterhoeven
2019-03-15 16:59 ` George Spelvin
2019-03-15 17:47 ` Geert Uytterhoeven
2019-03-15 18:53 ` Andrey Abramov
2019-03-15 19:06 ` Andy Shevchenko
2019-03-15 19:23 ` Andrey Abramov
2019-03-15 19:56 ` Andy Shevchenko
2019-03-16 3:49 ` George Spelvin
2019-03-05 5:58 ` [PATCH 5/5] lib/list_sort: Optimize number of calls to comparison function George Spelvin
2019-03-13 23:28 ` Rasmus Villemoes
2019-03-14 1:58 ` George Spelvin
2019-06-21 23:12 ` Rasmus Villemoes
2019-12-08 8:01 ` George Spelvin
2019-03-15 19:54 ` [PATCH 0/5] lib/sort & lib/list_sort: faster and smaller Andrey Abramov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=a98fba2d48042fa5a2defca4ef694a35ee227510.1552097842.git.lkml@sdf.org \
--to=lkml@sdf.org \
--cc=akpm@linux-foundation.org \
--cc=andriy.shevchenko@linux.intel.com \
--cc=daniel.wagner@siemens.com \
--cc=dchinner@redhat.com \
--cc=don.mullis@gmail.com \
--cc=geert@linux-m68k.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@rasmusvillemoes.dk \
--cc=st5pub@yandex.ru \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).