diff options
Diffstat (limited to 'libbacktrace')
| -rw-r--r-- | libbacktrace/ChangeLog | 4 | ||||
| -rw-r--r-- | libbacktrace/sort.c | 6 |
2 files changed, 10 insertions, 0 deletions
diff --git a/libbacktrace/ChangeLog b/libbacktrace/ChangeLog index abbea3ed6e8..8a1a8e74a32 100644 --- a/libbacktrace/ChangeLog +++ b/libbacktrace/ChangeLog @@ -1,3 +1,7 @@ +2014-03-07 Ian Lance Taylor <iant@google.com> + + * sort.c (backtrace_qsort): Use middle element as pivot. + 2014-03-06 Ian Lance Taylor <iant@google.com> * sort.c: New file. diff --git a/libbacktrace/sort.c b/libbacktrace/sort.c index 88f92314224..8c4760f8aa3 100644 --- a/libbacktrace/sort.c +++ b/libbacktrace/sort.c @@ -69,6 +69,12 @@ backtrace_qsort (void *basearg, size_t count, size_t size, 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++) { |