The new libbacktrace sort routine has, no doubt, many flaws, but one is
quite significant. The backtrace data tends to be roughly sorted in
practice (though unfortunately not perfectly sorted). By pivoting on
the first element in the array, the sort routine was tending to maximize
the number of recursive steps. This patch uses the middle element array
as the pivot. This reduced the backtrace time on a large executable by
two orders of magnitude.
Bootstrapped and ran Go and sanitizer testsuites on
x86_64-unknown-linux-gnu. Committed to mainline.
Ian
2014-03-07 Ian Lance Taylor <i...@google.com>
* sort.c (backtrace_qsort): Use middle element as pivot.
Index: sort.c
===================================================================
--- sort.c (revision 208402)
+++ sort.c (working copy)
@@ -69,6 +69,12 @@ backtrace_qsort (void *basearg, size_t c
if (count < 2)
return;
+ /* The symbol table and DWARF tables, which is all we use this
+ routine for, tend to be roughly sorted. Pick the middle element
+ in the array as our pivot point, so that we are more likely to
+ cut the array in half for each recursion step. */
+ swap (base, base + (count / 2) * size, size);
+
mid = 0;
for (i = 1; i < count; i++)
{
