tests/psort.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <sys/time.h>
   4
   5 #include <bsdtests.h>
   6
   7 typedef unsigned long T;
   8
   9 static int
  10 comparT(const void* a, const void* b) {
  11         const T x = *(T*)a, y = *(T*)b;
  12         return x < y ? -1 : x > y ? 1 : 0;
  13 }
  14
  15 static void
  16 test_psort(void)
  17 {
  18         struct timeval tv_start, tv_stop;
  19         struct rusage ru_start, ru_stop;
  20         unsigned long pwt, put, qwt, qut;
  21
  22         T *buf, *sorted;
  23         const size_t nel = 20480000;
  24         const size_t width = sizeof(T), bufsiz = nel * width;
  25
  26         buf = malloc(bufsiz);
  27         arc4random_buf(buf, bufsiz);
  28         sorted = malloc(bufsiz);
  29         memcpy(sorted, buf, bufsiz);
  30
  31         getrusage(RUSAGE_SELF, &ru_start);
  32         gettimeofday(&tv_start, NULL);
  33         psort(sorted, nel, width, comparT);
  34         gettimeofday(&tv_stop, NULL);
  35         getrusage(RUSAGE_SELF, &ru_stop);
  36
  37         pwt = ((uint64_t)tv_stop.tv_sec * USEC_PER_SEC + tv_stop.tv_usec) -
  38                         ((uint64_t)tv_start.tv_sec * USEC_PER_SEC + tv_start.tv_usec);
  39         put = ((uint64_t)ru_stop.ru_utime.tv_sec * USEC_PER_SEC + ru_stop.ru_utime.tv_usec) -
  40                         ((uint64_t)ru_start.ru_utime.tv_sec * USEC_PER_SEC + ru_start.ru_utime.tv_usec);
  41
  42         getrusage(RUSAGE_SELF, &ru_start);
  43         gettimeofday(&tv_start, NULL);
  44         qsort(buf, nel, width, comparT);
  45         gettimeofday(&tv_stop, NULL);
  46         getrusage(RUSAGE_SELF, &ru_stop);
  47
  48         qwt = ((uint64_t)tv_stop.tv_sec * USEC_PER_SEC + tv_stop.tv_usec) -
  49                         ((uint64_t)tv_start.tv_sec * USEC_PER_SEC + tv_start.tv_usec);
  50         qut = ((uint64_t)ru_stop.ru_utime.tv_sec * USEC_PER_SEC + ru_stop.ru_utime.tv_usec) -
  51                         ((uint64_t)ru_start.ru_utime.tv_sec * USEC_PER_SEC + ru_start.ru_utime.tv_usec);
  52
  53         bool match = true;
  54         for (size_t i = 0; i < nel; i++) {
  55                 if (!(match = (buf[i] == sorted[i]))) break;
  56         }
  57
  58         free(sorted);
  59         free(buf);
  60
  61         test_double_less_than_or_equal("psort/qsort wall time", (double)pwt/qwt, 1.0);
  62         test_double_less_than_or_equal("qsort/psort user time", (double)qut/put, 1.0);
  63         test_long("psort matches qsort", match, true);
  64 }
  65
  66 int main(void)
  67 {
  68         test_start("psort");
  69         test_psort();
  70         test_stop();
  71
  72         return 0;
  73 }