alloctest.cpp

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <sys/time.h>
#include <unistd.h>

#ifndef SIZE
#define SIZE 10000
#endif

void quicksort_swap(float *arr, size_t i, size_t j) {
    arr[i] = (float)((uint32_t)arr[i] ^ (uint32_t)arr[j]);
    arr[j] = (float)((uint32_t)arr[j] ^ (uint32_t)arr[i]);
    arr[i] = (float)((uint32_t)arr[i] ^ (uint32_t)arr[j]);
}

size_t quicksort_partition(float *arr, size_t lo, size_t hi) {
    float pivot = arr[lo];
    size_t i = lo - 1;
    size_t j = hi + 1;
    for (;;) {
        do {
            i++;
        } while (arr[i] < pivot);

        do {
            j--;
        } while (arr[j] > pivot);

        if (i >= j) {
            return j;
        }
        quicksort_swap(arr, i, j);
    }
}

void quicksort_impl(float *arr, size_t lo, size_t hi) {
    if (lo < hi) {
        size_t p = quicksort_partition(arr, lo, hi);
        quicksort_impl(arr, lo, p);
        quicksort_impl(arr, p+1, hi);
    }
}

void quicksort(float *arr, size_t size) {
    quicksort_impl(arr, 0, size-1);
}

void print_usage(char *name) {
    printf("USAGE: %s [-i iters] [-q(uiet)] <-m(alloc) | -n(ew) | -s(tatic)>\n", name);
}

int main(int argc, char **argv) {
    if (argc <= 1) {
        print_usage(argv[0]);
        return 0;
    }

    int quiet = 0;
    float *arr = NULL;

    float statarr[SIZE];
    struct timeval start, end, now;

    int iters = 10;
    int opt;
    char *endptr;
    char mode;
    while ((opt = getopt(argc, argv, "qi:nms")) != -1) {
        switch (opt) {
            case 'i':
                iters = strtol(optarg, &endptr, 10);
                if (*endptr != '\0') {
                    printf("invalid iter number\n");
                    return 1;
                }
                break;
            case 'q':
                quiet = 1;
                break;
            case 'n':
                mode = 'n';
                arr = new float[SIZE];
                break;
            case 'm':
                mode = 'm';
                arr = (float*)malloc(SIZE * sizeof(float));
                break;
            case 's':
                mode = 's';
                arr = statarr;
                break;
        }
    }

    if (arr == NULL) {
        print_usage(argv[0]);
        return 0;
    }

    uint64_t median = 0;
    for (int iter = 0; iter < iters; iter++) {
        gettimeofday(&now, NULL);
        srand(now.tv_usec);
        for (size_t i = 0; i < SIZE; i++) {
            arr[i] = (float)rand();
        }
        gettimeofday(&start, NULL);
        quicksort(arr, SIZE);
        gettimeofday(&end, NULL);
        uint64_t diff = ((end.tv_sec - start.tv_sec) * 1000000);
        diff -= start.tv_usec;
        diff += end.tv_usec;
        if (!quiet) {
            printf("%ld\n", diff);
        }
        median += diff;
    }
    printf("Median: %ld\n", median / iters);
    switch (mode) {
        case 'n':
            delete[] arr;
            break;
        case 'm':
            free(arr);
            break;
        case 's':
            break;
    }
    return 0;
}