1
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ If your rand only returns 15 or 16 bits (which is common) your random ranges won't cover the full range. \$\endgroup\$ Dec 29, 2020 at 21:00
  • \$\begingroup\$ @1201ProgramAlarm Thanks, valid point. It's (2^31)-1, ie ~ 2Billion on my machine, and I wasn't really focused on uniform distribution etc. But fair point. \$\endgroup\$ Dec 29, 2020 at 23:02
  • 1
    \$\begingroup\$ There shouldn't be anything random in here anyway - sorting should be completely deterministic, and tests need to be reproducible (nothing worse than tests that sometimes pass and sometimes fail - how do you debug that?) At least print the seed used, and allow that to be passed in to reproduce the test. \$\endgroup\$ Dec 30, 2020 at 12:45
  • \$\begingroup\$ Yes, that's true, and I did fix the seed while debugging. But I opened it to generate any possible unforseen edge cases. \$\endgroup\$ Dec 30, 2020 at 12:46
  • \$\begingroup\$ How many platforms' implementations of memcpy() did you profile to determine that it always performs weakly with small count? You're probably reimplementing something that the better compilers are already doing for you (remember that memcpy() may be inlined by the compiler, so it likely depends on the optimisation level you ask for, too). \$\endgroup\$ Dec 30, 2020 at 12:48

1 Answer 1

2
\$\begingroup\$

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.
\$\endgroup\$
12
  • \$\begingroup\$ Sure thanks. Aware of that technique and use it often. \$\endgroup\$ Dec 29, 2020 at 22:58
  • \$\begingroup\$ Yes I did time it. Without the sizeof() switch just using memcpy for small types it is twice as slow. As soon as I made swap() type aware the performance improved by 2x. \$\endgroup\$ Dec 29, 2020 at 23:08
  • \$\begingroup\$ I like the idea of time(NULL) as a fallback. I guess if I really cared enough about quality randomness, I probably shouldn't be using rand() anyway? \$\endgroup\$ Dec 29, 2020 at 23:11
  • \$\begingroup\$ I am compiling with clang-10 on ubuntu 20.04 btw. clang -O3 -Wall -Wextra -Werror \$\endgroup\$ Dec 29, 2020 at 23:12
  • 2
    \$\begingroup\$ marginally faster => branch prediction. The trouble is for times when the predication fails. switch will be faster in most situations. \$\endgroup\$ Dec 29, 2020 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.