Re: Propose C Metaprogramming-based qsort as GNU extension

[OndÅej BÃlka <neleai at seznam dot cz>]

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.