7
\$\begingroup\$

I'm trying out different sorting algorithms for learning purposes, here I'm doing a "type-agnostic" bubbleaort.

I modeled the function signature after the standard library's qsort. I know the bubblesort algorithm in general is not that fast, but I'm looking for a review in particular about the memory management.

In my implementation I'm accepting a void pointer to an array, the size of the array, the size of the single elements and the pointer to the comparison function. Then I convert the void pointers to char pointers, and I do manually the pointer arithmetics (I avoided nonstandard arithmetics on void *).

The part I'm not very happy about is the need for a buffer (dynamically allocated), and the use of memcpy to swap the memory of the two elements. I'd love to know if that part can be improved even slightly.

I'm using a pointer to the beginning and the end of the array, instead of using indexes with [] bracket notation.

Also, what about the if (buffer == NULL) check and "halting" with exit()? Is there a more elegant way to fail here?

I also could use one variable instead of two (current and left), but doing one more pointer arithmetic in the inner loop.

Here's my current bubblesort implementation:

/**
 * Bubblesort algorithm. Compatible with any data type.
 * @param base A void pointer to the array's first element.
 * @param num The number of elements in the array.
 * @param size The size of the data type.
 * @param compar A pointer to the comparison function.
 */
void bubblesort(void* base, size_t num, size_t size,
    int (*compar)(const void*, const void*)
) {
    const char *arr = (const char *) base;
    char *buffer, *left, *current, *right;

    if (arr != NULL && size > 0 && num > 1) {
        buffer = (char *) malloc(size);

        if (buffer == NULL) {
            fprintf(stderr, "Out of memory.");

            exit(EXIT_FAILURE);
        }

        right = (char *) arr + num * size;
        while (right > arr) {
            left = (char *) arr;
            current = left + size;

            while (current < right) {
                // Compare the two elements and move the bigger to the right
                if (compar(left, current) > 0) {
                    memcpy(buffer, left, size); // Temporary variable
                    memcpy(left, current, size); // Swap pt.1
                    memcpy(current, buffer, size); // Swap pt.2
                }

                left += size;
                current += size;
            }

            right -= size;
        }

        free(buffer);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Personally, I would always prefer for the caller to perform allocations, including swap space for items. Among other benefits, it allows for more flexible error handling. Furthermore, why not sort a list of pointers instead? \$\endgroup\$ – Rhymoid Nov 28 '15 at 10:50
  • 1
    \$\begingroup\$ As I said, I modeled the function signature after the standard library's qsort that accepts an "array" as a pointer to the first element of the array. That function won't work with a list of pointers. If I want to pass a list of pointers instead, that would be a different function signature, with a different implementation. Here my own "requirement" is to "mimic" a possible standard library function. \$\endgroup\$ – Zorgatone Nov 28 '15 at 10:55
  • \$\begingroup\$ Also about the allocations part, I believe the caller should only need to know if the sorting algorithm is in-place/not-in-place and if it's stable. If the caller should care about this buffer allocation it would need to pass one morepointer to function. Also the array being passed as first parameter is already allocated by the caller function. I'm not doing allocation where you see memcpy, just swapping the array elements (which the caller function should know being swapped). Am I right? What do you think @Rhymoid? \$\endgroup\$ – Zorgatone Nov 28 '15 at 11:01
  • 1
    \$\begingroup\$ By "swap space" I was referring to your buffer variable. In any case, it just occurred to me that you could isolate the three memcpy, together with the buffer allocation and release, to its own function memswap. This increases readability of bubblesort itself, and while you get O(n^2) calls to malloc and free in the naive implementation, memswap itself could be optimised to use the stack as a buffer (for small size), or use no buffer at all (swap word by word). You might even want to take a peek at C++'s swap_ranges. \$\endgroup\$ – Rhymoid Nov 28 '15 at 11:35
  • 1
    \$\begingroup\$ Yes, the stack. For stack allocation, I'd use locally declared VLAs, although I'm really not a fan of that (in part because C doesn't actually distinguish between stack and heap, as far as I know). For buffer-less swaps, I would swap the ranges char by char (the temporary char would then usually be allocated to a CPU register rather than stack memory or heap memory, but again: C doesn't really know the difference). \$\endgroup\$ – Rhymoid Nov 28 '15 at 11:47
6
\$\begingroup\$

Error handling

Some would argue that it's unacceptable to exit() in case of an "out of memory" error occurring in a library function. I would invite them to tell me how to actually recover in those situations, because I doubt many "well-designed" applications do so.

That said, many libraries indeed have the courtesy of telling the caller that they can't complete their task, rather than killing the process. For a language like C (which lacks support for sum types and exceptions), I'm currently undecided between a few approaches, but I'd always make sure that the caller can distinguish between success and failure by a simple inspection of the return value.

The easiest approach would be to change the return value of bubblesort to a library-specific enum of error codes, which includes exactly one 'success' value (in C libraries, the common value would be 0) and at least one 'generic failure' value. If you want your users to be able to distinguish between failure reasons, just add more reason to the enum.

Once you have done this, you can also explicitly signal for other error conditions (arr == 0, size == 0), if you consider them errors.

Note: for some pet projects, I used to just return a bool, where true would mean success. Since I realised that this runs counter to the UNIX tradition of "zero means success", I no longer use that in public APIs.

Swapping

By introducing a memswap function

void memswap(void *restrict left, void *restrict right, size_t length);

we can move a lot of logic out of bubblesort itself. This also means we would move the malloc and free to it, which seems like a bad idea for a function in the inner loop.

But don't worry: you can implement memswap in any way you like. For instance, memswap could swap the data between aaaa and bbbb byte-by-byte:

void memswap(
    void *restrict left,
    void *restrict right,
    size_t length
) {
    char *left2 = (char *)left;
    char *right2 = (char *)right;

    for (size_t cursor = 0; cursor < length; cursor++) {
        char tmp = left2[cursor];
        right2[cursor] = left2[cursor];
        left2[cursor] = tmp;
    }
}

Now that you have no more malloc, you won't have to deal with the possibility of it returning a null pointer.

Of course, a robust memswap would not ever cause any UB (which could imply exit()), so you should add some checks for null pointers here. Whether that's an error condition, or that it causes memswap to do nothing is up to you as a library designer. The same goes for the check that left and right don't overlap.

Other functional remarks

  • You forgot a trailing newline in your error message.
  • Checking for the cases num == 0 or num == 1 is an attempt at optimisation (right?). I wouldn't do this, unless a benchmark shows that clients of the library are getting significant poor performance because of it (but then it might be a better idea to figure out why these calls are made to begin with).
  • In the line

    right = (char *) arr + num * size;
    

    you should definitely protect yourself against a potential integer overflow in num * size.

Stylistic remarks

  • Don't cast malloc's return value.
  • I assume that this isn't all code, but I want to clarify that the structure of files matters. My specific remark here would be that I always make a forward declaration to the functions I define.
  • Positive conditions, even when negated, are easier to understand than negative ones. For instance, the condition in

    if (arr != NULL && size > 0 && num > 1) {
    

    takes me more time to understand than

    if (!(arr == NULL || size == 0 || num <= 1)) {
    
  • In terms of code real estate, vertical size is cheaper than horizontal size. With that, I mean that I think a failure check like

    if (!(arr == NULL || size == 0 || num <= 1)) {
    

    is more readable (and more VCS-friendly ;)) when it's split into multiple blocks, or that the clauses in the condition at least get their own line. Yes, your code grows in length, but I'd prefer boring-looking code that's obvious over "elegant" short code that takes effort to get through (and I say that as a Haskell user).

  • As of C99, 0 is the (canonical) null pointer constant (meaning that when you convert a constant integer expression with value 0 to a pointer, you get a null pointer; the actual "address" of that null pointer is implementation-defined, though). NULL is still valid, but I wouldn't use it.
  • const char *arr is confusing, as you know for a fact that you will modify arr. Just use char *arr, avoiding pointer casts later on.
  • The comments around the swap are not particularily helpful. I prefer many functions and named constants over comments and magic.
  • You could turn either loop into a for loop, but I recommend to keep this as a while here. The for-notation only helps readability when it concerns a single iterator, and has no performance benefit over while.
  • Thank you for using EXIT_SUCCESS and EXIT_FAILURE :)

Putting it together (without memswap itself)

enum your_library_status_code {
    your_library_success = 0,
    your_library_failure = 1,
};

/**
 * Bubblesort algorithm. Compatible with any data type.
 * @param base A void pointer to the array's first element.
 * @param num The number of elements in the array.
 * @param size The size of the data type.
 * @param compar A pointer to the comparison function.
 */
enum your_library_status_code bubblesort(
    void* base,
    size_t num,
    size_t size,
    int (*compar)(const void*, const void*)
) {
    if (base == 0) {
        // TODO: introduce error code for "invalid argument"
        return your_library_failure;
    }

    if (size == 0) {
        // TODO: introduce error code for "invalid argument"
        return your_library_failure;
    }

    size_t total_size = num * size;

    if (total_size / size != num) {
        // TODO: introduce error code for "invalid argument (due to overflow)"
        return your_library_failure;
    }

    char *arr = base;
    char *left, *current, *right;

    right = (char *) arr + total_size;

    while (right > arr) {
        left = (char *) arr;
        current = left + size;

        while (current < right) {
            if (compar(left, current) > 0) {
                memswap(left, current, size);
            }

            left += size;
            current += size;
        }

        right -= size;
    }

    return your_library_success;
}

(Caveat: not tested.)

\$\endgroup\$
  • \$\begingroup\$ Please, explain me the meaning of UB :P \$\endgroup\$ – Zorgatone Nov 28 '15 at 19:57
  • \$\begingroup\$ Hi! Welcome to Code Review. Excellent job on your first answer! I hope you come back and contribute more! \$\endgroup\$ – TheCoffeeCup Nov 28 '15 at 19:57
  • \$\begingroup\$ Wow, this was really your first answer? cool. Anyway about the num == 0 or num == 1 check, it wasn't meant to do any optimisation. I just added that as the first thing when I started the function implementation. I just thought I could do that check before anything else, so that I could be sure to avoid some errors while designing the inner code. I see it's probably un-needed here, as the while loop would terminate before doing anything \$\endgroup\$ – Zorgatone Nov 28 '15 at 20:01
  • \$\begingroup\$ About the Don't cast malloc's return value. part I've always been told/taught that it would be good practice to avoid mistakes, especially if you change the type of a pointer later the complier would generate a warning. \$\endgroup\$ – Zorgatone Nov 28 '15 at 20:03
  • 1
    \$\begingroup\$ As for generated code of the if: ... || ... also has 'left-to-right' (a.k.a. short-circuiting) behaviour; it will stop at the first true. The compiler may optimise these expressions as appropriate for the CPU architecture. As for NULL/0 clarity: it's just a matter of personal preference. You have a point about NULL obviously being a pointer. Whichever decision you make, just stick with it :) As for the total_size / size: that's a typo on my end, I was going for total_size / size == num; if that's false, then size * num exceeds SIZE_MAX and we need to abort. \$\endgroup\$ – Rhymoid Nov 28 '15 at 21:08
3
\$\begingroup\$

I see a number of things that may help you improve your code.

Eliminate unneeded variables

Since most of the places that are using arr also already have a cast, you may as well add a single cast and eliminate arr entirely, using base directly instead.

Highlight the early bailout

We can highlight the early bailout by putting it at the top of the routine:

if (base == NULL || size < 1 || num < 2) {
    return;
}

The effect is the same as your original, but now it's more clear to a reader of the program that any of the conditions (such as base == NULL will cause the routine to simply return.

Prefer for to while where sensible

Within the current code, first right is set to a value, then checked as an exit condition in a while loop, then decremented. That sounds more like a for loop construct, so it may be helpful to write it that way to make the logic of the program a little more obvious.

Eliminate the need for a buffer

If the buffer is omitted, there is no way for its allocation to fail. At the possible expense of some speed, the swap can be done char at a time:

for (unsigned i=0; i < size; ++i, ++left, ++current) {
   char ch = *left;
   *left = *current;
   *current = ch;
}

Putting it all together

Using all of these suggestions, here's how that might look:

void bubblesort(void* base, size_t num, size_t size,
    int (*compar)(const void*, const void*)
) {
    char *left, *current, *right;

    if (base == NULL || size < 1 || num < 2) {
        return;
    }
    for (right = (char *) base + num * size; right > (char *)base; right-=size) {
        left = (char *) base;
        current = left + size;

        while (current < right) {
            // Compare the two elements and move the bigger to the right
            if (compar(left, current) > 0) {
                for (unsigned i=0; i < size; ++i, ++left, ++current) {
                    char ch = *left;
                    *left = *current;
                    *current = ch;
                }
            } else {
                left += size;
                current += size;
            }
        }
    }
}

Test program

I wrote a little test program to exercise the function

#include <stdio.h>
#include <stdlib.h>
struct mongo 
{
    int n;
    const char *label;
};

int comp(const void *a, const void *b) 
{
    return ((struct mongo *)b)->n <= ((struct mongo *)a)->n;
}

void print(const char *msg, const struct mongo *m, int count)
{
    puts(msg);
    for ( ; count; --count, ++m) 
        printf("%d %s\n", m->n, m->label);
}

#define DATA_LEN 5
int main() {
    struct mongo mydata[DATA_LEN] = {
        { 2, "two" },
        { 5, "five" },
        { 3, "three" },
        { 1, "one" },
        { 4, "four" }
    };
    print("Before sorting:", mydata, DATA_LEN);
    bubblesort(mydata, DATA_LEN, sizeof(struct mongo), comp);
    print("After sorting:", mydata, DATA_LEN);
}

Test program output

Before sorting:
2 two
5 five
3 three
1 one
4 four
After sorting:
1 one
2 two
3 three
4 four
5 five
\$\endgroup\$
  • \$\begingroup\$ Very helpful answer. Yeah, I know about the while loops, I started with those, but changed them because the for notation was cluttered with too many informations, that I thought a while would be less "cryptic" to read. Even though the incrementing/decrementing would look more obvious. I'm very pleased about the char-by-char copy, and the fact that I don't need to allocate more memory. Good one \$\endgroup\$ – Zorgatone Nov 28 '15 at 13:16
  • \$\begingroup\$ I would also make a memswap() function that would do the "char-by-char" swap of two elements \$\endgroup\$ – Zorgatone Nov 28 '15 at 13:20
  • \$\begingroup\$ memswap() could also just be an inline, or maybe even a macro \$\endgroup\$ – Zorgatone Nov 28 '15 at 13:26
  • 1
    \$\begingroup\$ I'd advise against making it a macro. There are too many things that could easily go wrong. For instance, see Why isn't there a standard memswap function?. \$\endgroup\$ – Edward Nov 28 '15 at 13:38
  • \$\begingroup\$ I agree that macros would be a bad idea (static inline functions are already much better). A memswap function would still be very useful here, regardless of the accepted answer to that SO question (with which I very much disagree). \$\endgroup\$ – Rhymoid Nov 28 '15 at 16:07
2
\$\begingroup\$

Swapping efficiently without malloc

If you want to know how qsort() does its swapping, check out this open source implementation of qsort(). Essentially, their version precomputes whether the size is divisible by a long or not, then calls a static inline function which in a loop either swaps by longs or by bytes.

Pointer logic confusing

I found it hard to read through your algorithm because of all the pointer arithmetic involved. I feel like some of the pointers could be replaced with simple indices that count between 0 and num, because that is their function. That way, your routine would look more like a "normal" bubblesort.

Sample rewrite

Here is a sample rewrite based on the above two ideas:

static inline void swap(void *p1, void *p2, int swapByLong, size_t size)
{
    size_t i;
    if (swapByLong) {
        long *pl1 = (long *) p1;
        long *pl2 = (long *) p2;
        for (i = 0; i < size; i += sizeof(long)) {
            long tmp = *pl1;
            *pl1++ = *pl2;
            *pl2++ = tmp;
        }
    } else {
        char *pc1 = (char *) p1;
        char *pc2 = (char *) p2;
        for (i = 0; i < size; i++) {
            char tmp = *pc1;
            *pc1++ = *pc2;
            *pc2++ = tmp;
        }
    }
}

void bubblesort(void* base, size_t num, size_t size,
        int (*compar)(const void*, const void*))
{
    size_t i, j;
    int swapByLong;

    if (base == NULL || size <= 0 || num <= 1)
        return;
    swapByLong = (size % sizeof(long) == 0);

    for (i = num-1; i > 0; i--) {
        char *p0 = (char *) base;
        char *p1 = p0 + size;
        for (j = 0; j < i; j++) {
            if (compar(p0, p1) > 0)
                swap(p0, p1, swapByLong, size);
            p0 += size;
            p1 += size;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Very nice, I agree about the pointer arithmetics stuff. Also the divisible-by-long approach seems a great improvement. But couln't you move swapByLong = (size % sizeof(long) == 0); inside the swap() function, and pass one less parameter? You just need to know the size parameter to calculate that at the beginning of the swap routine. \$\endgroup\$ – Zorgatone Nov 28 '15 at 19:08
  • \$\begingroup\$ I see, you calculate that once, instead of on every call of swap inside the bubblesort loop \$\endgroup\$ – Zorgatone Nov 28 '15 at 19:13
  • \$\begingroup\$ Your swap function is very handed and reusable. I like it, I need to save this somewhere for future needs :) \$\endgroup\$ – Zorgatone Nov 28 '15 at 19:18
  • \$\begingroup\$ @Zorgatone Remember that swap() is an inlined routine, so really any "argument passing" is free because there isn't actually any argument passing going on. Therefore, calculating swapByLong once is better. \$\endgroup\$ – JS1 Nov 28 '15 at 19:22
  • \$\begingroup\$ Yeah, I noticed it's inline. That's one of the multiple reasons why I like that \$\endgroup\$ – Zorgatone Nov 28 '15 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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