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  * $FreeBSD$
  30  */
  31
  32 #include <math.h>
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include <sysexits.h>
  37 #include <unistd.h>
  38
  39 #ifdef WIKI
  40 #include "stdlib/wiki.c"
  41 #endif
  42
  43 /*
  44  * Integer comparison function for stdlib sorting algorithms
  45  */
  46 static int
  47 sorthelp(const void *a, const void *b)
  48 {
  49         if (*(int *)a > *(int *)b)
  50                 return 1;
  51         if (*(int *)a < *(int *)b)
  52                 return -1;
  53         return 0;
  54 }
  55
  56 #define NARGS 5
  57
  58 /*
  59  * Enumerated types for the different types of tests and sorting algorithms
  60  */
  61 enum test { RAND, SORT, PART, REV, INVALID_TEST };
  62
  63 #ifdef WIKI
  64 enum sort { MERGE, WIKI, QUICK, HEAP, INVALID_ALG };
  65 #else
  66 enum sort { MERGE, QUICK, HEAP, INVALID_ALG };
  67 #endif
  68
  69 /*
  70  * Sort an array with the given algorithm
  71  */
  72 static void
  73 sort(int *testarray, int elts, enum sort s)
  74 {
  75         switch (s) {
  76         case MERGE:
  77                 mergesort(testarray, (size_t)elts, sizeof(int), sorthelp);
  78                 break;
  79 #ifdef WIKI
  80         case WIKI:
  81                 WikiSort(testarray, (size_t)elts, sizeof(int), sorthelp);
  82                 break;
  83 #endif
  84         case QUICK:
  85                 qsort(testarray, (size_t)elts, sizeof(int), sorthelp);
  86                 break;
  87         case HEAP:
  88                 heapsort(testarray, (size_t)elts, sizeof(int), sorthelp);
  89                 break;
  90         // Should never be reached
  91         case INVALID_ALG:
  92                 exit(EX_DATAERR);
  93         }
  94 }
  95
  96 /*
  97  * Sort an array of randomly generated integers
  98  */
  99 static void
 100 rand_bench(int elts, enum sort s)
 101 {
 102         size_t size = sizeof(int) * elts;
 103         int *array = malloc(size);
 104         arc4random_buf(array, size);
 105         sort(array, elts, s);
 106         free(array);
 107 }
 108
 109 /*
 110  * Sort an array of increasing integers
 111  */
 112 static void
 113 sort_bench(int elts, enum sort s)
 114 {
 115         size_t size = sizeof(int) * elts;
 116         int *array = malloc(size);
 117         for (int i = 0; i < elts; i++) {
 118                 array[i] = i;
 119         }
 120         sort(array, elts, s);
 121         free(array);
 122 }
 123
 124 /*
 125  * Sort an array of partially increasing, partially random integers
 126  */
 127 static void
 128 partial_bench(int elts, enum sort s)
 129 {
 130         size_t size = sizeof(int) * elts;
 131         int *array = malloc(size);
 132         for (int i = 0; i < elts; i++) {
 133                 if (i <= elts / 2)
 134                         array[i] = i;
 135                 else
 136                         array[i] = arc4random();
 137         }
 138         sort(array, elts, s);
 139         free(array);
 140 }
 141
 142 /*
 143  * Sort an array of decreasing integers
 144  */
 145 static void
 146 reverse_bench(int elts, enum sort s)
 147 {
 148         size_t size = sizeof(int) * elts;
 149         int *array = malloc(size);
 150         for (int i = 0; i < elts; i++) {
 151                 array[i] = elts - i;
 152         }
 153         sort(array, elts, s);
 154         free(array);
 155 }
 156
 157 static void
 158 run_bench(enum sort s, enum test t, int runs, int elts)
 159 {
 160         for (int i = 0; i < runs; i++) {
 161                 switch (t) {
 162                 case RAND:
 163                         rand_bench(elts, s);
 164                         break;
 165                 case SORT:
 166                         sort_bench(elts, s);
 167                         break;
 168                 case PART:
 169                         partial_bench(elts, s);
 170                         break;
 171                 case REV:
 172                         reverse_bench(elts, s);
 173                         break;
 174                 // Should never be reached
 175                 case INVALID_TEST:
 176                         exit(EX_DATAERR);
 177                 }
 178         }
 179 }
 180
 181 static enum sort
 182 parse_alg(char *alg)
 183 {
 184         if (strcmp(alg, "merge") == 0)
 185                 return MERGE;
 186 #ifdef WIKI
 187         else if (strcmp(alg, "wiki") == 0)
 188                 return WIKI;
 189 #endif
 190         else if (strcmp(alg, "quick") == 0)
 191                 return QUICK;
 192         else if (strcmp(alg, "heap") == 0)
 193                 return HEAP;
 194         else
 195                 return INVALID_ALG;
 196 }
 197
 198 static enum test
 199 parse_test(char *test)
 200 {
 201         if (strcmp(test, "rand") == 0)
 202                 return RAND;
 203         else if (strcmp(test, "sort") == 0)
 204                 return SORT;
 205         else if (strcmp(test, "part") == 0)
 206                 return PART;
 207         else if (strcmp(test, "rev") == 0)
 208                 return REV;
 209         else
 210                 return INVALID_TEST;
 211 }
 212
 213 static void
 214 usage(const char *progname)
 215 {
 216         printf("Usage:\n");
 217         printf("\t%s: [alg] [test] [runs] [elt_power]\n", progname);
 218         printf("\n");
 219         printf("Valid algs:\n");
 220 #ifdef WIKI
 221         printf("\theap merge quick wiki\n");
 222 #else
 223         printf("\theap merge quick\n");
 224 #endif
 225         printf("Valid tests:\n");
 226         printf("\trand sort part rev\n");
 227         printf("\trand: Random element array \n");
 228         printf("\tsort: Increasing order array \n");
 229         printf("\tpart: Partially ordered array\n");
 230         printf("\trev: Decreasing order array\n");
 231         printf("Run the algorithm [runs] times with 2^[elt_power] elements\n");
 232         exit(EX_USAGE);
 233 }
 234
 235 /*
 236  * Runs a sorting algorithm with a provided data configuration according to
 237  * command line arguments
 238  */
 239 int
 240 main(int argc, char *argv[])
 241 {
 242         const char *progname = argv[0];
 243         int runs, elts;
 244         if (argc != NARGS)
 245                 usage(progname);
 246
 247         enum sort s = parse_alg(argv[1]);
 248         if (s == INVALID_ALG)
 249                 usage(progname);
 250
 251         enum test t = parse_test(argv[2]);
 252         if (t == INVALID_TEST)
 253                 usage(progname);
 254
 255         runs = atoi(argv[3]);
 256         elts = pow(2, atoi(argv[4]));
 257
 258         run_bench(s, t, runs, elts);
 259 }