Propose C Metaprogramming-based qsort as GNU extension

[Daniel Santos]

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