This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Propose C Metaprogramming-based qsort as GNU extension
- From: Daniel Santos <daniel dot santos at pobox dot com>
- To: libc-alpha at sourceware dot org
- Cc: carlos at redhat dot com
- Date: Mon, 16 Feb 2015 15:15:07 -0600
- Subject: Propose C Metaprogramming-based qsort as GNU extension
- Authentication-results: sourceware.org; auth=none
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