A Middling and Situational Sort

Part of my personal projects using C is that there is a fair few bits of code that are broadly useful to me, and potentially others, across many current and future repositories.

The initial, naive, quick and dirty approach I often start out with is to just copy a piece of code I am using between projects, fine on that small scale and if you know changes are not going to have to be passed back and forth, but as soon as you want to share improvements and changes between projects, immediate hassle.

Submodule(s), especially with CMakeLists set up for them, is how I have massively lubricated the use of shared code. For the most part I have just been putting anything broad and polished enough that I feel happy with it being all over the place, at least right now. I’m sure in a decade I’ll either despise it all as amateurish garbage that I regret sharing or I will have been obsessively reworked the whole thing a dozen times by that point.

Isolated in their own repo their focus can remain the supreme functionality, I can’t end up repeating myself, and I can’t unintentionally tie it to something less portable. In addition, given the form that this now fits it easily shared in a useful form, for that OSS cred. I am more than happy if people want you use this for their own projects, if you want to; let me know, I want to see what cool stuff people are working on. Keep in mind it is somewhat GCC focused, I may rectify this in future but don’t rely on it.

This is a collection of things like a string hashing function that can run at compile time if needed, some functions that give you the number of digits a number has given a couple of different common bases, and a type agnostic swap macro. I’m pretty happy with that last one:

#define swap_helper(_1, _2, _3, NAME, ...) NAME

#define swap_known(a,b) \
    do { \
        __typeof__ (a) _a = (a); \
        __typeof__ (b) _b = (b); \
        if (_a == _b) break; \
        unsigned char swap_temp[sizeof(*_a) == sizeof(*_b) ? (signed)sizeof(*_a) : -1]; \
        memcpy(swap_temp,_b,sizeof(*_a)); \
        memcpy(_b,_a,sizeof(*_a)); \
        memcpy(_a,swap_temp,sizeof(*_a)); \
    } while(0)

#define swap_size(a,b,size) \
    do { \
        __typeof__ (a) _a = (a); \
        __typeof__ (b) _b = (b); \
        __typeof__ (size) _size = (size); \
        if (_a == _b) break; \
        unsigned char swap_temp[_size]; \
        memcpy(swap_temp,_b,_size); \
        memcpy(_b,_a,_size); \
        memcpy(_a,swap_temp,_size); \
    } while(0)

#define swap(...) swap_helper(__VA_ARGS__, swap_size, swap_known)(__VA_ARGS__)

It sits somewhere in my mind like the prettiest, most handsome, goblin. It feels like a mess but is relatively clean, very capable, and able to handle arbitrary sizes of data. Still, like with a lot of what I put up; if you have suggestions for improvements do let me know.

The focus of this act of coding will remain primarily for the benefit of my own projects, so what I currently need gets the grease.

It is worth acknowledging that in this realm lies madness, all should be weary as to not let it overtake you. There is 2 ends to this spectrum; ‘Not invented here’ syndrome and ‘proudly found elsewhere’ are both common pitfalls, as always, balance is key. I have often fell into the latter, I have built a software render for 3D multiple times.

Anyway that is all an aside to some experimentation that I have done within the submodule. Sorting algorithms are hardly untrod ground but I still thought it was worth poking into the possibilities for novelty. Nothing too original you understand, just bits and pieces in the details, like a bitwise focus for a In-place MSD binary-radix sort, or looking into the use of data ‘rotations’ to reduce memory usage.

As part of my testing and evaluation of these different algorithms it made sense to be able to measure the real world performance of the algorithms so that I could, at the very least, can discern if there was any actual improvements.

The following is a table showing in microseconds how long it takes for the a list of a given size/length to be sorted 100 times by each algorithm, for lengths 1 to 10000 entries long. While all 10000 lengths have been tested the table on this page are just those at regular intervals for readability in this format.

The full set of results, collected continuously over several days, can be found here: https://gist.github.com/MegaDarken/0f8186aa7c84c9fc684d9f3874daec9a

Even in this form there is some thing I think it is fair to say that some outside factors had an influence in parts of this as sections will jump down and jump up.

I was pleasantly surprised with how well binaryRadixSort_lsd did on the high end, it has similar memory usage to the iterative merge sort O(n) space, but appears to outperform it. Related; the in-place variants of those same algorithms are both slower, as you may expect, but they have the opposite relationship, the in-place merge sort is faster than the in-place binaryRadixSort_lsd. I’m fairly certain this is because the rotations used to make the algorithms not require additional memory work by shifting blocks of data around, the further the distance between values moved the more data has to be moved, and while the mergesort movements tend to keep relatively localized, while binaryRadixSort_lsd

From this data we can make some graphs:

All sorts to 10000:

The same without insertion sort:

The same without insertion sort or binaryRadixSort_lsd_inPlace:

I’m sure others can graph this better than I have.

Was this massively overkill? Seems like it.

The algorithms that are functional enough should be able to be found in the Shared-C repo, linked above.