search

ianlancetaylor / libbacktrace

A C library that may be linked into a C/C++ program to produce symbolic backtraces
Other
944 stars 220 forks source link

Non-recursive shell sort #101

Closed funny-falcon closed 1 year ago

funny-falcon commented 1 year ago

Shell-sort is straight-forward non-recursive algorithm. It is comparable in performance to naive qsort up to million items.

ianlancetaylor commented 1 year ago

The libbacktrace sort time is a big percentage of its performance on large programs. I have not seen any complaints about running out of stack space during the sort. So this doesn't seem like a desirable change.

Have you run any benchmarks on large programs?

funny-falcon commented 1 year ago

I've integrated libbacktrace into PostgreSQL, and by 'perf record' shell sort is just a bit slower (3-7%). (ie 12% vs 13% of total cpu usage).

To be honestly, looking on swap function it was hard to guess sorting is performance critical.

Given all array elements passed to backtrace_qsort are pointer-aligned, I've made PR #102. It makes sorting 2.5 times faster.