Author: brooks Date: Thu Apr 19 21:53:57 2018 New Revision: 332796 URL: https://svnweb.freebsd.org/changeset/base/332796
Log: Add sortbench. This is a set of benchmarks of qsort, mergesort, heapsort, and optionally wikisort and a script to run them. Submitted by: Miles Fertel <milesfer...@college.harvard.edu> Sponsored by: Google Summer of Code 2017 Differential Revision: https://reviews.freebsd.org/D12677 Added: head/tools/tools/sortbench/ head/tools/tools/sortbench/Makefile (contents, props changed) head/tools/tools/sortbench/README (contents, props changed) head/tools/tools/sortbench/bench.py (contents, props changed) head/tools/tools/sortbench/sort_bench.c (contents, props changed) Added: head/tools/tools/sortbench/Makefile ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/tools/tools/sortbench/Makefile Thu Apr 19 21:53:57 2018 (r332796) @@ -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 <bsd.prog.mk> Added: head/tools/tools/sortbench/README ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/tools/tools/sortbench/README Thu Apr 19 21:53:57 2018 (r332796) @@ -0,0 +1,17 @@ +$FreeBSD$ + +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. Added: head/tools/tools/sortbench/bench.py ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/tools/tools/sortbench/bench.py Thu Apr 19 21:53:57 2018 (r332796) @@ -0,0 +1,72 @@ +#!/usr/bin/env python +""" +Copyright (c) 2017 Miles Fertel +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions +are met: +1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. +2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + +THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE +FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +SUCH DAMAGE. + + $FreeBSD$ +""" + +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) + Added: head/tools/tools/sortbench/sort_bench.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/tools/tools/sortbench/sort_bench.c Thu Apr 19 21:53:57 2018 (r332796) @@ -0,0 +1,259 @@ +/*- + * Copyright (c) 2017 Miles Fertel + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer, + * without modification. + * 2. Redistributions in binary form must reproduce at minimum a disclaimer + * similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any + * redistribution must be conditioned upon including a substantially + * similar Disclaimer requirement for further binary redistribution. + * + * NO WARRANTY + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY + * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL + * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, + * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER + * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGES. + * + * $FreeBSD$ + */ + +#include <math.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sysexits.h> +#include <unistd.h> + +#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); +} _______________________________________________ svn-src-head@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
