tools/tools/sortbench/sort_bench.c

   1 /*-
   2  * Copyright (c) 2017 Miles Fertel
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer,
  10  *    without modification.
  11  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
  12  *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
  13  *    redistribution must be conditioned upon including a substantially
  14  *    similar Disclaimer requirement for further binary redistribution.
  15  *
  16  * NO WARRANTY
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
  20  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
  21  * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
  22  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
  25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  27  * THE POSSIBILITY OF SUCH DAMAGES.
  28  */
  29
  30 #include <math.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <sysexits.h>
  35 #include <unistd.h>
  36
  37 #ifdef WIKI
  38 #include "stdlib/wiki.c"
  39 #endif
  40
  41 /*
  42  * Integer comparison function for stdlib sorting algorithms
  43  */
  44 static int
  45 sorthelp(const void *a, const void *b)
  46 {
  47         if (*(int *)a > *(int *)b)
  48                 return 1;
  49         if (*(int *)a < *(int *)b)
  50                 return -1;
  51         return 0;
  52 }
  53
  54 #define NARGS 5
  55
  56 /*
  57  * Enumerated types for the different types of tests and sorting algorithms
  58  */
  59 enum test { RAND, SORT, PART, REV, INVALID_TEST };
  60
  61 #ifdef WIKI
  62 enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
  63 #else
  64 enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
  65 #endif
  66
  67 /*
  68  * Sort an array with the given algorithm
  69  */
  70 static void
  71 sort(int *testarray, int elts, enum sort s)
  72 {
  73         switch (s) {
  74         case MERGE:
  75                 mergesort(testarray, (size_t)elts, sizeof(int), sorthelp);
  76                 break;
  77 #ifdef WIKI
  78         case WIKI:
  79                 WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp);
  80                 break;
  81 #endif
  82         case QUICK:
  83                 qsort(testarray, (size_t)elts, sizeof(int), sorthelp);
  84                 break;
  85         case HEAP:
  86                 heapsort(testarray, (size_t)elts, sizeof(int), sorthelp);
  87                 break;
  88         // Should never be reached
  89         case INVALID_ALG:
  90                 exit(EX_DATAERR);
  91         }
  92 }
  93
  94 /*
  95  * Sort an array of randomly generated integers
  96  */
  97 static void
  98 rand_bench(int elts, enum sort s)
  99 {
 100         size_t size = sizeof(int) * elts;
 101         int *array = malloc(size);
 102         arc4random_buf(array, size);
 103         sort(array, elts, s);
 104         free(array);
 105 }
 106
 107 /*
 108  * Sort an array of increasing integers
 109  */
 110 static void
 111 sort_bench(int elts, enum sort s)
 112 {
 113         size_t size = sizeof(int) * elts;
 114         int *array = malloc(size);
 115         for (int i = 0; i < elts; i++) {
 116                 array[i] = i;
 117         }
 118         sort(array, elts, s);
 119         free(array);
 120 }
 121
 122 /*
 123  * Sort an array of partially increasing, partially random integers
 124  */
 125 static void
 126 partial_bench(int elts, enum sort s)
 127 {
 128         size_t size = sizeof(int) * elts;
 129         int *array = malloc(size);
 130         for (int i = 0; i < elts; i++) {
 131                 if (i <= elts / 2)
 132                         array[i] = i;
 133                 else
 134                         array[i] = arc4random();
 135         }
 136         sort(array, elts, s);
 137         free(array);
 138 }
 139
 140 /*
 141  * Sort an array of decreasing integers
 142  */
 143 static void
 144 reverse_bench(int elts, enum sort s)
 145 {
 146         size_t size = sizeof(int) * elts;
 147         int *array = malloc(size);
 148         for (int i = 0; i < elts; i++) {
 149                 array[i] = elts - i;
 150         }
 151         sort(array, elts, s);
 152         free(array);
 153 }
 154
 155 static void
 156 run_bench(enum sort s, enum test t, int runs, int elts)
 157 {
 158         for (int i = 0; i < runs; i++) {
 159                 switch (t) {
 160                 case RAND:
 161                         rand_bench(elts, s);
 162                         break;
 163                 case SORT:
 164                         sort_bench(elts, s);
 165                         break;
 166                 case PART:
 167                         partial_bench(elts, s);
 168                         break;
 169                 case REV:
 170                         reverse_bench(elts, s);
 171                         break;
 172                 // Should never be reached
 173                 case INVALID_TEST:
 174                         exit(EX_DATAERR);
 175                 }
 176         }
 177 }
 178
 179 static enum sort
 180 parse_alg(char *alg)
 181 {
 182         if (strcmp(alg, "merge") == 0)
 183                 return MERGE;
 184 #ifdef WIKI
 185         else if (strcmp(alg, "wiki") == 0)
 186                 return WIKI;
 187 #endif
 188         else if (strcmp(alg, "quick") == 0)
 189                 return QUICK;
 190         else if (strcmp(alg, "heap") == 0)
 191                 return HEAP;
 192         else
 193                 return INVALID_ALG;
 194 }
 195
 196 static enum test
 197 parse_test(char *test)
 198 {
 199         if (strcmp(test, "rand") == 0)
 200                 return RAND;
 201         else if (strcmp(test, "sort") == 0)
 202                 return SORT;
 203         else if (strcmp(test, "part") == 0)
 204                 return PART;
 205         else if (strcmp(test, "rev") == 0)
 206                 return REV;
 207         else
 208                 return INVALID_TEST;
 209 }
 210
 211 static void
 212 usage(const char *progname)
 213 {
 214         printf("Usage:\n");
 215         printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname);
 216         printf("\n");
 217         printf("Valid algs:\n");
 218 #ifdef WIKI
 219         printf("\theap merge quick wiki\n");
 220 #else
 221         printf("\theap merge quick\n");
 222 #endif
 223         printf("Valid tests:\n");
 224         printf("\trand sort part rev\n");
 225         printf("\trand: Random element array \n");
 226         printf("\tsort: Increasing order array \n");
 227         printf("\tpart: Partially ordered array\n");
 228         printf("\trev: Decreasing order array\n");
 229         printf("Run the algorithm [runs] times with 2^[elt_power] elements\n");
 230         exit(EX_USAGE);
 231 }
 232
 233 /*
 234  * Runs a sorting algorithm with a provided data configuration according to
 235  * command line arguments
 236  */
 237 int
 238 main(int argc, char *argv[])
 239 {
 240         const char *progname = argv[0];
 241         int runs, elts;
 242         if (argc != NARGS)
 243                 usage(progname);
 244
 245         enum sort s = parse_alg(argv[1]);
 246         if (s == INVALID_ALG)
 247                 usage(progname);
 248
 249         enum test t = parse_test(argv[2]);
 250         if (t == INVALID_TEST)
 251                 usage(progname);
 252
 253         runs = atoi(argv[3]);
 254         elts = pow(2, atoi(argv[4]));
 255
 256         run_bench(s, t, runs, elts);
 257 }