diff options
| author | ian <ian@138bc75d-0d04-0410-961f-82ee72b054a4> | 2014-03-07 15:52:48 +0000 |
|---|---|---|
| committer | ian <ian@138bc75d-0d04-0410-961f-82ee72b054a4> | 2014-03-07 15:52:48 +0000 |
| commit | 30510c702fb70d0d685fc66b2235326372176448 (patch) | |
| tree | 03f1ea0fd39ee7d425bc94e866f3ace1f85b7c09 /libbacktrace | |
| parent | 7b1c573958c4759974356fe9fc1a3499e0b99c21 (diff) | |
| download | gcc-30510c702fb70d0d685fc66b2235326372176448.tar.gz | |
* sort.c (backtrace_qsort): Use middle element as pivot.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@208403 138bc75d-0d04-0410-961f-82ee72b054a4
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++) { |