svn commit: r332796 - head/tools/tools/sortbench
Brooks Davis
brooks at FreeBSD.org
Thu Apr 19 21:53:58 UTC 2018
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 <milesfertel at 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);
+}
More information about the svn-src-all
mailing list