Index: tools/tools/sortbench/Makefile =================================================================== --- /dev/null +++ tools/tools/sortbench/Makefile @@ -0,0 +1,18 @@ +# $FreeBSD$ + +PROG= sort_bench +MAN= + +LIBADD= m + +.ifdef WITH_WIKISORT +CFLAGS= -I${SRCTOP}/lib/libc -DWIKI +.endif + +CLEANDIRS= stats +ELEMENT_BITS= 20 +bench: .PHONY + ${.CURDIR}/bench.py ${ELEMENT_BITS} + echo "See results in ${.OBJDIR}/stats" + +.include Index: tools/tools/sortbench/README =================================================================== --- /dev/null +++ tools/tools/sortbench/README @@ -0,0 +1,15 @@ +Running: +1. Compile mergesort_bench.c into mergesort_bench +2. Run bench.py with python bench.py [elts] +2a. Bench will optionally run 2 ^ elts elements as the dataset size when provided. Otherwise it will run 2 ^ 20 elements. + +Output: +Files will be output in a new folder called stats with separate files for each statistical comparison and the raw results in a subfolder called data. +This files will contain the results of the running of ministat with time required to sort as the dataset. + +Modifications: +Change bench.py's WIKI variable to be true if you have wiki.c implemented and want to test it. + +As the script runs, it is running each of the stdlib sorting algorithms (and wikisort if provided) with 2 ^ elts elements, +5 trials of the sort time as it's output. That output is saved in the data folder and then passed into the command line +utility ministat which then provides the confidence interval of difference between the data in stats folder. Index: tools/tools/sortbench/bench.py =================================================================== --- /dev/null +++ tools/tools/sortbench/bench.py @@ -0,0 +1,45 @@ +#!/usr/bin/env python + +from time import time +import os +import sys + +WIKI = False +sorts=["heap", "merge", "quick"] +if (WIKI): + sorts.append("wiki") +tests=["rand", "sort", "rev", "part"] +runs = 5 +trials = 5 +outdir = "stats" +datadir = '{}/data'.format(outdir) +progname = "sort_bench" +try: + elts = sys.argv[1] +except: + elts = 20 + +if (not os.path.isdir(datadir)): + os.makedirs(datadir) + +for test in tests: + files = [] + for sort in sorts: + filename = '{}/{}{}'.format(datadir, test, sort) + files.append(filename) + with open(filename, 'w+') as f: + for _ in range(trials): + start = time() + ret = os.system('./{} {} {} {} {}'.format(progname, sort, test, runs, elts)) + total = time() - start + if (ret): + sys.exit("Bench program failed. Did you remember to compile it?") + f.write('{}\n'.format(str(total))) + f.close() + with open('{}/{}'.format(outdir, test), 'w+') as f: + command = 'ministat -s -w 60 ' + for filename in files: + command += '{} '.format(filename) + command += '> {}/{}stats'.format(outdir, test) + os.system(command) + Index: tools/tools/sortbench/sort_bench.c =================================================================== --- /dev/null +++ tools/tools/sortbench/sort_bench.c @@ -0,0 +1,228 @@ +#include +#include +#include +#include +#include +#include + +#ifdef WIKI +#include "stdlib/wiki.c" +#endif + +/* + * Integer comparison function for stdlib sorting algorithms + */ +static int +sorthelp(const void *a, const void *b) +{ + if (*(int *)a > *(int *)b) + return 1; + if (*(int *)a < *(int *)b) + return -1; + return 0; +} + +#define NARGS 5 + +/* + * Enumerated types for the different types of tests and sorting algorithms + */ +enum test { RAND, SORT, PART, REV, INVALID_TEST }; + +#ifdef WIKI +enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG }; +#else +enum sort { MERGE, QUICK, HEAP, INVALID_ALG }; +#endif + +/* + * Sort an array with the given algorithm + */ +static void +sort(int *testarray, int elts, enum sort s) +{ + switch (s) { + case MERGE: + mergesort(testarray, (size_t)elts, sizeof(int), sorthelp); + break; +#ifdef WIKI + case WIKI: + WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp); + break; +#endif + case QUICK: + qsort(testarray, (size_t)elts, sizeof(int), sorthelp); + break; + case HEAP: + heapsort(testarray, (size_t)elts, sizeof(int), sorthelp); + break; + // Should never be reached + case INVALID_ALG: + exit(EX_DATAERR); + } +} + +/* + * Sort an array of randomly generated integers + */ +static void +rand_bench(int elts, enum sort s) +{ + size_t size = sizeof(int) * elts; + int *array = malloc(size); + arc4random_buf(array, size); + sort(array, elts, s); + free(array); +} + +/* + * Sort an array of increasing integers + */ +static void +sort_bench(int elts, enum sort s) +{ + size_t size = sizeof(int) * elts; + int *array = malloc(size); + for (int i = 0; i < elts; i++) { + array[i] = i; + } + sort(array, elts, s); + free(array); +} + +/* + * Sort an array of partially increasing, partially random integers + */ +static void +partial_bench(int elts, enum sort s) +{ + size_t size = sizeof(int) * elts; + int *array = malloc(size); + for (int i = 0; i < elts; i++) { + if (i <= elts / 2) + array[i] = i; + else + array[i] = arc4random(); + } + sort(array, elts, s); + free(array); +} + +/* + * Sort an array of decreasing integers + */ +static void +reverse_bench(int elts, enum sort s) +{ + size_t size = sizeof(int) * elts; + int *array = malloc(size); + for (int i = 0; i < elts; i++) { + array[i] = elts - i; + } + sort(array, elts, s); + free(array); +} + +static void +run_bench(enum sort s, enum test t, int runs, int elts) +{ + for (int i = 0; i < runs; i++) { + switch (t) { + case RAND: + rand_bench(elts, s); + break; + case SORT: + sort_bench(elts, s); + break; + case PART: + partial_bench(elts, s); + break; + case REV: + reverse_bench(elts, s); + break; + // Should never be reached + case INVALID_TEST: + exit(EX_DATAERR); + } + } +} + +static enum sort +parse_alg(char *alg) +{ + if (strcmp(alg, "merge") == 0) + return MERGE; +#ifdef WIKI + else if (strcmp(alg, "wiki") == 0) + return WIKI; +#endif + else if (strcmp(alg, "quick") == 0) + return QUICK; + else if (strcmp(alg, "heap") == 0) + return HEAP; + else + return INVALID_ALG; +} + +static enum test +parse_test(char *test) +{ + if (strcmp(test, "rand") == 0) + return RAND; + else if (strcmp(test, "sort") == 0) + return SORT; + else if (strcmp(test, "part") == 0) + return PART; + else if (strcmp(test, "rev") == 0) + return REV; + else + return INVALID_TEST; +} + +static void +usage(const char *progname) +{ + printf("Usage:\n"); + printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname); + printf("\n"); + printf("Valid algs:\n"); +#ifdef WIKI + printf("\theap merge quick wiki\n"); +#else + printf("\theap merge quick\n"); +#endif + printf("Valid tests:\n"); + printf("\trand sort part rev\n"); + printf("\trand: Random element array \n"); + printf("\tsort: Increasing order array \n"); + printf("\tpart: Partially ordered array\n"); + printf("\trev: Decreasing order array\n"); + printf("Run the algorithm [runs] times with 2^[elt_power] elements\n"); + exit(EX_USAGE); +} + +/* + * Runs a sorting algorithm with a provided data configuration according to + * command line arguments + */ +int +main(int argc, char *argv[]) +{ + const char *progname = argv[0]; + int runs, elts; + if (argc != NARGS) + usage(progname); + + enum sort s = parse_alg(argv[1]); + if (s == INVALID_ALG) + usage(progname); + + enum test t = parse_test(argv[2]); + if (t == INVALID_TEST) + usage(progname); + + runs = atoi(argv[3]); + elts = pow(2, atoi(argv[4])); + + run_bench(s, t, runs, elts); +}