Generic QuickSort with Performance Optimised Swap for small types

Question

Overview

A "from scratch" generic quicksort implemented in C, which allows predicate (returning bool, like C++ rather than int like C), and any type via void*.

Using memcpy for the swap() implementation was the general solution. But this was about twice as slow as declared types for small types (int, float, double etc). So I added a simple "type-size-switch", which worked to restore performance to pre-generic levels.

More types/sizes can be easily added. Including char* to sort strings by swapping their pointers - demo included, it uses the long case in the type switch on my machine because long and ptr are both 8 bytes. I know the memcpy solution won't handle very large types - would have to use malloc or "byte-by-byte swap" it with our own loop.

Uses "C++ iterator" style params start and end (which is one past the end) rather than C-style start and count.

Questions

1. Type-size switch. Is this a reasonable techique hint to the compiler to use registers for optimisation rather than slow generic memcpy for small types.
2. Does the above violate the standard? What about using long to swap a double if they happen to be the same size, which is very common?
3. How about the use of /dev/urandom use for srand() (I know it's not cross-platform).
4. Any other comments?

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdio.h>


typedef bool (*cmp)(const void*, const void*);

bool less_ints(const void* a, const void* b) {
  return *(const int*)a < *(const int*)b;
}

bool greater_ints(const void* a, const void* b) {
  return *(const int*)a > *(const int*)b;
}

bool less_strs(const void* a, const void* b) {
  return strcmp(*((const char**)a), *((const char**)b)) < 0;
}

void swap(void* x, void* y, size_t size) {
  switch (size) {
  case sizeof(int): {
    int t      = *((int*)x);
    *((int*)x) = *((int*)y);
    *((int*)y) = t;
    break;
  }
  case sizeof(long): { // used by char**
    long t      = *((long*)x);
    *((long*)x) = *((long*)y);
    *((long*)y) = t;
    break;
  }
  default: {
    char t[size];
    memcpy(t, x, size);
    memcpy(x, y, size);
    memcpy(y, t, size);
  }
  }
}

void* partition(void* start, void* end, size_t size, cmp predicate) {
  if (start == NULL || end == NULL || start == end) return start;
  char* storage = (char*)start;
  char* last    = (char*)end - size; // used as pivot
  for (char* current = start; current != last; current += size) {
    if (predicate(current, last)) {
      swap(current, storage, size);
      storage += size;
    }
  }
  swap(storage, last, size);
  return storage; // returns position of pivot
}

void quicksort(void* start, void* end, size_t size, cmp predicate) {
  if (start == end) return;
  void* middle = partition(start, end, size, predicate);
  quicksort(start, middle, size, predicate);
  quicksort((char*)middle + size, end, size, predicate);
}

bool sortcheck(const int* start, int size) {
  for (int i = 0; i < size - 1; ++i) {
    if (start[i] > start[i + 1]) return false;
  }
  return true;
}

void print(const int* start, int size) {
  for (int i = 0; i < size; ++i) printf("%3d", start[i]);
  printf("\n");
}

bool rand_seed() {
  int   seed = 0;
  FILE* fp   = fopen("/dev/urandom", "re");
  if (!fp) {
    fprintf(stderr, "Error: couldn't open source of randomness");
    return false;
  }
  if (fread(&seed, sizeof(int), 1, fp) < 1) {
    fprintf(stderr, "Error: couldn't read random seed");
    fclose(fp);
    return false;
  }
  fclose(fp);
  srand(seed); // nice seed for rand()
  return true;
}

int rand_range(int start, int end) {
  return start + rand() / (RAND_MAX / (end - start + 1) + 1);
}

int main() {
#define size 10000000
  int* data = malloc(size * sizeof(int));
  if (!data) {
    fprintf(stderr, "couldn't allocate memory");
    exit(EXIT_FAILURE);
  }
  if (!rand_seed()) {
    fprintf(stderr, "couldn't seed random number generator");
    free(data);
    exit(EXIT_FAILURE);
  }
  for (int i = 0; i < size; ++i) data[i] = rand_range(1, size / 2);

  // print(data, size);

  quicksort(data, data + size, sizeof(int), &less_ints);
  // partition(data, data + size, sizeof(int), &less_ints);

  // if (!sortcheck(data, size)) {
  //   fprintf(stderr, "ERROR: data is not sorted!\n");
  //   exit(EXIT_FAILURE);
  // }
  // print(data, size);
  free(data);

  // string demo
#define str_count 12
  const char* strings[str_count] = {
      "material", "rare",    "fade",      "aloof",  "way",  "torpid",
      "men",      "purring", "abhorrent", "unpack", "zinc", "unsightly",
  };
  quicksort(strings, strings + str_count, sizeof(char*), &less_strs);
  for (int i = 0; i < str_count; ++i) printf("%s\n", strings[i]);

  return EXIT_SUCCESS;
}

Answer 1

Type-size switch. Is this a reasonable techique hint to the compiler to use registers for optimisation rather than slow generic memcpy for small types.

Why do you think that memcpy() has not already implemented this optimization itself? Do you have timing data to suggest this optimization works and improves performance?

Does the above violate the standard? What about using long to swap a double if they happen to be the same size, which is very common?

On a lot of systems long and int are the same size. In that case your switch() will fail to compile (I think).

How about the use of /dev/urandom use for srand() (I know it's not cross-platform).

If it does not exist then why not fall back on the classic time(NULL) rather than generating an error.

Any other comments?

Let the compiler do the work of calculating array sizes:

const char* strings[] = {
                // ^^   Notice empty braces forces the compiler to 
                //      calculate the correct size based on the initialization values.
    "material", "rare",    "fade",      "aloof",  "way",  "torpid",
    "men",      "purring", "abhorrent", "unpack", "zinc", "unsightly",
};

const int str_count = sizeof(strings) / sizeof(strings[0]);
                   // This trick works even if the array has size 0
                   // because the sizeof is done at compile time
                   // and thus strings[0] is never actually accessed
                   // just type information is retrieved.