Commits

Anonymous committed e730ec1

backing up today's work.

Comments (0)

Files changed (45)

 #  define HS_(name) HS_##name
 #endif
 
-/* #include "swap.c"  */
-/* smaller than this value => insertion sort */
-#define HSORT_ISORT_SWITCH 32
-#define HSORT_NINTHER_SWITCH 64
-
 /* Comparisons... default to arithmatic */
 #ifndef HSORT_EQ
 #  define HSORT_EQ(a,b) (*(a) == *(b))

hsort/t/cmp-small.sh

+#!/usr/bin/zsh -e
+
+echo "TESTING APP: " ${app:="f8"}
+APP=$app
+
+i=(4 8 16 32 64 128 256 1024)
+t=(1000000 1000000 1000000 100000 100000 20000 10000 5000 2000)
+sz=${#i[@]}
+c=1
+echo "Sort Comparison of unsigned integers on N numbers generating according to:"
+echo "RANDOM:    random integers"
+echo "BOUNDED:   random() % (N/4)"
+echo "SORTED:    sorted integers 1...N"
+echo "REVERSED:  sorted integers N...1"
+echo "IDENT:     all values of the array are \"1\""
+
+echo "\nRANDOM"
+echo "N               mysort (secs)   GLIBC (secs)    %impr"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} RAND ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+exit 0
+if [ ! $app = "f4" -a ! $app = "f8" ] ; then
+    echo "BOUNDED"
+    c=1
+    while [ $c -lt $sz ] ; do
+        ./${APP} ${i[$c]} BOUNDED ${t[$c]}  
+        c=$(( $c + 1 ))
+    done;
+fi;
+echo "SORTED"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} SORTED ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+echo "REVERSED"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} REVERSE ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+echo "IDENT"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} IDENT ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
 #define ISORT_SWAP(y) { swap = *(y); *(y) = *((y)-1) ; *((y)-1) = swap; } 
 #endif
 
+#include <stdlib.h>
+
 static inline void IS_(isort)(ISORT_TY* a, const long long n) {    
     ISORT_TY *x=a+1,*y=NULL,swap;
     for (;x < a + n; x++) {
+include ../defs.mk
+
+APPS=s2 s8
+SRC=$(patsubst %,%.c,$(wildcard $(APPS)))
+
+all : $(APPS)
+
+s2  : isort-cmp.c  ../isort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(O) -o s2 s2.c 
+s8  : isort-cmp.c  ../isort.c  $(SRC)
+	gcc $(G) $(W) $(I) $(O) -o s8 s8.c 
+
+clean :
+	rm -f $(APPS) csort-cmp 

isort/t/cmp-all.sh

+#!/bin/bash -e
+
+apps="s2"
+
+for app in $apps ; do
+    export app
+    ./cmp.sh
+done
+
+#!/usr/bin/zsh -e
+
+echo "TESTING APP: " ${app:="f8"}
+APP=$app
+
+i=(4 8 16 32 64 128 256 1024)
+t=(1000000 1000000 1000000 100000 100000 20000 10000 5000 2000)
+sz=${#i[@]}
+c=1
+echo "Sort Comparison of unsigned integers on N numbers generating according to:"
+echo "RANDOM:    random integers"
+echo "BOUNDED:   random() % (N/4)"
+echo "SORTED:    sorted integers 1...N"
+echo "REVERSED:  sorted integers N...1"
+echo "IDENT:     all values of the array are \"1\""
+
+echo "\nRANDOM"
+echo "N               mysort (secs)   GLIBC (secs)    %impr"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} RAND ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+exit 0
+if [ ! $app = "f4" -a ! $app = "f8" ] ; then
+    echo "BOUNDED"
+    c=1
+    while [ $c -lt $sz ] ; do
+        ./${APP} ${i[$c]} BOUNDED ${t[$c]}  
+        c=$(( $c + 1 ))
+    done;
+fi;
+echo "SORTED"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} SORTED ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+echo "REVERSED"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} REVERSE ${t[$c]}  
+    c=$(( $c + 1 ))
+done;
+echo "IDENT"
+c=1
+while [ $c -lt $sz ] ; do
+    ./${APP} ${i[$c]} IDENT ${t[$c]}  
+    c=$(( $c + 1 ))
+done;

isort/t/isort-cmp.c

+/* Test harness for csort.c, useful for all C base types up to 64 bits.  
+   Uses macros for polymorphism.
+   To use, define macro TY (e.g. #define TY float) then #include this file. */
+
+#ifndef QSORT_CMP
+#define QSORT_CMP
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <time.h>
+#include <string.h>
+#include <sys/time.h>
+#include "datetime/TIME.c"
+#include <unistd.h>
+#ifndef ISNAN
+#define CHECKNAN(x) (x)
+#else 
+#define CHECKNAN(x) (ISNAN((x)) ? 0 : (x)) 
+#endif
+
+enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
+
+long long k,j;
+const char* usage="csort-cmp dist N trials\n"
+"dist is one of: RAND, BOUNDED , SORTED, REVSORTED, IDENT\n"
+"N:              size of the array.\n"
+"trials:         how many trials to do.  Necessary for small N.\n";
+
+int parseDist(char* dist_str) {
+    if (!strcmp("BOUNDED",dist_str)) 
+        return BOUNDED;
+    else if (!strcmp("RAND",dist_str)) 
+        return RAND;
+    else if (!strcmp("SORTED",dist_str))
+        return SORTED;
+    else if (!strcmp("REVERSE",dist_str))
+        return REVERSE;
+    else if (!strcmp("IDENT",dist_str))
+        return IDENT;
+    else fprintf(stderr,"dist argument mismatch.\n%s\n",usage),exit(1);
+}
+
+void randomized(TY *x, long long n) {
+    long long i; 
+    union { char l[8]; TY t; } u;
+    for (i = 0; i < n; i++) {
+        u.l[0] =  random();
+        u.l[1] =  random();
+        u.l[2] =  random();
+        u.l[3] =  random();
+	u.l[4] =  random();
+        u.l[5] =  random();
+        u.l[6] =  random();
+        u.l[7] =  random();
+        
+	x[i]   =  u.t; 
+        x[i]   =  CHECKNAN(x[i]);
+    }
+}
+
+void bounded(TY *x, long long n) {
+    long long i;
+    union { long l[2]; TY t;} u;
+    for (i = 0; i < n; i++) {
+        u.l[0] = (random() % (n/4));
+        u.l[1] = (random() % (n/4));
+        x[i]   = u.t;
+        x[i]   = CHECKNAN(x[i]);
+    }
+}
+
+void identity(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) {
+        x[i] = 1;
+    }
+}
+
+void reverse(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) 
+        x[i] = n - i - 1;
+}
+
+void sorted(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) 
+        x[i] = i;
+}
+
+int compare(const void *a, const void *b) {
+    TY A = *(const TY *)a, B = *(const TY *)b;
+    if (A > B) return 1;
+    if (B < A) return -1;
+    return 0;
+}
+
+void fill(char* dist, TY* array1,long n) {
+    switch (parseDist(dist)) {
+    case RAND : 
+        randomized(array1,n) ; break;
+    case BOUNDED :
+        bounded(array1,n) ;    break;
+    case SORTED :
+        sorted(array1,n)  ;    break;
+    case REVERSE :
+        reverse(array1,n) ;    break;
+    case IDENT :
+        identity(array1,n) ;    break;
+    default :
+        fprintf(stderr,"dist match error.\n"), exit(1);
+    }
+}
+
+void checkWork(const char *name, TY *a, long long n ) {
+    long long i,j;
+    for (i = 1; i < n; i++) {
+        if (a[i-1] > a[i]) {
+            fprintf (stderr,"%s: %lld x %zd: failure at offset %lld\n", name, n,
+                     sizeof(TY), i);
+            for (j=0; j < n;j++) {
+                if (j != i) fprintf(stderr,TY_FMT " ",a[j]);
+                else { fprintf(stderr,TY_FMT "* ", a[j]); }
+            }
+            
+            fprintf(stderr,"\n"); 
+            free(a);
+            exit(1);
+        }
+    }
+}
+
+int main (int argc, char **argv)
+{
+    if (argc < 4) fprintf(stderr,"too few arguments: %d\n%s",argc,usage) , exit(1);
+    long i=j=0; long n=strtoul(argv[1],NULL,10);
+    long num_trials = strtoul(argv[3],NULL,10);
+    double start, end, m_tot=0, g_tot=0;
+    TY *array1 = (TY*) malloc (n * sizeof(TY));
+    if (array1 == NULL)
+        {
+            fprintf (stderr,"%d x %zd: no memory\n", argc, sizeof(TY));
+            return 1;
+        }
+    if (getenv("SEED")) srand(time(NULL)); /* default is debugging mode. */
+    for (i = 0; i < num_trials; i++) {
+        fill(argv[2],array1,n);
+        start = TIME();
+        qsort (array1,n,sizeof(TY),&compare);
+        end   = TIME();
+        if (i) {
+            g_tot += end-start;
+        }  
+        checkWork("GNU",array1,n);
+    }
+    g_tot /= (double) (num_trials - 1);
+    
+    
+    for (i = 0; i < num_trials; i++) {
+        fill(argv[2],array1,n);
+        start = TIME();
+        QS(array1,n);
+        end   = TIME();
+        if (i) {
+            m_tot += end - start;
+        }    
+        checkWork("schein",array1,n);
+    
+    }
+    m_tot /= (double) (num_trials - 1);
+    
+        
+    
+    fprintf(stdout,"%10ld\t%5.10f\t%5.10f\t%2.2f\n",n,m_tot,g_tot,
+            100*((g_tot/m_tot) - 1));
+    free (array1);
+    return 0; 
+}
+#endif
+
+
+
+
+
+
+#define TY short
+#define TY_FMT "%i"
+#include "../ufunc/s2_isort.c"
+#define QS s2_isort
+#include "isort-cmp.c"
+
+#define TY long long
+#define TY_FMT "%lli"
+#include "../ufunc/s8_isort.c"
+#define QS s8_isort
+#include "isort-cmp.c"

qsort/README

-To run type:
-
-make cmp
-
-which will compile and run a test/timing harness for major C types.
-
-Naming code for types:
-
-uN - unsigned int types of size N bytes
-sN - signed int types of size N bytes
-fN - N byte floating point numbers
-
-Key files :
-
-0. ./Makefile 
-1. ./qsort.c  - the quicksort template
-2. ./ufunc/*  - #include variants for major C types
-3. ./t/*      - test files.
-4. ./datetime - library for timings, symbolic link dereferenced in tar ball. 
+/* c 2008 Andrew I. Schein.  All rights reserved.
+   
+   A fast general-purpose sorting smplemention based on Bentley and McIlroy, 1993's discussion
+   of quicksort.
+   
+   Caller defines a few macros:
+   Required: QSORT_TY, QSORT_LT
+   Recommended: 
+   1. #define QS_(name) ty_##name, e.g. QS_(sort) -> u4_qsort
+   To do: 
+   1. handle keys within structs.
+   2. define optional mode using comparison operators wrt a single CMP a la python, ocaml.
+   
+   This implementation achieves a speedup compared to GLIBC 2.7 qsort by using the following
+   strategies:
+
+   1. Static definitions of comparions ensure inlining of this operation.  This is accomplished
+   through C macros.
+   2. Switch to insertion sort (GLIBC does this much later in the recursion tree than my impl.)
+   3. Smart treatment of duplicate pivots.  Useful for arrays containing very low entropy elements.
+   
+   In addition, this implementation differs from GLIBC 2.7 qsort in the use of recursion.
+   GLIB 2.7 manually manages a stack in order to bypass the more conventional decision of using 
+   the C runtime stack.  My implementation allows the C runtime to manage the
+   recursion stack for the non-tail first recursion call of quicksort, but performs the second
+   recursion in tail fashion by performing a goto. 
+
+   Something this implementation shares with the GLIBC implementation is recursing on the smaller 
+   partition first.  This ensures a O(N*log(N)) bound on memory usage. Another commonality is the
+   use of a smart median selection procedure the, "Tukey Ninther" method.
+   
+   The speedup compared to GLIBC is documented through a test harness located in the same 
+   directory as this file.
+
+*/
+
+#ifndef QSORT
+#define QSORT
+#if !defined LIBBING_AS_QSORT
+#  define QSORT_LKG static inline
+#else
+#  define QSORT_LKG 
+#endif
+
+#ifndef QSORT_TY
+#  error "qsort.c imported without QSORT_TY definition."
+#endif
+
+/* can redefine with type_ */
+#ifndef QS_
+#  define QS_(name) QS_##name
+#endif
+
+#include "swap.c" 
+/* smaller than this value => insertion sort */
+#define QSORT_ISORT_SWITCH 32
+#define QSORT_NINTHER_SWITCH 64
+
+/* Comparisons... default to arithmatic */
+#ifndef QSORT_EQ
+#  define QSORT_EQ(a,b) (*(a) == *(b))
+#endif
+#ifndef QSORT_LT
+#  define QSORT_LT(a,b) (*(a) < *(b))
+#endif
+#ifndef QSORT_LE
+#  define QSORT_LE(a,b) (*(a) <= *(b))
+#endif
+
+#define QSORT_MIN(a,b) ((a) < (b) ? (a) : (b))
+
+/* implements median of 3 "the ninther." Argumments are addresses. */
+#define QSORT_NINTHER(a,b,c)                                            \
+    (QSORT_LT((a),(b)) ? (QSORT_LT((b),(c)) ? (b) :                     \
+                          QSORT_LT((a),(c)) ? (c) : (a))                \
+     : (QSORT_LT((c),(b)) ? (b) : QSORT_LT((c),(a)) ? (c) : (a)))
+
+
+static inline void QS_(SWAP)(QSORT_TY *a, QSORT_TY *b) {
+    /* made a function since arguments tend to be incremented by caller */
+    QSORT_TY swap = *a;
+    *a            = *b;
+    *b            = swap;
+}
+
+static inline void QS_(isort)(QSORT_TY* a, const long long len) {    
+    QSORT_TY *x=a+1,*y;
+    for (;x < a + len;x++)
+        for ( y=x; y>a && QSORT_LT(y,(y-1)); y-- )
+            QS_(SWAP)(y,y-1);
+}
+
+static inline void QS_(sort)(QSORT_TY *x, const long long orig_n) {
+    long long n = orig_n,s;
+    long long ty_sz; /* ,l,h; */ 
+    QSORT_TY *p0,*pm,*p1;
+    QSORT_TY *a,*b,*c,*d; /* ,*t; */ /* indices within array */
+    QSORT_TY pivot;
+ ssort_start:
+    if (n < 0) fprintf(stderr,"sort error: n < 0: %lld\n",n),exit(1);
+    if (n <= QSORT_ISORT_SWITCH) return QS_(isort)(x,n);
+    s=(n>>3), ty_sz=sizeof(QSORT_TY);
+    p0=x;pm=x+(n>>1);p1=x+n-1; /* pivot candidates 0,1 from calculus, m for median */
+    if (n >= QSORT_NINTHER_SWITCH) {
+        p0    = QSORT_NINTHER(p0    , p0+s, p0+2*s);
+        pm    = QSORT_NINTHER(pm-s  , pm  , pm+s);
+        p1    = QSORT_NINTHER(p1-2*s, p1-s, p1);    
+    } 
+    pm    = QSORT_NINTHER(p0,pm,p1); /* now pm contains the pivot */
+    pivot = *pm;
+    a     = b = x;
+    c     = d = x + (n-1);
+    for (;;) { 
+        while (b <= c && QSORT_LE(b, &pivot)) { 
+            if (QSORT_EQ(b,&pivot)) QS_(SWAP)(a++,b);  /* repeated pivots treated separately */
+            b++; 
+        }  
+        while (c >= b && QSORT_LE(&pivot,c)) { 
+            if (QSORT_EQ(c,&pivot)) QS_(SWAP)(d--,c);  
+            c--; 
+        }
+        if (b > c) break;
+        QS_(SWAP)(b++,c--);
+    }
+    s = QSORT_MIN(a-x,b-a); /* repeat pivot movement */
+    //for (l=0,h=(b-x)-s; s ; s--) QS_(SWAP)(&x[l++],&x[h++]); 
+    swap(x , b - s     , s * sizeof(QSORT_TY));
+    s = QSORT_MIN(d-c, (x + n - 1) - d);
+    //for (l=b-x,h=n-s;s;s--) QS_(SWAP)(&x[l++],&x[h++]);
+    swap(b, x + (n - s), s * sizeof(QSORT_TY));
+    if ((b-a) < n-(d-c)) {  /* recurse on smaller first to bound memory usage. */
+        if ((b-a) > 1) QS_(sort)(x, (b-a));
+        if ((n-(d-c)) > 1) { /* avoid procedure call on second recursion. */
+            x = x+n-(d-c);
+            n = d-c;
+            goto ssort_start;
+        }
+    }
+    else {
+        if ((d-c) > 1) QS_(sort)(x + n-(d-c), d-c);
+        if ((b - a) > 1) {
+            n = (b-a); 
+            goto ssort_start; /* avoid procedure call on second recursion. */
+        }
+    }
+}
+
+#undef QS_
+#undef QSORT_MIN
+#undef QSORT_LKG 
+#undef QSORT_LT
+#undef QSORT_LE
+#undef QSORT_EQ
+#undef QSORT_TY
+#undef QSORT_SWITCH
+#undef QSORT_NINTHER
+#endif

qsort/qsort-cmp

Binary file removed.

qsort/qsort.c

-/* c 2008 Andrew I. Schein.  All rights reserved.
-   
-   A fast general-purpose sorting smplemention based on Bentley and McIlroy, 1993's discussion
-   of quicksort.
-   
-   Caller defines a few macros:
-   Required: QSORT_TY, QSORT_LT
-   Recommended: 
-   1. #define QS_(name) ty_##name, e.g. QS_(sort) -> u4_qsort
-   To do: 
-   1. handle keys within structs.
-   2. define optional mode using comparison operators wrt a single CMP a la python, ocaml.
-   
-   This implementation achieves a speedup compared to GLIBC 2.7 qsort by using the following
-   strategies:
-
-   1. Static definitions of comparions ensure inlining of this operation.  This is accomplished
-   through C macros.
-   2. Switch to insertion sort (GLIBC does this much later in the recursion tree than my impl.)
-   3. Smart treatment of duplicate pivots.  Useful for arrays containing very low entropy elements.
-   
-   In addition, this implementation differs from GLIBC 2.7 qsort in the use of recursion.
-   GLIB 2.7 manually manages a stack in order to bypass the more conventional decision of using 
-   the C runtime stack.  My implementation allows the C runtime to manage the
-   recursion stack for the non-tail first recursion call of quicksort, but performs the second
-   recursion in tail fashion by performing a goto. 
-
-   Something this implementation shares with the GLIBC implementation is recursing on the smaller 
-   partition first.  This ensures a O(N*log(N)) bound on memory usage. Another commonality is the
-   use of a smart median selection procedure the, "Tukey Ninther" method.
-   
-   The speedup compared to GLIBC is documented through a test harness located in the same 
-   directory as this file.
-
-*/
-
-#ifndef QSORT
-#define QSORT
-#if !defined LIBBING_AS_QSORT
-#  define QSORT_LKG static inline
-#else
-#  define QSORT_LKG 
-#endif
-
-#ifndef QSORT_TY
-#  error "qsort.c imported without QSORT_TY definition."
-#endif
-
-/* can redefine with type_ */
-#ifndef QS_
-#  define QS_(name) QS_##name
-#endif
-
-#include "swap.c" 
-/* smaller than this value => insertion sort */
-#define QSORT_ISORT_SWITCH 32
-#define QSORT_NINTHER_SWITCH 64
-
-/* Comparisons... default to arithmatic */
-#ifndef QSORT_EQ
-#  define QSORT_EQ(a,b) (*(a) == *(b))
-#endif
-#ifndef QSORT_LT
-#  define QSORT_LT(a,b) (*(a) < *(b))
-#endif
-#ifndef QSORT_LE
-#  define QSORT_LE(a,b) (*(a) <= *(b))
-#endif
-
-#define QSORT_MIN(a,b) ((a) < (b) ? (a) : (b))
-
-/* implements median of 3 "the ninther." Argumments are addresses. */
-#define QSORT_NINTHER(a,b,c)                                            \
-    (QSORT_LT((a),(b)) ? (QSORT_LT((b),(c)) ? (b) :                     \
-                          QSORT_LT((a),(c)) ? (c) : (a))                \
-     : (QSORT_LT((c),(b)) ? (b) : QSORT_LT((c),(a)) ? (c) : (a)))
-
-
-static inline void QS_(SWAP)(QSORT_TY *a, QSORT_TY *b) {
-    /* made a function since arguments tend to be incremented by caller */
-    QSORT_TY swap = *a;
-    *a            = *b;
-    *b            = swap;
-}
-
-static inline void QS_(isort)(QSORT_TY* a, const long long len) {    
-    QSORT_TY *x=a+1,*y;
-    for (;x < a + len;x++)
-        for ( y=x; y>a && QSORT_LT(y,(y-1)); y-- )
-            QS_(SWAP)(y,y-1);
-}
-
-static inline void QS_(sort)(QSORT_TY *x, const long long orig_n) {
-    long long n = orig_n,s;
-    long long ty_sz; /* ,l,h; */ 
-    QSORT_TY *p0,*pm,*p1;
-    QSORT_TY *a,*b,*c,*d; /* ,*t; */ /* indices within array */
-    QSORT_TY pivot;
- ssort_start:
-    if (n < 0) fprintf(stderr,"sort error: n < 0: %lld\n",n),exit(1);
-    if (n <= QSORT_ISORT_SWITCH) return QS_(isort)(x,n);
-    s=(n>>3), ty_sz=sizeof(QSORT_TY);
-    p0=x;pm=x+(n>>1);p1=x+n-1; /* pivot candidates 0,1 from calculus, m for median */
-    if (n >= QSORT_NINTHER_SWITCH) {
-        p0    = QSORT_NINTHER(p0    , p0+s, p0+2*s);
-        pm    = QSORT_NINTHER(pm-s  , pm  , pm+s);
-        p1    = QSORT_NINTHER(p1-2*s, p1-s, p1);    
-    } 
-    pm    = QSORT_NINTHER(p0,pm,p1); /* now pm contains the pivot */
-    pivot = *pm;
-    a     = b = x;
-    c     = d = x + (n-1);
-    for (;;) { 
-        while (b <= c && QSORT_LE(b, &pivot)) { 
-            if (QSORT_EQ(b,&pivot)) QS_(SWAP)(a++,b);  /* repeated pivots treated separately */
-            b++; 
-        }  
-        while (c >= b && QSORT_LE(&pivot,c)) { 
-            if (QSORT_EQ(c,&pivot)) QS_(SWAP)(d--,c);  
-            c--; 
-        }
-        if (b > c) break;
-        QS_(SWAP)(b++,c--);
-    }
-    s = QSORT_MIN(a-x,b-a); /* repeat pivot movement */
-    //for (l=0,h=(b-x)-s; s ; s--) QS_(SWAP)(&x[l++],&x[h++]); 
-    swap(x , b - s     , s * sizeof(QSORT_TY));
-    s = QSORT_MIN(d-c, (x + n - 1) - d);
-    //for (l=b-x,h=n-s;s;s--) QS_(SWAP)(&x[l++],&x[h++]);
-    swap(b, x + (n - s), s * sizeof(QSORT_TY));
-    if ((b-a) < n-(d-c)) {  /* recurse on smaller first to bound memory usage. */
-        if ((b-a) > 1) QS_(sort)(x, (b-a));
-        if ((n-(d-c)) > 1) { /* avoid procedure call on second recursion. */
-            x = x+n-(d-c);
-            n = d-c;
-            goto ssort_start;
-        }
-    }
-    else {
-        if ((d-c) > 1) QS_(sort)(x + n-(d-c), d-c);
-        if ((b - a) > 1) {
-            n = (b-a); 
-            goto ssort_start; /* avoid procedure call on second recursion. */
-        }
-    }
-}
-
-#undef QS_
-#undef QSORT_MIN
-#undef QSORT_LKG 
-#undef QSORT_LT
-#undef QSORT_LE
-#undef QSORT_EQ
-#undef QSORT_TY
-#undef QSORT_SWITCH
-#undef QSORT_NINTHER
-#endif
 
 all : $(APPS)
 
-u1  : qsort-cmp.c ../swap.c ../qsort.c $(SRC)  
+u1  : csort-cmp.c ../swap.c ../csort.c $(SRC)  
 	gcc $(G) $(W) $(I) $(O) -o u1 u1.c 
 
-s1  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+s1  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o s1 s1.c 
 
-u2  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+u2  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o u2 u2.c 
 
-s2  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+s2  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o s2 s2.c 
 
-f4  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+f4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o f4 f4.c 
 
-s4  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+s4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o s4 s4.c 
 
-u4  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+u4  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o u4 u4.c 
 
-f8  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+f8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o f8 f8.c 
 
-u8  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+u8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o u8 u8.c 
 
-s8  : qsort-cmp.c ../swap.c ../qsort.c  $(SRC)
+s8  : csort-cmp.c ../swap.c ../csort.c  $(SRC)
 	gcc $(G) $(W) $(I) $(O) -o s8 s8.c 
 
 
 clean :
-	rm -f $(APPS) qsort-cmp 
+	rm -f $(APPS) csort-cmp 

qsort/t/csort-cmp.c

+/* Test harness for csort.c, useful for all C base types up to 64 bits.  
+   Uses macros for polymorphism.
+   To use, define macro TY (e.g. #define TY float) then #include this file. */
+
+#ifndef QSORT_CMP
+#define QSORT_CMP
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <time.h>
+#include <string.h>
+#include <sys/time.h>
+#include "datetime/TIME.c"
+#include <unistd.h>
+#ifndef ISNAN
+#define CHECKNAN(x) (x)
+#else 
+#define CHECKNAN(x) (ISNAN((x)) ? 0 : (x)) 
+#endif
+
+enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
+
+long long k,j;
+const char* usage="csort-cmp dist N trials\n"
+"dist is one of: RAND, BOUNDED , SORTED, REVSORTED, IDENT\n"
+"N:              size of the array.\n"
+"trials:         how many trials to do.  Necessary for small N.\n";
+
+int parseDist(char* dist_str) {
+    if (!strcmp("BOUNDED",dist_str)) 
+        return BOUNDED;
+    else if (!strcmp("RAND",dist_str)) 
+        return RAND;
+    else if (!strcmp("SORTED",dist_str))
+        return SORTED;
+    else if (!strcmp("REVERSE",dist_str))
+        return REVERSE;
+    else if (!strcmp("IDENT",dist_str))
+        return IDENT;
+    else fprintf(stderr,"dist argument mismatch.\n%s\n",usage),exit(1);
+}
+
+void randomized(TY *x, long long n) {
+    long long i; 
+    union { char l[8]; TY t; } u;
+    for (i = 0; i < n; i++) {
+        u.l[0] =  random();
+        u.l[1] =  random();
+        u.l[2] =  random();
+        u.l[3] =  random();
+	u.l[4] =  random();
+        u.l[5] =  random();
+        u.l[6] =  random();
+        u.l[7] =  random();
+        
+	x[i]   =  u.t; 
+        x[i]   =  CHECKNAN(x[i]);
+    }
+}
+
+void bounded(TY *x, long long n) {
+    long long i;
+    union { long l[2]; TY t;} u;
+    for (i = 0; i < n; i++) {
+        u.l[0] = (random() % (n/4));
+        u.l[1] = (random() % (n/4));
+        x[i]   = u.t;
+        x[i]   = CHECKNAN(x[i]);
+    }
+}
+
+void identity(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) {
+        x[i] = 1;
+    }
+}
+
+void reverse(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) 
+        x[i] = n - i - 1;
+}
+
+void sorted(TY *x, long long n) {
+    long long i;
+    for (i = 0; i < n; i++) 
+        x[i] = i;
+}
+
+int compare(const void *a, const void *b) {
+    TY A = *(const TY *)a, B = *(const TY *)b;
+    if (A > B) return 1;
+    if (B < A) return -1;
+    return 0;
+}
+
+void fill(char* dist, TY* array1,long n) {
+    switch (parseDist(dist)) {
+    case RAND : 
+        randomized(array1,n) ; break;
+    case BOUNDED :
+        bounded(array1,n) ;    break;
+    case SORTED :
+        sorted(array1,n)  ;    break;
+    case REVERSE :
+        reverse(array1,n) ;    break;
+    case IDENT :
+        identity(array1,n) ;    break;
+    default :
+        fprintf(stderr,"dist match error.\n"), exit(1);
+    }
+}
+
+void checkWork(const char *name, TY *a, long long n ) {
+    long long i,j;
+    for (i = 1; i < n; i++) {
+        if (a[i-1] > a[i]) {
+            fprintf (stderr,"%s: %lld x %zd: failure at offset %lld\n", name, n,
+                     sizeof(TY), i);
+            for (j=0; j < n;j++) {
+                if (j != i) fprintf(stderr,TY_FMT " ",a[j]);
+                else { fprintf(stderr,TY_FMT "* ", a[j]); }
+            }
+            
+            fprintf(stderr,"\n"); 
+            free(a);
+            exit(1);
+        }
+    }
+}
+
+int main (int argc, char **argv)
+{
+    if (argc < 4) fprintf(stderr,"too few arguments: %d\n%s",argc,usage) , exit(1);
+    long i=j=0; long n=strtoul(argv[1],NULL,10);
+    long num_trials = strtoul(argv[3],NULL,10);
+    double start, end, m_tot=0, g_tot=0;
+    TY *array1 = (TY*) malloc (n * sizeof(TY));
+    if (array1 == NULL)
+        {
+            fprintf (stderr,"%d x %zd: no memory\n", argc, sizeof(TY));
+            return 1;
+        }
+    if (getenv("SEED")) srand(time(NULL)); /* default is debugging mode. */
+    for (i = 0; i < num_trials; i++) {
+        fill(argv[2],array1,n);
+        start = TIME();
+        qsort (array1,n,sizeof(TY),&compare);
+        end   = TIME();
+        if (i) {
+            g_tot += end-start;
+        }  
+        checkWork("GNU",array1,n);
+    }
+    g_tot /= (double) (num_trials - 1);
+    
+    
+    for (i = 0; i < num_trials; i++) {
+        fill(argv[2],array1,n);
+        start = TIME();
+        QS(array1,n);
+        end   = TIME();
+        if (i) {
+            m_tot += end - start;
+        }    
+        checkWork("schein",array1,n);
+    
+    }
+    m_tot /= (double) (num_trials - 1);
+    
+        
+    
+    fprintf(stdout,"%10ld\t%5.10f\t%5.10f\t%2.2f\n",n,m_tot,g_tot,
+            100*((g_tot/m_tot) - 1));
+    free (array1);
+    return 0; 
+}
+#endif
+
+
+
+
+
 #define TY_FMT "%f"
 #include "../ufunc/f4_sort.c"
 #define QS f4_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 #define TY_FMT "%lf"
 #include "../ufunc/f8_sort.c"
 #define QS f8_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"

qsort/t/qsort-cmp.c

-/* Test harness for qsort.c, useful for all C base types up to 64 bits.  
-   Uses macros for polymorphism.
-   To use, define macro TY (e.g. #define TY float) then #include this file. */
-
-#ifndef QSORT_CMP
-#define QSORT_CMP
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <math.h>
-#include <time.h>
-#include <string.h>
-#include <sys/time.h>
-#include "datetime/TIME.c"
-#include <unistd.h>
-#ifndef ISNAN
-#define CHECKNAN(x) (x)
-#else 
-#define CHECKNAN(x) (ISNAN((x)) ? 0 : (x)) 
-#endif
-
-enum generator {RAND,BOUNDED,SORTED, REVERSE ,IDENT} ;
-
-long long k,j;
-const char* usage="qsort-cmp dist N trials\n"
-"dist is one of: RAND, BOUNDED , SORTED, REVSORTED, IDENT\n"
-"N:              size of the array.\n"
-"trials:         how many trials to do.  Necessary for small N.\n";
-
-int parseDist(char* dist_str) {
-    if (!strcmp("BOUNDED",dist_str)) 
-        return BOUNDED;
-    else if (!strcmp("RAND",dist_str)) 
-        return RAND;
-    else if (!strcmp("SORTED",dist_str))
-        return SORTED;
-    else if (!strcmp("REVERSE",dist_str))
-        return REVERSE;
-    else if (!strcmp("IDENT",dist_str))
-        return IDENT;
-    else fprintf(stderr,"dist argument mismatch.\n%s\n",usage),exit(1);
-}
-
-void randomized(TY *x, long long n) {
-    long long i; 
-    union { char l[8]; TY t; } u;
-    for (i = 0; i < n; i++) {
-        u.l[0] =  random();
-        u.l[1] =  random();
-        u.l[2] =  random();
-        u.l[3] =  random();
-	u.l[4] =  random();
-        u.l[5] =  random();
-        u.l[6] =  random();
-        u.l[7] =  random();
-        
-	x[i]   =  u.t; 
-        x[i]   =  CHECKNAN(x[i]);
-    }
-}
-
-void bounded(TY *x, long long n) {
-    long long i;
-    union { long l[2]; TY t;} u;
-    for (i = 0; i < n; i++) {
-        u.l[0] = (random() % (n/4));
-        u.l[1] = (random() % (n/4));
-        x[i]   = u.t;
-        x[i]   = CHECKNAN(x[i]);
-    }
-}
-
-void identity(TY *x, long long n) {
-    long long i;
-    for (i = 0; i < n; i++) {
-        x[i] = 1;
-    }
-}
-
-void reverse(TY *x, long long n) {
-    long long i;
-    for (i = 0; i < n; i++) 
-        x[i] = n - i - 1;
-}
-
-void sorted(TY *x, long long n) {
-    long long i;
-    for (i = 0; i < n; i++) 
-        x[i] = i;
-}
-
-int compare(const void *a, const void *b) {
-    TY A = *(const TY *)a, B = *(const TY *)b;
-    if (A > B) return 1;
-    if (B < A) return -1;
-    return 0;
-}
-
-void fill(char* dist, TY* array1,long n) {
-    switch (parseDist(dist)) {
-    case RAND : 
-        randomized(array1,n) ; break;
-    case BOUNDED :
-        bounded(array1,n) ;    break;
-    case SORTED :
-        sorted(array1,n)  ;    break;
-    case REVERSE :
-        reverse(array1,n) ;    break;
-    case IDENT :
-        identity(array1,n) ;    break;
-    default :
-        fprintf(stderr,"dist match error.\n"), exit(1);
-    }
-}
-
-void checkWork(const char *name, TY *a, long long n ) {
-    long long i,j;
-    for (i = 1; i < n; i++) {
-        if (a[i-1] > a[i]) {
-            fprintf (stderr,"%s: %lld x %zd: failure at offset %lld\n", name, n,
-                     sizeof(TY), i);
-            for (j=0; j < n;j++) {
-                if (j != i) fprintf(stderr,TY_FMT " ",a[j]);
-                else { fprintf(stderr,TY_FMT "* ", a[j]); }
-            }
-            
-            fprintf(stderr,"\n"); 
-            free(a);
-            exit(1);
-        }
-    }
-}
-
-int main (int argc, char **argv)
-{
-    if (argc < 4) fprintf(stderr,"too few arguments: %d\n%s",argc,usage) , exit(1);
-    long i=j=0; long n=strtoul(argv[1],NULL,10);
-    long num_trials = strtoul(argv[3],NULL,10);
-    double start, end, m_tot=0, g_tot=0;
-    TY *array1 = (TY*) malloc (n * sizeof(TY));
-    if (array1 == NULL)
-        {
-            fprintf (stderr,"%d x %zd: no memory\n", argc, sizeof(TY));
-            return 1;
-        }
-    if (getenv("SEED")) srand(time(NULL)); /* default is debugging mode. */
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        qsort (array1,n,sizeof(TY),&compare);
-        end   = TIME();
-        if (i) {
-            g_tot += end-start;
-        }  
-        checkWork("GNU",array1,n);
-    }
-    g_tot /= (double) (num_trials - 1);
-    
-    
-    for (i = 0; i < num_trials; i++) {
-        fill(argv[2],array1,n);
-        start = TIME();
-        QS(array1,n);
-        end   = TIME();
-        if (i) {
-            m_tot += end - start;
-        }    
-        checkWork("schein",array1,n);
-    
-    }
-    m_tot /= (double) (num_trials - 1);
-    
-        
-    
-    fprintf(stdout,"%10ld\t%5.10f\t%5.10f\t%2.2f\n",n,m_tot,g_tot,
-            100*((g_tot/m_tot) - 1));
-    free (array1);
-    return 0; 
-}
-#endif
-
-
-
-
-
 #define TY_FMT "%c"
 #include "../ufunc/s1_sort.c"
 #define QS s1_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 #define TY_FMT "%i"
 #include "../ufunc/s2_sort.c"
 #define QS s2_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 #define TY_FMT "%d"
 #include "../ufunc/s4_sort.c"
 #define QS s4_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 #define TY_FMT "%lld"
 #include "../ufunc/s8_sort.c"
 #define QS s8_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 #define TY_FMT "%d"
 #include "../ufunc/u1_sort.c"
 #define QS u1_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 
 
 #define TY_FMT "%ui"
 #include "../ufunc/u2_sort.c"
 #define QS u2_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 #define TY_FMT "%u"
 #include "../ufunc/u4_sort.c"
 #define QS u4_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"
 
 #define TY_FMT "%llu"
 #include "../ufunc/u8_sort.c"
 #define QS u8_sort
-#include "qsort-cmp.c"
+#include "csort-cmp.c"

qsort/ufunc/f4_sort.c

 #define QSORT_TY float
 #define QS_(name) f4_## name
 
-#include "../qsort.c"
+#include "../csort.c"
 #endif

qsort/ufunc/f8_sort.c

 #define F8_QSORT
 #define QSORT_TY double
 #define QS_(name) f8_## name
-#include "../qsort.c"
+#include "../csort.c"
 #endif

qsort/ufunc/s1_sort.c

 #define S1_QSORT
 #define QSORT_TY signed char
 #define QS_(name) s1_## name
-#include "qsort.c"
+#include "csort.c"
 #endif

qsort/ufunc/s2_sort.c

 #define S2_QSORT
 #define QSORT_TY signed short
 #define QS_(name) s2_## name
-#include "qsort.c"
+#include "csort.c"
 #endif

qsort/ufunc/s4_sort.c

 #define S4_QSORT
 #define QSORT_TY int
 #define QS_(name) s4_## name
-#include "../qsort.c"
+#include "../csort.c"
 #endif

qsort/ufunc/s8_sort.c

 #define S8_QSORT
 #define QSORT_TY long long
 #define QS_(name) s8_## name
-#include "../qsort.c"
+#include "../csort.c"
 #endif

qsort/ufunc/u1_sort.c

 #define U1_QSORT
 #define QS_(name) u1_## name
 #define QSORT_TY unsigned char
-#include "qsort.c"
+#include "csort.c"
 #endif

qsort/ufunc/u2_sort.c

 #define U2_QSORT
 #define QSORT_TY unsigned short
 #define QS_(name) u2_## name
-#include "qsort.c"
+#include "csort.c"
 #endif

qsort/ufunc/u4_sort.c

 #define U4_QSORT
 #define QSORT_TY uint32_t
 #define QS_(name) u4_##name
-#include "../qsort.c"
+#include "../csort.c"
 #endif
 
 

qsort/ufunc/u8_sort.c

 #define U8_QSORT
 #define QSORT_TY unsigned long long
 #define QS_(name) u8_## name
-#include "../qsort.c"
+#include "../csort.c"
 #endif
-test :
-	gcc -E -c -I../ -I../../ -I../qsort/ 
-
+all : 
+	cd t ; make all
 clean :
 	rm -f test
 	cd t ; make clean
 #  include <stdlib.h>
 #  define QSORT_TY float
 #  define QS_(name) f4_q##name
-#  include "../qsort/qsort.c"
+#  include "../qsort/csort.c"
 
 #  define _0(v) ( (v)         & 0x7FF)
 #  define _1(v) (((v)  >> 11) & 0x7FF)
 #else /* endian */
 #  define QS_(name) f4_## name 
 #  define QSORT_TY float
-#  include "../qsort/qsort.c"
+#  include "../qsort/csort.c"
 #endif
 #  include <stdlib.h>
 #  define QSORT_TY double
 #  define QS_(name) f8_q##name
-#  include "../qsort/qsort.c"
+#  include "../qsort/csort.c"
 
 #define _0(v) ( (v)         & 0x7FF)
 #define _1(v) (((v)  >> 11) & 0x7FF)
 #else /* endian */
 # define QS_(name) f8_## name 
 # define QSORT_TY double
-# include "../qsort/qsort.c"
+# include "../qsort/csort.c"
 #endif
 #else /* endian */
 #define QS_(name) s2_## name 
 #define QSORT_TY short
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 #endif
 #include <stdlib.h>
 #define QSORT_TY int
 #define QS_(name) s4_q##name
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 
 #define _0(v) ((unsigned)(v)         & 0x7FF)
 #define _1(v) (((unsigned)(v) >> 11) & 0x7FF)
 /* endian */
 #define QS_(name) s4_## name 
 #define QSORT_TY int
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 #endif
 
 #define QS_(name) s8_q##name
 #define QSORT_TY long long
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 
 #define _0(v) ((v)         & 0x7FF)
 #define _1(v) (((v) >> 11) & 0x7FF)
 #else /* big endian */
 #define QS_(name) s8_## name 
 #define QSORT_TY long long
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 #endif 
 #else
 #define QS_(name) u2_## name 
 #define QSORT_TY unsigned short
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 #endif
 #include <stdlib.h>
 #define QSORT_TY unsigned
 #define QS_(name) u4_q##name
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 
 #define _0(v) (unsigned) ((v)         & 0x7FF)
 #define _1(v) (unsigned) (((v) >> 11) & 0x7FF)
 #else /* endian */
 #define QS_(name) u4_## name 
 #define QSORT_TY unsigned
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 #endif
 
 #define QSORT_TY unsigned long long 
 #define QS_(name) u8_q##name
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 
 #define _0(v) ((v)         & 0x7FF)
 #define _1(v) (((v) >> 11) & 0x7FF)
 #else  /* endian */
 #define QS_(name) u8_## name 
 #define QSORT_TY unsigned long long
-#include "../qsort/qsort.c"
+#include "../qsort/csort.c"
 #endif