stackoverflow-9846681.c

/* Testing sort - stackoverflow topic 9846681
 * Compares sorts on float 'val':
 *  -q qsort,
 *  -m mergesort,
 *  -h heapsort
 * Reordering could be by the same type of sort on idx - default or
 *  -c by copying to a second array
 *
 * Note: timing is Mac OS X specific, and uses mach timing mechanisms.
 *
 * Copyright G Bulmer 2012
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <mach/mach.h>
#include <mach/mach_time.h>


static mach_timebase_info_data_t sTimebaseInfo; /* OS X nanoseconds clock */
static struct timeval start_time;           /* wall clock start time */
static struct timeval end_time;             /* wall clock end time */
static struct rusage initial_rUsage;        /* initial time (resource) use */
static struct rusage final_rUsage;          /* final time (resource) use */

/* Calculate the duration measured in mach absolute time, nanoseconds */
double duration(uint64_t start, uint64_t end)
{
    uint64_t elapsed = end - start;

    return (double) (elapsed * sTimebaseInfo.numer / sTimebaseInfo.denom)
                            / 1000000000.0;
}

/* Test Data to be sorted and copied */
struct ValStruct {
    float val;
    /* float val2; */
    int idx;
};

struct Val2Struct {
    float val;
    float val2;
    /* int idx; */
};

#define MAX (40000000)
static struct ValStruct data[MAX];
static struct Val2Struct dataIdx[MAX];


static int ValOrdering(const void* const v1, const void* const v2)
{
    if (((struct ValStruct*) v1)->val < ((struct ValStruct*) v2)->val)
        return -1;

    if (((struct ValStruct*) v1)->val> ((struct ValStruct*) v2)->val)
        return 1;

    return 0;
}

static int IndexOrdering(const void* const v1, const void* const v2)
{
    return ((struct ValStruct*) v1)->idx- ((struct ValStruct*) v2)->idx;
}


int main (int argc, const char * argv[]) {
    char sorttype = 'q';   /* sort type - default is quicksort     */
    char idxtype = '\0';   /* reorganise idx by sort ('c' == copy) */

    for (int i=1; i<argc; ++i) {
        /* printf("got %s\n", argv[i]); */
        if (*argv[i] == '-') {
            char arg = *(argv[i]+1);
            /* printf("got %s arg=%c\n", argv[1], arg); */
            if (arg == 'q') {
                sorttype = 'q';
            } else if (arg == 'm') {
                sorttype = 'm';
            } else if (arg == 'h') {
                sorttype = 'h';
            } else if (arg == 'c') {
                idxtype = 'c';
            } else {
                fprintf(stderr, "unrecognised argument '%c'\n", arg);
                exit(1);
            }
        }
    }

    /* Initialise with random data - so their will be some variation */
    for (int i=0; i<MAX; ++i) {
        data[i].val = lrand48();
        data[i].idx = i;
    }

    /* Print enough information to identify the type of sort and data set */
    if (sorttype  == 'q') {
        printf("qsort(data, number-of-elements=%d, element-size=%d)\n",
                                                MAX, sizeof(data[0]));
    } else if (sorttype  == 'm') {
        printf("mergesort(data, number-of-elements=%d, element-size=%d)\n",
                                                MAX, sizeof(data[0]));
    } else if (sorttype  == 'h') {
        printf("heapsort(data, number-of-elements=%d, element-size=%d)\n",
                                                MAX, sizeof(data[0]));
    }

    uint64_t start;         /* start, intermediate and final timing points */
    uint64_t mid_val;
    uint64_t mid_idx;
    uint64_t end;
    (void) mach_timebase_info(&sTimebaseInfo); /* Critical that this is done! */

    gettimeofday(&start_time, NULL); /* only to cross-check total duration */
    getrusage(RUSAGE_SELF, &initial_rUsage);    /* get CPU usage so far */

    start = mach_absolute_time();

    if (sorttype  == 'q') {
        qsort(data, MAX, sizeof(data[0]), ValOrdering);
    } else if (sorttype  == 'm') {
        mergesort(data, MAX, sizeof(data[0]), ValOrdering);
    } else if (sorttype  == 'h') {
        heapsort(data, MAX, sizeof(data[0]), ValOrdering);
    }

    mid_val = mach_absolute_time();

    if (idxtype = 'c') {            /* copy by index rather than sort */
        for (int i=0; i<MAX; ++i) {
            dataIdx[data[i].idx].val = data[i].val;
            dataIdx[data[i].idx].val2 = lrand48(); /* simulate calculation */
        }
    } else {
        if (sorttype  == 'q') {
            qsort(data, MAX, sizeof(data[0]), IndexOrdering);
        } else if (sorttype  == 'm') {
            mergesort(data, MAX, sizeof(data[0]), IndexOrdering);
        } else if (sorttype  == 'h') {
            heapsort(data, MAX, sizeof(data[0]), IndexOrdering);
        }
    }

    mid_idx = mach_absolute_time();

        /* time sort with in-order data, maybe handy to know */
    if (sorttype  == 'q') {
        qsort(data, MAX, sizeof(data[0]), ValOrdering);
    } else if (sorttype  == 'm') {
        mergesort(data, MAX, sizeof(data[0]), ValOrdering);
    } else if (sorttype  == 'h') {
        heapsort(data, MAX, sizeof(data[0]), ValOrdering);
    }


    end = mach_absolute_time();
    getrusage(RUSAGE_SELF, &final_rUsage);
    gettimeofday(&end_time, NULL);      /* only to cross-check total duration */


    printf("Sorting by val - duration = %f\n", duration(start, mid_val));
    if (idxtype = 'c') {            /* copy by index rather than sort */
        printf("Re-order to idx by copying - duration = %f\n",
                                                duration(mid_val, mid_idx));
    } else {
        printf("Sort to idx - duration = %f\n", duration(mid_val, mid_idx));
    }
    printf("Sort in-order data - duration = %f\n", duration(mid_idx, end));
    printf("Total duration = %f\n", duration(start, end));

    /* long double makes arithmetic easier, calculate in micro-seconds (usec) */
    long double utime_usec = 1000000.0
                                * ((double)final_rUsage.ru_utime.tv_sec
                                      - (double)initial_rUsage.ru_utime.tv_sec)
                                  + (double)final_rUsage.ru_utime.tv_usec
                                      - (double)initial_rUsage.ru_utime.tv_usec;

    long double stime_usec = 1000000.0
                                * ((double)final_rUsage.ru_stime.tv_sec
                                    - (double)initial_rUsage.ru_stime.tv_sec)
                                  + (double)final_rUsage.ru_stime.tv_usec
                                     - (double)initial_rUsage.ru_stime.tv_usec;


    /* We can use the value from gettimeof day to cross check duration
     * but it is confusing, so leave it as a debug aid.
     */
#if 0
     long double rtime_usec = 1000000.0
                    * ((double)end_time.tv_sec - (double)start_time.tv_sec)
                        + (double)end_time.tv_usec - (double)start_time.tv_usec;
     printf("Real Time (cross check): %.6Lf\n", rtime_usec/1000000.0);
#endif

    printf("User Time: %.6Lf\n", utime_usec/1000000.0);
    printf("System Time: %.6Lf\n", stime_usec/1000000.0);

    printf("Done Smallsort\n");
    return 0;
}