diff options
| author | Ian Lance Taylor <iant@google.com> | 2014-03-07 15:52:48 +0000 |
|---|---|---|
| committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2014-03-07 15:52:48 +0000 |
| commit | dbe2084238e45a60aa6e6b0469bd9e0c4ef15b2f (patch) | |
| tree | 03f1ea0fd39ee7d425bc94e866f3ace1f85b7c09 /libbacktrace | |
| parent | bc65bdd5b48902d7d544ef88f6ab96158e6e8064 (diff) | |
| download | gcc-dbe2084238e45a60aa6e6b0469bd9e0c4ef15b2f.tar.gz | |
* sort.c (backtrace_qsort): Use middle element as pivot.
From-SVN: r208403
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++) { |