On Mon, Feb 16, 2015 at 03:15:07PM -0600, Daniel Santos wrote:
As part of my work on a paper on C Metaprogramming with gcc, I have
implemented a sqort/insertion sort algorithm based off of the legacy
glibc implementation (when msort is not used) who's performance far
exceeds the current implementation. I have opened an enhancement bug
here https://sourceware.org/bugzilla/show_bug.cgi?id=17941 with
details about this, and was told I need to talk to you guys.
In short, a basic benchmark shows an average performance increase
83% (16k of data, using element sizes from 1 to 8192 bytes). These
are techniques that I appear to have invented in 2012; I haven't run
into anybody else doing it just yet, but I hope it will catch on.
Currently I only know this to work on GCC, but it may be possible
that other compilers have enough support (in their extensions) to
make it possible.
The basic theory of operation is that by exploiting
-findirect-inline, and attributes always_inline & flatten (in some
cases), we force the compiler to inline a larger function than would
normally be considered beneficial -- this is where instantiation of
the "pseudo-template function" (as I call it) occurs. In this way a
more efficient sort function is generated, because we know at
compile-time the exact size and alignment of data elements and we
can inline the compar function. We can even decide if we'll be doing
a direct or indirect sort at compile-time, tune stack size, etc. The
code its self needs more cleanup to be ready to integrate into
glibc, although the algorithm appears to now be quite efficient and
error-free.
The main question is really where it belongs. The Boost project was
started as a place for experimental libraries, many of which ended
up in a later C++ standard. As I see it, a similar process must take
place with C metaprograming, as it provides a powerful tool to
improve performance in programs, libraries and system-level code. I
thought that glibc might be a nice place for this because there are
already so many extensions. This is slightly different however,
because we aren't just providing new functions, but new
metafunctions.
Either way, I would very much like this work to fall under the GNU
umbrella if at all possible.
Daniel
Something like this is on my backlog. You can start with patch with
always_inline qsort template in header surrounded by
# if __GNUC_PREREQ (4, 8)
You do several basic optimizations. I wanted to do more, a hard part
would make gcc recognize different comparison functions. In most cases
radixsort is faster than quick/mergesort.