I modified the sort function ever so slightly to take an int input that takes the place of the 7 that was originally hardcoded into the function. Other than that, the function works exactly as it was written for the paper.
#include <stddef.h>
#include "bm.h"
typedef long WORD;
#define W sizeof(WORD) /* must be a power of 2 */
#define SWAPINIT(a, es) swaptype =\
(a-(void*)0 | es) % W ? 2 : es > W ? 1 : 0
#define exch(a, b, t) (t = a, a = b, b = t)
#define swap(a, b) swaptype != 0 ?\
swapfunc(a, b, es, swaptype) : (void)exch(*(WORD*)(a), *(WORD*)(b), t)
#define vecswap(a, b, n) if (n > 0) swapfunc(a, b, n, swaptype)
#define PVINIT(pv, pm) if (swaptype != 0) pv = a, swap(pv, pm);\
else pv = (char*)&v, v = *(WORD*)pm
#define MIN(a, b) ((a) < (b) ? a : b)
static char *med3(char *a, char *b, char *c, int (*cmp)())
{
return cmp(a, b)<0?
(cmp(b, c)<0?b: cmp(a, c) < 0 ? c : a)
: (cmp(b, c)>0?b: cmp(a, c) > 0 ? c : a);
}
static void swapfunc(char *a, char *b, size_t n, int swaptype)
{
if (swaptype <= 1) {
WORD t;
for( ; n > 0; a += W, b += W, n -= W)
exch(*(WORD*)a, *(WORD*)b, t);
} else {
char t;
for( ; n > 0; a += 1, b += 1, n -= 1)
exch(*a, *b, t);
}
}
void bm(void *a, size_t n, size_t es, int (*cmp)(const void *, const void *), int m)
{
void *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
int r, swaptype;
WORD t, v;
size_t s;
SWAPINIT(a, es);
if (n < m) { /* Insertion sort on smallest arrays */
for (pm = a + es; pm < a + n*es; pm += es)
for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
swap(pl, pl-es);
return;
}
pm = a + (n/2)*es; /* Small arrays, middle element */
if (n > m) {
pl = a;
pn = a + (n-1)*es;
if (n > 40) { /* Big arrays, pseudomedian of 9 */
s = (n/8)*es;
pl = med3(pl, pl+s, pl+2*s, cmp);
pm = med3(pm-s, pm, pm+s, cmp);
pn = med3(pn-2*s, pn-s, pn, cmp);
}
pm = med3(pl, pm, pn, cmp); /* Mid-size, med of 3 */
}
PVINIT(pv, pm); /* pv points to partition value */
pa = pb = a;
pc = pd = a + (n-1)*es;
for (;;) {
while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
if (r == 0) { swap(pa, pb); pa += es; }
pb += es;
}
while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
if (r == 0) { swap(pc, pd); pd -= es; }
pc -= es;
}
if (pb > pc) break;
swap(pb, pc);
pb += es;
pc -= es;
}
pn = a + n*es;
s = MIN(pa-a, pb-pa ); vecswap(a, pb-s, s);
s = MIN(pd-pc, pn-pd-es); vecswap(pb, pn-s, s);
if ((s = pb-pa) > es) bm(a, s/es, es, cmp, m);
if ((s = pd-pc) > es) bm(pn-s, s/es, es, cmp, m);
}The test program is controlled by a series of #define statements at the top. `ITERATIONS` determines how many times each function is run to get a runtime average. `TESTTYPE` is the datatype used. NMIN is the minimum size array, NMAX is the maximum size, and NSTEP is how much to grow the array on each run. The PIVOT directives work exactly the same way for the magic number. DDD determines whether to generate a 3d graph or just a 2d graph. In 2d mode the array size is always NMAX.
#define ITERATIONS 100
#define TESTTYPE char
#define NMIN 1
#define NMAX 255
#define NSTEP 1
#define PIVOTMIN 1
#define PIVOTMAX 255
#define PIVOTSTEP 1
#define DDD
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "bm.h"
clock_t timeit (void (*func)\
(void *, size_t, size_t, int (*)(const void *, const void *), int), \
void *a, size_t n, size_t es, int(*cmp)(const void *, const void *), int m)
{
clock_t s, e;
int i;
unsigned long int total = 0;
for (i = 0; i < ITERATIONS; i++)
{
s = clock();
func(a, n, es, cmp, m);
e = clock();
total = total + (e - s);
}
return total / ITERATIONS;
}
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
void printarr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void qshim (void *a, size_t n, size_t es,\
int(*cmp)(const void *, const void *), int m)
{
qsort(a, n, es, cmp);
}
int main()
{
int l = NMAX;
int i, j;
TESTTYPE a[NMAX], b[NMAX], c[NMAX], d[NMAX], e[NMAX], f[NMAX];
clock_t time_a, time_b, time_c, time_d, time_e, time_f;
srand(0);
#ifdef DDD
for (l = NMIN; l <= NMAX; l = l + NSTEP)
{
#endif
for (j = PIVOTMIN; j <= PIVOTMAX; j = j + PIVOTSTEP)
{
for (i = 0; i < l; i++)
{
a[i] = l - i; // descending
b[i] = i; // ascending
c[i] = rand() % NMAX; // random
d[i] = i % 5; // sawtooth
e[i] = i + (i % 5); // dithered
if (i < l/2) // organ pipe
{
f[i] = i;
}
else
{
f[i] = l - i;
}
}
time_a = timeit(bm, a, l, sizeof(TESTTYPE), compare, j);
time_b = timeit(bm, b, l, sizeof(TESTTYPE), compare, j);
time_c = timeit(bm, c, l, sizeof(TESTTYPE), compare, j);
time_d = timeit(bm, d, l, sizeof(TESTTYPE), compare, j);
time_e = timeit(bm, e, l, sizeof(TESTTYPE), compare, j);
time_f = timeit(bm, f, l, sizeof(TESTTYPE), compare, j);
#ifdef DDD
printf("%d %d %lu %lu %lu %lu %lu %lu\n",\
j, l, time_a, time_b, time_c, time_d, time_e, time_f);
}
#else
printf("%d %lu %lu %lu %lu %lu %lu\n",\
j, time_a, time_b, time_c, time_d, time_e, time_f);
#endif
}
return(0);
}On array sizes from 10 to 10000, I found that the array size had very little impact on the relative impact of the magic number. That is, the effect the magic number had on arrays of size 10000 impacted other array sizes the same way proportionally. Because of this, I decided to make the 2d graphs using an array size of 10000 for purposes of clarity. It should be noted, however, that I did test array sizes from 10 to 10000 in steps of 10 in order to verify this claim.
Ints are an important case in sorting since they are one of the most common datatypes. They are also important as they typically represent the datatype that machines are optimized to work best on. Perhaps as a result of this, the int test was one of the most interesting, representative, and consistent cases.
Ints are also important because arrays very often contain int pointers when operating on larger datatypes. Thus, for things like structs, the int is often what you are actually swapping.
From the graphs, you can see that the magic number of 7 is clearly ridiculous for ints. Runtime steadily decreases until a magic number of about 200, where the results become less clear, with random and organ pipe inputs getting slightly slower.
The graphs only show chars for array sizes up to 255. Above that, the graphs all flattened out. I suspect this is because chars can only hold 255 distinct values.
As can be seen from the graphs, larger magic numbers speed up the sort accross the board. Again, a magic number of about 200 or slightly higher seems to make the most sense in this case.
Unsigned long longs were important to test because they are the largest primitive datatype and the swapping method used in Bentley & McIlroy’s sort is changed to use a function swap rather than an inline swap in this case.
Again, it seems that larger magic numbers seem to cause the sort to perform better, until a point where the results become less clear.
I found that the magic number affected the runtime of the sort function significantly. It also affected large arrays proportionally more. I suspect that this is because a larger array is broken down into more subarrays recursively, so the decision as to which magic number to use comes into play more times on a larger array. For my machine, I found that a magic number of around 200 would make the most sense. In order to apply this to a library sort, however, I would want to test on a larger variety of machines in current use.