Page MenuHomeFreeBSD
Files F154325657

D12677.id34117.diff
No OneTemporary
Actions

D12677.id34117.diff
View Options

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 <bsd.prog.mk>
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 <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);
+}

File Metadata

Mime Type
text/plain
Expires
Tue, Apr 28, 8:50 PM (9 h, 26 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
32288682
Default Alt Text
D12677.id34117.diff (7 KB)

Event Timeline