Index: lib/libc/tests/stdlib/Makefile =================================================================== --- lib/libc/tests/stdlib/Makefile +++ lib/libc/tests/stdlib/Makefile @@ -47,6 +47,7 @@ PROGS+= h_getopt h_getopt_long CFLAGS+= -I${.CURDIR} +CFLAGS+= -I${.CURDIR:H:H} CXXFLAGS.cxa_thread_atexit_test+= -std=c++11 CXXFLAGS.cxa_thread_atexit_nothr_test+= -std=c++11 Index: lib/libc/tests/stdlib/mergesort_test.c =================================================================== --- lib/libc/tests/stdlib/mergesort_test.c +++ lib/libc/tests/stdlib/mergesort_test.c @@ -29,16 +29,160 @@ */ #include -__FBSDID("$FreeBSD$"); +__FBSDID("$FreeBSD: head/lib/libc/tests/stdlib/mergesort_test.c 290538 2015-11-08 07:03:17Z ngie $"); #include +#include #include #include +#include "stdlib/wiki.c" #include "test-sort.h" -ATF_TC_WITHOUT_HEAD(mergesort_test); -ATF_TC_BODY(mergesort_test, tc) +#define ELT_MAX 16 +/* + * Number of keys in stability test. + * Chosen to be low enough that every element would probabilistically need + * to be properly ordered for stability, without being trivially small. + */ +#define KEYS 50 +/* + * Definitions for sizeable_WikiSort_test + * Test from 2^BASE to 2^MAX elements of type SORT_TYPE + */ +#define BASE 10 +#define MAX 27 +#define SORT_TYPE int + +/* + * Structures to allow for the creation of predefined variable sized arrays. + * The len field is necessary to determine how many elements are being used + * in the elts array + */ +struct int_array { + int len; + int elts[ELT_MAX]; +}; + +struct char_array { + int len; + char elts[ELT_MAX]; +}; + +/* + * Sorting arrays of small size and simple element combinations to ensure + * basic competency. + */ +ATF_TC_WITHOUT_HEAD(trivial_mergesort_test); +ATF_TC_BODY(trivial_mergesort_test, tc) +{ + static const struct int_array testarrays[] = { + {1, {0}}, {2, {0, 0}}, {3, {0, 0, 0}}, {2, {0, 1}}, + {2, {1, 0}}, {3, {0, 1, 2}}, {3, {0, 2, 1}}, {3, {1, 0, 2}}, + {3, {1, 2, 0}}, {3, {2, 0, 1}}, {3, {2, 1, 0}}, {3, {0, 1, 1}}, + {3, {1, 0, 1}}, {3, {1, 1, 0}}, {3, {0, -1, -1}}, {3, {0, -1, 0}}}; + + int sresvector[ELT_MAX]; + int testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + + for (int i = 0; i < num_tests; i++) { + int len = testarrays[i].len; + + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, len); + memcpy(sresvector, testarrays[i].elts, len); + + /* Sort using WikiSort */ + WikiSort(testvector, len, sizeof(testvector[0]), sorthelp); + /* Sort using reference slow sorting routine */ + ssort(sresvector, len); + + for (int k = 0; k < len; k++) + ATF_CHECK_MSG(testvector[k] == sresvector[k], + "item at index %d didn't match: %d != %d", + k, testvector[k], sresvector[k]); + } +} + +/* + * Sorting arrays in which the elements are either ordered, partially ordered, + * or reverse ordered. + */ +ATF_TC_WITHOUT_HEAD(ordering_mergesort_test); +ATF_TC_BODY(ordering_mergesort_test, tc) +{ + static const struct int_array testarrays[] = { + {3, {-1, -2, -3}}, + {3, {-3, -2, -1}}, + {11, {1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1}}, + {10, {5, 5, 4, 4, 3, 3, 2, 2, 1, 1}}, + {10, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}, + {10, {1, 2, 3, 4, 5, 6, -7, -8, -9, -10}}, + {10, {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}}}; + + int sresvector[ELT_MAX]; + int testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + + for (int i = 0; i < num_tests; i++) { + int len = testarrays[i].len; + + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, len); + memcpy(sresvector, testarrays[i].elts, len); + + /* Sort using WikiSort */ + WikiSort(testvector, len, sizeof(testvector[0]), sorthelp); + /* Sort using reference slow sorting routine */ + ssort(sresvector, len); + + for (int k = 0; k < len; k++) + ATF_CHECK_MSG(testvector[k] == sresvector[k], + "item at index %d didn't match: %d != %d", + k, testvector[k], sresvector[k]); + } +} + +/* + * Sorting arrays with a variety of challenges: i.e. max integer values, + * multiple identical values, etc. + */ +ATF_TC_WITHOUT_HEAD(misc_mergesort_test); +ATF_TC_BODY(misc_mergesort_test, tc) +{ + static const struct int_array testarrays[] = { + {10, {42, 9, 17, 123, 602, -3, 123, 969, -11, INT_MAX}}, + {10, {-11, -3, 9, 17, 42, 54, 54, 602, 969, INT_MIN}}}; + + int sresvector[ELT_MAX]; + int testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + + for (int i = 0; i < num_tests; i++) { + int len = testarrays[i].len; + + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, len); + memcpy(sresvector, testarrays[i].elts, len); + + /* Sort using WikiSort */ + WikiSort(testvector, len, sizeof(testvector[0]), sorthelp); + /* Sort using reference slow sorting routine */ + ssort(sresvector, len); + + for (int j = 0; j < len; k++) + ATF_CHECK_MSG(testvector[j] == sresvector[j], + "item at index %d didn't match: %d != %d", + j, testvector[j], sresvector[j]); + } +} + +/* + * Sort an array of random integers. + */ +ATF_TC_WITHOUT_HEAD(rand_mergesort_test); +ATF_TC_BODY(rand_mergesort_test, tc) { int sresvector[IVEC_LEN]; int testvector[IVEC_LEN]; @@ -46,11 +190,11 @@ for (j = 2; j < IVEC_LEN; j++) { /* Populate test vectors */ - for (i = 0; i < j; i++) - testvector[i] = sresvector[i] = initvector[i]; + memcpy(testvector, initvector, j); + memcpy(sresvector, initvector, j); - /* Sort using mergesort(3) */ - mergesort(testvector, j, sizeof(testvector[0]), sorthelp); + /* Sort using WikiSort */ + WikiSort(testvector, j, sizeof(testvector[0]), sorthelp); /* Sort using reference slow sorting routine */ ssort(sresvector, j); @@ -62,10 +206,386 @@ } } -ATF_TP_ADD_TCS(tp) +/* + * Sort an array of chars + */ +ATF_TC_WITHOUT_HEAD(small_elt_mergesort_test); +ATF_TC_BODY(small_elt_mergesort_test, tc) +{ + static const struct char_array testarrays[] = { + {1, {0}}, + {2, {0, 0}}, + {3, {0, 0, 0}}, + {2, {0, 1}}, + {2, {1, 0}}, + {3, {0, 1, 2}}, + {3, {0, 2, 1}}, + {3, {1, 0, 2}}, + {3, {1, 2, 0}}, + {3, {2, 0, 1}}, + {3, {2, 1, 0}}, + {3, {0, 1, 1}}, + {3, {1, 0, 1}}, + {3, {1, 1, 0}}, + {3, {0, -1, -1}}, + {3, {0, -1, 0}}, + {3, {-1, -2, -3}}, + {3, {-3, -2, -1}}, + {11, {1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1}}, + {10, {5, 5, 4, 4, 3, 3, 2, 2, 1, 1}}, + {10, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}, + {10, {1, 2, 3, 4, 5, 6, -7, -8, -9, -10}}, + {10, {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}}, + {10, {42, 9, 17, 123, 62, -3, 123, 99, -11, CHAR_MAX}}, + {10, {-11, -3, 9, 17, 42, 54, 54, -62, 9, CHAR_MIN}}}; + + char sresvector[ELT_MAX]; + char testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + + for (int i = 0; i < num_tests; i++) { + int len = testarrays[i].len; + /* Populate test vectors */ + memcpy(testvector, testarrays[i].elts, len); + memcpy(sresvector, testarrays[i].elts, len); + + /* Sort using WikiSort */ + WikiSort(testvector, len, sizeof(testvector[0]), csorthelp); + /* Sort using reference slow sorting routine */ + scsort(sresvector, len); + + for (int j = 0; j < len; j++) + ATF_CHECK_MSG(testvector[j] == sresvector[j], + "item at index %d didn't match: %d != %d", + j, testvector[j], sresvector[j]); +} +} + +/* + * Sort an array of char[5] arrays. Tests for possible alignment issues. + */ +ATF_TC_WITHOUT_HEAD(oddelt_WikiSort_test); +ATF_TC_BODY(oddelt_WikiSort_test, tc) +{ +#define NCHARS 5 + struct odd_array { + int len; + char elts[ELT_MAX][NCHARS]; + }; + + static const struct odd_array testarrays[] = { + {2, {{0, 1, 2, 3, 4}, {1, 2, 3, 4, 5}}}, + {3, {{1, 2, 3, 4, 5}, {0, 1, 2, 3, 4}, {2, 3, 1, 0, 0}}}, + {3, {{-1, 2, -3, 4, 5}, {0, 1, 2, -3, 4}, {2, 3, -1, 0, 0}}}, + {3, {{-1, 7, 4, 0, 0}, {0, 1, 2, 0, 0}, {4, 3, 5, 0, 0}}}, + {3, {{1, 7, 4, 0, 0}, {0, 1, -2, 0, 0}, {4, -3, 5, 0, 0}}}, + {10, + {{-1, 0, 0, 0, 0}, + {-2, 0, 0, 0, 0}, + {-3, 0, 0, 0, 0}, + {-4, 0, 0, 0, 0}, + {-5, 0, 0, 0, 0}, + {-6, 0, 0, 0, 0}, + {-7, 0, 0, 0, 0}, + {-8, 0, 0, 0, 0}, + {-9, 0, 0, 0, 0}, + {-10, 0, 0, 0, 0}}}}; + + char sresvector[ELT_MAX][NCHARS]; + char testvector[ELT_MAX][NCHARS]; + int num_tests = nitems(testarrays); + + for (int i = 0; i < num_tests; i++) { + int len = testarrays[i].len; + /* Populate test vectors */ + for (int j = 0; j < len; j++) { + for (int k = 0; k < NCHARS; k++) + testvector[j][k] = sresvector[j][k] = + testarrays[i].elts[j][k]; + } + /* Sort using WikiSort */ + WikiSort(testvector, len, sizeof(testvector[0]), oddsorthelp); + /* Sort using reference slow sorting routine */ + mergesort(sresvector, len, sizeof(sresvector[0]), oddsorthelp); + for (int j = 0; j < len; j++) + for (int k = 0; k < NCHARS; k++) { + ATF_CHECK_MSG(testvector[j][k] != + sresvector[j][k], + "item at index %d didn't match: %d != %d\n", + j, testvector[j][k], sresvector[j][k]); + } + } +} + +/* + * Sort an array of int*'s + */ +ATF_TC_WITHOUT_HEAD(pointer_WikiSort_test); +ATF_TC_BODY(pointer_WikiSort_test, tc) +{ + struct ptr_array { + int len; + int *elts[ELT_MAX]; + }; + + static const struct ptr_array testarrays[] = { + {3, {NULL, (int *)0x200, (int *)0x100}}, + {3, {(int *)0xFFFF, (int *)0xFFFE, (int *)0xFFFD}}, + {3, {NULL, NULL, NULL}}, + {6, + {(int *)0xFFFFFFFF, (int *)0x100000000, NULL, (int *)1234, + (int *)0x1234, (int *)0xFFFFFFFF}}}; + + int *sresvector[ELT_MAX]; + int *testvector[ELT_MAX]; + int num_tests = nitems(testarrays); + + for (int i = 0; i < num_tests; i++) { + int len = testarrays[i].len; + /* Populate test vectors */ + for (int j = 0; j < len; j++) + testvector[j] = sresvector[j] = testarrays[i].elts[j]; + /* Sort using WikiSort */ + WikiSort(testvector, len, sizeof(testvector[0]), ptrsorthelp); + /* Reference sort */ + mergesort(sresvector, len, sizeof(testvector[0]), ptrsorthelp); + + for (int k = 0; k < len; k++) + ATF_CHECK_MSG(testvector[k] != sresvector[k], + "item at index %d didn't match: %p != %p\n", + k, testvector[k], sresvector[k]); + } +} + +/* + * Sort an array of random int*'s + */ +ATF_TC_WITHOUT_HEAD(rand_pointer_WikiSort_test); +ATF_TC_BODY(rand_pointer_WikiSort_test, tc) +{ + int *rand_sresvector[IVEC_LEN]; + int *rand_testvector[IVEC_LEN]; + int i, j; + + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) + rand_testvector[i] = rand_sresvector[i] = + &(initvector[rand() % IVEC_LEN]); + + /* Sort using WikiSort */ + WikiSort(rand_testvector, j, sizeof(rand_testvector[0]), + ptrsorthelp); + /* Reference sort */ + mergesort(rand_sresvector, j, sizeof(rand_sresvector[0]), + ptrsorthelp); + + /* Compare results */ + for (i = 0; i < j; i++) + ATF_CHECK_MSG(rand_testvector[i] != rand_sresvector[i], + "item at index %d didn't match: %p != %p\n", + i, rand_testvector[i], rand_sresvector[i]); + } +} + +/* + * Sort an array of nontrivially large structs + */ +ATF_TC_WITHOUT_HEAD(bigstruct_WikiSort_test); +ATF_TC_BODY(bigstruct_WikiSort_test, tc) +{ + struct big sresvector[IVEC_LEN]; + struct big testvector[IVEC_LEN]; + int i, j; + + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) + testvector[i].value = sresvector[i].value = + initvector[i]; + + /* Sort using WikiSort */ + WikiSort(testvector, j, sizeof(testvector[0]), bigsorthelp); + /* Reference sort */ + mergesort(sresvector, j, sizeof(testvector[0]), bigsorthelp); + + /* Compare results */ + for (i = 0; i < j; i++) + ATF_CHECK_MSG(testvector[i].value != + sresvector[i].value, + "item at index %d didn't match: %d != %d\n", + i, testvector[i].value, sresvector[i].value); + } +} + +/* + * Sort an array of structs with identical values but different keys in order + * to check for stability. The sorted elements with the same value should + * be in the same order by key. + */ +ATF_TC_WITHOUT_HEAD(stability_WikiSort_test); +ATF_TC_BODY(stability_WikiSort_test, tc) +{ + struct stable sresvector[IVEC_LEN]; + struct stable testvector[IVEC_LEN]; + int i, j; + int keys[KEYS] = {0}; + for (j = 2; j < IVEC_LEN; j++) { + /* Populate test vectors */ + for (i = 0; i < j; i++) { + int value = rand() % KEYS; + testvector[i].value = sresvector[i].value = value; + testvector[i].key = sresvector[i].key = keys[value]; + keys[value]++; + } + + /* Sort using WikiSort */ + WikiSort(testvector, j, sizeof(testvector[0]), stablesorthelp); + /* Reference sort */ + mergesort(sresvector, j, sizeof(testvector[0]), stablesorthelp); + + /* Compare results */ + for (i = 0; i < j; i++) { + ATF_CHECK_MSG(testvector[i].value != + sresvector[i].value || + testvector[i].key != sresvector[i].key, + "item at index %d didn't match: value %d " + "!= %d or key %d != %d\n", + i, testvector[i].value, sresvector[i].value, + testvector[i].key, sresvector[i].key); + } + } +} + +static void +check(SORT_TYPE *array1, SORT_TYPE *array2, int elts) { + for (int k = 0; k < elts; k++) + ATF_CHECK_MSG(array1[k] == array2[k], + "item at index %d didn't match: %d != %d", + k, array1[k],array2[k]); +} + +static void +rand_test(int elts) +{ + SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts); + SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts); + + for (int i = 0; i < elts; i++) { + testvector[i] = sresvector[i] = rand(); + } + + /* Sort using WikiSort */ + WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + + check(testvector, sresvector, elts); + + free(testvector); + free(sresvector); +} + +static void +sort_test(int elts) +{ + SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts); + SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts); + + for (int i = 0; i < elts; i++) { + testvector[i] = sresvector[i] = i; + } + + /* Sort using WikiSort */ + WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + + check(testvector, sresvector, elts); + + free(testvector); + free(sresvector); +} + +static void +partial_test(int elts) +{ + SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts); + SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts); + + for (int i = 0; i < elts; i++) { + if (i <= elts / 2) + testvector[i] = sresvector[i] = i; + else + testvector[i] = sresvector[i] = rand(); + } + + /* Sort using WikiSort */ + WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); - ATF_TP_ADD_TC(tp, mergesort_test); + check(testvector, sresvector, elts); + + free(testvector); + free(sresvector); +} + +static void +reverse_test(int elts) +{ + SORT_TYPE *testvector = malloc(sizeof(SORT_TYPE) * elts); + SORT_TYPE *sresvector = malloc(sizeof(SORT_TYPE) * elts); + + for (int i = 0; i < elts; i++) { + testvector[i] = sresvector[i] = elts - i; + } + + /* Sort using WikiSort */ + WikiSort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + /* Sort using reference sorting routine */ + mergesort(testvector, elts, sizeof(SORT_TYPE), sorthelp); + + check(testvector, sresvector, elts); + + free(testvector); + free(sresvector); +} + +/* + * Sort an array of integers from 2^BASE to 2^MAX elements + */ +ATF_TC_WITHOUT_HEAD(sizeable_WikiSort_test); +ATF_TC_BODY(sizeable_WikiSort_test, tc) +{ + int max = pow(2, MAX); + int base = pow(2, BASE); + for (int elts = base; elts < max; elts *= 2) { + rand_test(elts); + sort_test(elts); + partial_test(elts); + reverse_test(elts); + } +} + + +/* + * Test cases to ensure correctness of stdlib mergesort function + */ +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, trivial_mergesort_test); + ATF_TP_ADD_TC(tp, ordering_mergesort_test); + ATF_TP_ADD_TC(tp, misc_mergesort_test); + ATF_TP_ADD_TC(tp, rand_mergesort_test); + ATF_TP_ADD_TC(tp, small_elt_mergesort_test); + ATF_TP_ADD_TC(tp, oddelt_WikiSort_test); + ATF_TP_ADD_TC(tp, pointer_WikiSort_test); + ATF_TP_ADD_TC(tp, rand_pointer_WikiSort_test); + ATF_TP_ADD_TC(tp, bigstruct_WikiSort_test); + ATF_TP_ADD_TC(tp, stability_WikiSort_test); + ATF_TP_ADD_TC(tp, sizeable_WikiSort_test); return (atf_no_error()); } Index: lib/libc/tests/stdlib/test-sort.h =================================================================== --- lib/libc/tests/stdlib/test-sort.h +++ lib/libc/tests/stdlib/test-sort.h @@ -23,7 +23,7 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * $FreeBSD$ + * $FreeBSD: head/lib/libc/tests/stdlib/test-sort.h 290538 2015-11-08 07:03:17Z ngie $ */ #ifndef _TEST_SORT_H @@ -33,6 +33,9 @@ #include +/* + * Integer comparison function for stdlib sorting algorithms + */ static int sorthelp(const void *a, const void *b) { @@ -48,7 +51,116 @@ return (0); } -/* Reference sorting routine (slooow!) */ +/* + * Char comparison function for stdlib sorting algorithms + */ +static int +csorthelp(const void *a, const void *b) +{ + const char *oa, *ob; + + oa = a; + ob = b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (*oa < *ob) + return (-1); + if (*oa > *ob) + return (1); + return (0); +} + +/* + * Char[5] comparison function for stdlib sorting algorithms + * Simply sorts the arrays by the first element of each array + */ +static int +oddsorthelp(const void *a, const void *b) +{ + const char(*oa)[3], (*ob)[3]; + + oa = a; + ob = b; + /* Don't use "return *oa[0] - *ob[0]" since it's easy to cause overflow! */ + if (*oa[0] > *ob[0]) + return (1); + if (*oa[0] < *ob[0]) + return (-1); + return (0); +} + +/* + * Int* comparison function for stdlib sorting algorithms + */ +static int +ptrsorthelp(const void *a, const void *b) +{ + const int **oa, **ob; + oa = (const int **)a; + ob = (const int **)b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (*oa > *ob) + return (1); + if (*oa < *ob) + return (-1); + return (0); +} + +/* + * Struct used to test stdlib sorting algorithms ability to sort nontrivially + * large elements + */ +struct big { + int value; + int spacetaker[100]; +}; + +/* + * Struct big comparison function for stdlib sorting algorithms + */ +static int +bigsorthelp(const void *a, const void *b) +{ + const struct big *oa, *ob; + oa = a; + ob = b; + /* + * Don't use "return oa->value - *ob->value" + * since it's easy to cause overflow! + */ + if (oa->value > ob->value) + return (1); + if (oa->value < ob->value) + return (-1); + return (0); +} + +/* + * Struct used to test stdlib sorting algorithms ability to sort data with + * stability + */ +struct stable { + int key; + int value; +}; + +/* + * Struct stable comparison function for stdlib sorting algorithms + */ +static int +stablesorthelp(const void *a, const void *b) +{ + const struct stable *oa, *ob; + oa = a; + ob = b; + /* Don't use "return *oa - *ob" since it's easy to cause overflow! */ + if (oa->value > ob->value) + return (1); + if (oa->value < ob->value) + return (-1); + return (0); +} + +/* Reference sorting routine for integers (slooow!) */ static void ssort(int v[], int nmemb) { @@ -65,6 +177,24 @@ } } +/* Reference sorting routine for chars (slooow!) */ +static void +scsort(char v[], int nmemb) +{ + int i, j; + char k; + + for (i = 0; i < nmemb; i++) { + for (j = i + 1; j < nmemb; j++) { + if (v[j] < v[i]) { + k = v[i]; + v[i] = v[j]; + v[j] = k; + } + } + } +} + /* Some random data */ static int initvector[1024] = { 599853225, 371951333, -428880425, 1450668530, 85530178, -460170550, Index: tools/tools/msortbench/Makefile =================================================================== --- /dev/null +++ tools/tools/msortbench/Makefile @@ -0,0 +1,7 @@ +# $FreeBSD$ + +PROG= mergesort_bench +CFLAGS+=-I${SRCTOP}/lib/libc +MAN= + +.include Index: tools/tools/msortbench/README =================================================================== --- /dev/null +++ tools/tools/msortbench/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/msortbench/bench.py =================================================================== --- /dev/null +++ tools/tools/msortbench/bench.py @@ -0,0 +1,73 @@ +""" +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$ + """ + +#!/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 = "mergesort_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/msortbench/mergesort_bench.c =================================================================== --- /dev/null +++ tools/tools/msortbench/mergesort_bench.c @@ -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 +#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); +} 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); +}