Skip to content

Instantly share code, notes, and snippets.

@maghoff
Created October 2, 2012 11:47
Show Gist options
  • Save maghoff/3818421 to your computer and use it in GitHub Desktop.
Save maghoff/3818421 to your computer and use it in GitHub Desktop.
Timing-tester for #pragblom
#!/bin/bash
CCS="gcc clang"
O_VARIANTS="-O0 -O2 -O3 -Os -O99"
SORTS="quick selection radix shell insertion bubble"
for CC in $CCS
do
for O_VARIANT in $O_VARIANTS
do
echo $CC $O_VARIANT sort.c -o "sort-$CC$O_VARIANT"
$CC $O_VARIANT sort.c -o "sort-$CC$O_VARIANT"
done
done
for CC in $CCS
do
for O_VARIANT in $O_VARIANTS
do
EXECUTABLE="./sort-$CC$O_VARIANT"
if [ -f $EXECUTABLE ]
then
echo "$EXECUTABLE"
for SORT in $SORTS
do
echo " $SORT"
LOG="result-$CC$O_VARIANT-$SORT.txt"
$EXECUTABLE $SORT > $LOG
done
fi
done
done
/**
* From "Algorithm Speed", here are implementations of
* some common sorts.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>
#include <stdarg.h>
/*
* Report a failed test and exit
*/
void fail(const char *fmt, ...) {
va_list ap;
va_start(ap, fmt);
fprintf(stderr, "TEST FAILED -- ");
vfprintf(stderr, fmt, ap);
fprintf(stderr, "\n");
exit(1);
}
typedef unsigned long ELEMENT;
const int MAX_SIZE=10000000;
const int TEST_SIZE = 1000;
ELEMENT *array = 0;
ELEMENT *tmp_array;
#define SWAP(A,B) { ELEMENT tmp; tmp = A; A = B; B = tmp; }
/*
* Prototype for a generic sort function
*/
typedef void (*SORT_FUNCTION)(ELEMENT *, int);
/*
* Selection sort
*/
/* START: selection */
void selection(ELEMENT *input, int n) {
int i, j;
for (i = 0; i < n-1; i++) {
int lowest_index = i;
ELEMENT lowest_value = input[i];
for (j = i+1; j < n; j++)
if (input[j] < lowest_value) {
lowest_value = input[j];
lowest_index = j;
}
SWAP(input[i], input[lowest_index]);
}
}
/* END: selection */
/*
* Bubble sort
*/
void bubble(ELEMENT *input, int n) {
ELEMENT tmp;
int i;
do {
tmp = input[0];
for (i = 1; i < n; i++) {
if (input[i-1] > input[i]) {
tmp = input[i-1];
input[i-1] = input[i];
input[i] = tmp;
}
}
} while (tmp != input[0]);
}
/*
* insertion sort
*/
void insertion(ELEMENT *input, int n) {
int i, j;
ELEMENT tmp;
for (i = 1; i < n; i++) {
tmp = input[i];
j = i;
while ((j > 0) && (input[j-1] > tmp)) {
input[j] = input[j-1];
j--;
}
input[j] = tmp;
}
}
/* quicksort
*/
/* START: quicksort */
int partition(ELEMENT *input, int first, int last) {
ELEMENT pivot = input[first];
int right = last;
int left = first+1;
while (1) {
while (input[right] > pivot) right--;
while ((left < right) &&
input[left] <= pivot) left++;
if (left >= right)
break;
SWAP(input[left], input[right]);
}
input[first] = input[right];
input[right] = pivot;
return right;
}
void quicksort(ELEMENT *input, int first, int last) {
if (last > first) {
int pivot_index = partition(input, first, last);
quicksort(input, first, pivot_index-1);
quicksort(input, pivot_index+1, last);
}
}
/* END: quicksort */
void quick(ELEMENT *input, int count) {
quicksort(input, 0, count-1);
}
/*
* Shell sort
*/
void shell(ELEMENT *input, int n) {
int h = 1;
ELEMENT tmp;
int i, j;
do { h = h*3+1; } while (h <= n);
do {
h = h/3;
for (i = h; i < n; i++) {
tmp = input[i];
j = i;
while (input[j-h]>tmp) {
input[j] = input[j-h];
j -= h;
if (j < h)
break;
}
input[j] = tmp;
}
} while (h > 1);
}
/*
* Straight radix sort - NOTE - only sorts unsigned
*/
/* START: radix */
void radix(ELEMENT *input, int n) {
long count[256];
int shift = 0;
int i;
while (shift < 32) {
memset(count, 0, sizeof(count));
for (i = 0; i < n; i++) {
int bits = (input[i] >> shift) & 255;
count[bits]++;
}
for (i = 1; i < 256; i++)
count[i] += count[i-1];
for (i = n-1; i >= 0; i--) {
int bits = (input[i] >> shift) & 255;
tmp_array[count[bits]] = input[i];
count[bits]--;
}
memcpy(input, tmp_array, n*sizeof(input[0]));
shift += 8;
}
}
/* END: radix */
/*
* Check the array is sorted, exit (1) if not
*/
void checkSorted(ELEMENT *array, int size, const char *type, const char *msg) {
int i;
for (i = 1; i < size; i++) {
if (array[i-1] > array[i]) {
fail("%s: failed on test '%s'", type, msg);
exit(1);
}
}
}
/*
* testSort - run the sort function and test we're doing it right
*/
void testSort(SORT_FUNCTION fn, const char *name) {
int j;
/* initialize the array with random numbers */
for (j = 0; j < TEST_SIZE; j++)
array[j] = random();
(*fn)(array, TEST_SIZE);
checkSorted(array, TEST_SIZE, name, "random fill");
/* initialize the array with identical numbers */
for (j = 0; j < TEST_SIZE; j++)
array[j] = 0;
(*fn)(array, TEST_SIZE);
checkSorted(array, TEST_SIZE, name, "zeroes");
/* initialize the array with ascending values */
for (j = 0; j < TEST_SIZE; j++)
array[j] = j;
(*fn)(array, TEST_SIZE);
checkSorted(array, TEST_SIZE, name, "ascending");
/* initialize the array with descending values */
for (j = 0; j < TEST_SIZE; j++)
array[j] = TEST_SIZE - j;
(*fn)(array, TEST_SIZE);
checkSorted(array, TEST_SIZE, name, "descending");
}
/*
* runSort - run each sort with increasing array sizes
*/
void runSort(SORT_FUNCTION fn, const char *name,
int min, int max, int step, int test) {
int howBig;
/* make sure we start the same each time */
srandom(1);
if (test) {
testSort(fn, name);
}
else {
howBig = min;
do {
int j;
struct timeval start, end;
double diff;
/* initialize the array of numbers to sort */
for (j = 0; j < howBig; j++)
array[j] = random();
gettimeofday(&start, 0);
(*fn)(array, howBig);
gettimeofday(&end, 0);
diff = (end.tv_sec - start.tv_sec) +
(double)(end.tv_usec-start.tv_usec)/1e6;
printf("%-10s %8d %g\n", name, howBig, diff);
howBig += step;
} while (howBig <= max);
}
}
/*
* Invoked with:
*
* ./sort [-t] [name ...]
*
* where 'name' is one or more sort types. If '-t' is given, then
* the sorts are tested instead of timed
*
*/
int main(int argc, char **argv) {
int testFlag = 0;
long arraySize = MAX_SIZE;
argc--; argv++;
if (argc && (strcmp(*argv, "-t") == 0)) {
argc--;
argv++;
testFlag++;
arraySize = TEST_SIZE;
}
/*
* For efficiency, pre-allocate our array
*/
array = (ELEMENT *)malloc(arraySize*sizeof(array[0]));
if (array == 0) {
fprintf(stderr, "No memory for array\n");
exit(1);
}
/*
* Run them sorts
*/
while (argc--) {
if (strcmp(*argv, "radix") == 0) {
tmp_array = (ELEMENT *)malloc(arraySize*sizeof(array[0]));
runSort(radix, "radix", 1000000, MAX_SIZE, 1000000, testFlag);
free(tmp_array);
}
else if (strcmp(*argv, "quick") == 0)
runSort(quick, "quick", 1000000, MAX_SIZE, 1000000, testFlag);
else if (strcmp(*argv, "selection") == 0)
runSort(selection, "selection", 10000, 100000, 10000, testFlag);
else if (strcmp(*argv, "shell") == 0)
runSort(shell, "shell", 100000, MAX_SIZE, 100000, testFlag);
else if (strcmp(*argv, "insertion") == 0)
runSort(insertion, "insertion", 10000, 100000, 10000, testFlag);
else if (strcmp(*argv, "bubble") == 0)
runSort(bubble, "bubble", 10000, 100000, 20000, testFlag);
else
fprintf(stderr, "Unknown sort type '%s'\n", *argv);
argv++;
}
exit(0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment