10
\$\begingroup\$

Over on Stack Overflow, I read an answer asserting that Insertion Sort was inferior to Selection Sort for array data (as opposed to linked list data) on account of the larger amount of data movement that insertion sort performs on average. This claim was new to me, running counter to many assertions I have read and accepted over the years of the general superiority of Insertion sort among its comparison-sort peers. Moreover, my own algorithmic analysis supports Insertion sort as being slightly better on average for random data, assuming efficient implementations of both algorithms and an environment where memory writes are not appreciably more expensive than reads.

But inasmuch as the two algorithms have the same asymptotic cost, all the argumentation is so much smoke without testing. Therefore, I wrote a selection sort, an insertion sort, and a test harness to put some actual data in play. I was surprised by the results: my Insertion sort was way faster than my Selection sort on random input (about one fourth the running time), and Insertion was a clear winner even for its worst case of reverse-sorted input. I didn't expect Insertion to perform so much better in the average case, and I didn't expect it to win at all in the reverse-sorted input case.

And that brings me here. I present my two sort functions and the test harness for your review and commentary. I am particularly interested in insights on how the selection sort's performance might be improved, so as to ensure that the test is a fair one. I am also interested in commentary on any flaws in the test harness that might bias the results.

selection.c

void selection(int data[], unsigned int count) {
    for (unsigned int i = 0; i < count - 1; i++) {
        int min_value = data[i];
        unsigned int min_index = i;
        
        for (unsigned int j = i + 1; j < count; j++) {
            if (data[j] < min_value) {
                min_index = j;
                min_value = data[j];
            }
        }

        data[min_index] = data[i];
        data[i] = min_value;
    }
}

selection.h

void selection(int data[], unsigned int count);

insertion.c

void insertion(int data[], unsigned int count) {
    for (unsigned int i = 1; i < count; i++) {
        int test_value = data[i];
        unsigned int j;

        for (j = i; j > 0; j--) {
            if (data[j - 1] > test_value) {
                data[j] = data[j - 1];
            } else {
                break;
            }
        }

        if (j != i) {
            data[j] = test_value;
        }
    }
}

insertion.h

void insertion(int data[], unsigned int count);

main.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "insertion.h"
#include "selection.h"

#define NUM_ITEMS 16384
#define RANDOM_SEED 17231
#define ITERATIONS 32
#define CLOCKS_PER_MS (CLOCKS_PER_SEC / 1000)

int original_items[NUM_ITEMS];
int selection_items[NUM_ITEMS];
int insertion_items[NUM_ITEMS];

int main(void) {
    clock_t start_time;
    clock_t total_time;
    int num_distinct;

    srand(RANDOM_SEED);
    for (int i = 0; i < NUM_ITEMS; i++) {
        original_items[i] = rand() % NUM_ITEMS;
    }

    // test selection
    total_time = 0;
    for (int i = 0; i < ITERATIONS; i++) {
        memcpy(selection_items, original_items, sizeof(original_items));
        start_time = clock();
        selection(selection_items, NUM_ITEMS);
        total_time += clock() - start_time;
    }

    // Validation / sanity check
    num_distinct = 1;
    for (int i = 1; i < NUM_ITEMS; i++) {
        if (selection_items[i] < selection_items[i - 1]) {
            printf("Selection result validation failed.\n");
        }
        if (selection_items[i] != selection_items[i - 1]) {
            num_distinct++;
        }
    }
    printf("%d distinct values sorted\n", num_distinct);

    printf("Selection sort on %d items: %ld ms\n", NUM_ITEMS, (long) (total_time / ITERATIONS / CLOCKS_PER_MS));


    // test insertion
    total_time = 0;
    for (int i = 0; i < ITERATIONS; i++) {
        memcpy(insertion_items, original_items, sizeof(original_items));
        start_time = clock();
        insertion(insertion_items, NUM_ITEMS);
        total_time += clock() - start_time;
    }

    // Validation
    for (int i = 0; i < NUM_ITEMS; i++) {
        if (insertion_items[i] != selection_items[i]) {
            printf("Insertion result differs from selection result.\n");
        }
    }

    printf("Insertion sort on %d items: %ld ms\n", NUM_ITEMS, (long) (total_time / ITERATIONS / CLOCKS_PER_MS));
}

Makefile

PROG = sort_test
OBJS = main.o selection.o insertion.o

CFLAGS = -O3 -Wall -Wextra -pedantic -std=c11

$(PROG) : $(OBJS)
    $(CC) -o $@ $(CFLAGS) $(LDFLAGS) $^

main.o selection.o: selection.h
main.o insertion.o: insertion.h

clean:
    rm $(PROG) $(OBJS)

.PHONY: clean

I built and tested the code in a WSL container running SUSE Leap 42.3, featuring GCC 4.8.5.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I notice your test tests the selection sort first then the insertion sort. Could it be that all the page faults necessary to make either of them function were resolved on the selection sort? I would shut my computer off cold, boot it from scratch, maybe do some other stuff first, run the selection-then-insetion test, then modify the program to do it the other way around and repeat the tests. \$\endgroup\$
    – Jennifer
    Aug 24 '20 at 10:49
  • \$\begingroup\$ Fair question, @Jennifer. I tried testing them in the opposite order, and it made no appreciable difference in their computed timing. \$\endgroup\$ Aug 24 '20 at 16:39
8
\$\begingroup\$

Observations

Very interesting question.

The numbers I came up with when running the program are

10248 distinct values sorted
Selection sort on 16384 items: 353 ms
Insertion sort on 16384 items: 176 ms

Which makes the insertion sort twice as fast as the selection sort. This is on Windows 10 using Visual Studio 2019 on a 4 year old Lenovo Thinkpad P50 with 32GB and an Intel i7-6820HQ processor.

After I rewrote the code to use functions, here are my results. Notice that the selection sort time went up slightly:

10248 distinct values sorted by insertion
10248 distinct values sorted by selection
selection sort on 16384 items: 355 ms
inserstion sort on 16384 items: 176 ms

I was going to add a section on global variables but when I first tried to rewrite the code I discovered a reason for them, the arrays are too large and the stack can't support them, at least on my laptop. I also used memory allocation to put as much of the data as possible on the heap rather than on the stack. That would be one way to get around any global variables.

You might want to see if you can optimize both selection and insertion to bring the numbers down.

Declare variables as you need them, the C programming language no longer requires all variables to be declared at the top of a code block.

Improvements to the Code

You worked too hard or at least wrote too much code in main().

I see 3 distinct functions possible, and one of them would have reduced the repetition of the existing code.

You can use pointers to the sort functions to make common functions for testing.

I decided to validate the sorts before testing for time, if one of the sorts doesn't work timing it doesn't make sense.

Given the implementation below you could test more sorts to find the best one by adding new sort functions.

Here are the functions I see:

int original_items[NUM_ITEMS];

static void generate_unsorted_data(void)
{
    srand(RANDOM_SEED);
    for (int i = 0; i < NUM_ITEMS; i++) {
        original_items[i] = rand() % NUM_ITEMS;
    }
}

static void validate_results(void(*ptr_to_sort_function)(int data[], unsigned int count), char *func_name)
{
    int *sorted_items = calloc(NUM_ITEMS, sizeof(*sorted_items));
    if (!sorted_items)
    {
        fprintf(stderr, "calloc failed in validate_results\n");
        return;
    }
    memcpy(sorted_items, original_items, sizeof(original_items));

    ptr_to_sort_function(sorted_items, NUM_ITEMS);

    int num_distinct = 1;
    for (int i = 1; i < NUM_ITEMS; i++) {
        if (sorted_items[i] < sorted_items[i - 1]) {
            printf("%s result validation failed.\n", func_name);
        }
        if (sorted_items[i] != sorted_items[i - 1]) {
            num_distinct++;
        }
    }

    printf("%d distinct values sorted by %s\n", num_distinct, func_name);
    free(sorted_items);
}

static void time_test_sort(void(*ptr_to_sort_function)(int data[], unsigned int count), char* func_name)
{
    clock_t start_time;
    clock_t total_time;
    int* sorted_items = calloc(NUM_ITEMS, sizeof(*sorted_items));
    if (!sorted_items)
    {
        fprintf(stderr, "calloc failed in validate_results\n");
        return;
    }

    total_time = 0;
    for (int i = 0; i < ITERATIONS; i++) {
        memcpy(sorted_items, original_items, sizeof(original_items));
        start_time = clock();
        ptr_to_sort_function(sorted_items, NUM_ITEMS);
        total_time += clock() - start_time;
    }

    printf("%s sort on %d items: %ld ms\n", func_name, NUM_ITEMS, (long)(total_time / ITERATIONS / CLOCKS_PER_MS));
    free(sorted_items);
}

int main(void) {

    generate_unsorted_data();

    validate_results(insertion, "insertion");

    validate_results(selection, "selection");

    time_test_sort(selection, "selection");

    time_test_sort(insertion, "insertion");
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you. I agree that your version of the test harness is nicely factored and readily adaptable to testing additional alternatives. As for optimizing selection and insertion, I take it that you do not see any specific improvements to suggest -- is that fair? I do not see any myself, but one of my reasons for requesting review was to let another set of eyes verify (or refute!) that my sort implementations faithfully represent their respective algorithms, and do not unfairly handicap either one. \$\endgroup\$ Aug 24 '20 at 3:12
  • 1
    \$\begingroup\$ It's not about optimizing these sorts. It's about deciding which is inherently faster; all that's needed optimization-wise is that they should each be optimized, if possible, to the same degree. \$\endgroup\$
    – Jennifer
    Aug 24 '20 at 10:53
8
\$\begingroup\$

Insertion sort allows a little known optimization. As coded, each iteration of an inner loop performs two comparisons: j > 0 and data[j - 1] > test_value. It is possible to get away with one:

if (test_value < data[0]) {
    // No need to compare data anymore. Just shift.
    for (j = i; j > 0; j--) {
        data[j] = data[j - 1];
    }
} else {
    // No need to check for indices anymore. data[0] is a natural sentinel.
    while (data[j - 1] > test_value) {
        data[j] = data[j - 1];
        --j;
    }
}
data[j] = test_value;

As a no naked loops mantra dictates, the loops shall be refactored into function, shift and unguarded_insert respectively.

To be clear, user58697 who commented on John Bollinger's answer to the linked question is me.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Curious about the "no naked loops mantra" (and skeptical about mantras in general) I cannot find good references about that \$\endgroup\$
    – edc65
    Aug 24 '20 at 12:32
  • \$\begingroup\$ @edc65 Every loop represents an important algorithm, and thus deserves a name. \$\endgroup\$
    – vnp
    Aug 24 '20 at 14:25
  • \$\begingroup\$ For the record, I wrote this Code Review question before looking into the optimization described in this answer. When I did look into it, I found that it didn't make a significant difference in the random-input test case presented in this question, but it yielded a tremendous improvement for some other kinds of inputs, such as reverse-sorted ones. \$\endgroup\$ Aug 24 '20 at 16:14
  • 1
    \$\begingroup\$ @edc65 "No raw loops" -- Sean Parent. I can't remember which conference talk specifically. It might be C++ Seasoning \$\endgroup\$
    – Justin
    Aug 24 '20 at 20:40
  • \$\begingroup\$ @Justin thx for the reference. It's Seasoning indeed \$\endgroup\$
    – edc65
    Aug 25 '20 at 6:57
5
\$\begingroup\$

As the main point of the question is about performance and not refactoring, I will address the performance of the code.

Unfortunately, the question doesn't include actual numbers, just

my Insertion sort was way faster than my Selection sort on random input (about one fourth the running time), and Insertion was a clear winner even for its worst case of reverse-sorted input.

I compiled the above code with GCC 9.2.1 on Linux, because it is the version on the computer I'm currently using.

The results are:

  • For the code in the question, random order:

      10350 distinct values sorted
      Selection sort on 16384 items: 78 ms
      Insertion sort on 16384 items: 38 ms
    
  • For inverse sorted input:

      16384 distinct values sorted
      Selection sort on 16384 items: 77 ms
      Insertion sort on 16384 items: 77 ms
    

Variation when running it multiple times is around 1ms, so the results should be sufficiently exact.

That means:

  • Your compiler is probably not as good at optimizing the selection sort, or better at optimizing the insertion sort.
  • It is to be expected that the insertion sort is faster on random data. That is because the insertion sort has a break condition in the inner loop. While both have a complexity of O(n^2), insertion sort will on average for random data only need to check half of the already sorted data, while selection sort must always check the complete unsorted rest of the data. In the case of reverse sorted input data, both algorithms need the same number inner loop executions.

It is correct that insertion moves more data around, but the way you are doing it, you get it basically for free. What that means is that the value to be moved has already been read and available for the following write, and the write goes to a memory location that is already in the cache.
Other architectures and compilers may lead to different results.

In case someone is interested in the math, the number of comparisons for the selection sort is n*(n-1)/2. This is also the worst case number for insertion sort, while the average number for insertion sort on random data is just half that value, n*(n-1)/2/2

\$\endgroup\$
3
\$\begingroup\$

I'm running this on an Haswell (4770K but the specific model shouldn't matter). I compiled with MSVC 2017 version 15.9 .. and MASM I suppose, you will see. The performance difference between the selection sort and insertion sort was 5x: 166ms vs 33ms. That difference is simmilar to what you saw, so it may be for the same reason.

I am particularly interested in insights on how the selection sort's performance might be improved, so as to ensure that the test is a fair one.

As it turns out, there may be, but whether a comparison with that version is more fair is not a simple question.

An other fairness concern in benchmarks is ensuring that what gets measures is what was intended to be measured. C code is not what actually runs, so looking at it does not necessarily give much insight into that question. With that in mind, here are the annotated "most important blocks" from both algorithms, and analyzed with Intel VTune. So here is, from selection, the important part:

Address       Instruction              Clock ticks
0x140001040   mov edx, dword ptr [r11] 1,862,000,000
0x140001043   lea r11, ptr [r11+0x4]       7,000,000
0x140001047   cmp edx, eax               700,000,000
0x140001049   mov ecx, r10d            1,736,000,000
0x14000104c   cmovnl ecx, r8d          1,837,500,000
0x140001050   cmovnl edx, eax          7,217,000,000
0x140001053   inc r10d                 4,140,500,000
0x140001056   mov r8d, ecx                 7,000,000
0x140001059   mov eax, edx               693,000,000
0x14000105b   cmp r10d, 0x4000         1,683,500,000
0x140001062   jb 0x140001040

The distribution of clock ticks does not entirely make sense when taken at face value (that inc r10d should be innocent), but some slight "smearing out" of slowdowns is normal. Anyway, cmov was used, and cmov is the main culprit according to VTune. Maybe cmov should take a lot of time, after all, it is what's really doing the work (the selection part of selection sort).

Whether cmov or a branch is used is unfortunately not up to the source code, from the point of view of C code it is an uncontrollable variable with a potentially huge impact. For completeness, it should be looked into anyway. So as an additional experiment, which I suggest you also try to replicate, I took the code that MSVC emitted for selection and modified it to use a branch (and did a minimal modification to make it work, MSVC is cheating just a little bit and not actually passing a pointer into the function but directly refers to a global):

_text SEGMENT

selection2 PROC FRAME
.endprolog
 mov         qword ptr [rsp+8],rbx  
 mov         qword ptr [rsp+10h],rsi  
 mov         qword ptr [rsp+18h],rdi  
 mov         rsi,rcx  
 mov         r9d,1  
 mov         rbx,rsi  
_block2:
 mov         eax,dword ptr [rbx]  
 mov         edi,eax  
 lea         r8d,[r9-1]  
 mov         r10d,r9d  
 cmp         r9d,4000h  
 jae         _block5  
 mov         ecx,r9d  
 lea         r11,[rsi+rcx*4]  
_block4:
 mov         edx,dword ptr [r11]  
 lea         r11,[r11+4]  
 cmp         edx,eax  
 jge _skip
 mov r8d, r10d
 mov eax, edx
_skip:
 inc r10d
 cmp         r10d,4000h  
 jb          _block4
_block5:
 inc         r9d  
 mov         ecx,r8d  
 mov         dword ptr [rsi+rcx*4],edi  
 mov         dword ptr [rbx],eax  
 add         rbx,4  
 lea         eax,[r9-1]  
 cmp         eax,3FFFh  
 jb          _block2  
 mov         rbx,qword ptr [rsp+8]  
 mov         rsi,qword ptr [rsp+10h]  
 mov         rdi,qword ptr [rsp+18h]  
 ret 
selection2 ENDP

END

(various modifications would be needed to port this to linux, re-doing the cmov-to-branch conversion would be easier)

Imported on the C side with extern void selection2(int* data);.

Result: 72ms. Much faster! It's still twice as slow as insertion sort, but it's a huge improvement compared to the cmov version.

But what is fair, is the cmov version fair? That is what MSVC outputs by default, so in that sense it is representative of the "real life performance of selection sort", maybe.. but the cmov is not inherent to the algorithm, it's an artifact from an (apparently mistaken!) compiler optimization. A different compiler can just as well decide to use a branch, which could be why @pacmaninbw reports a similar 2x perf gap rather than a 4x or 5x gap.

Fortunately (maybe?) Selection Sort lost both ways, so all of this doesn't change the winner, but it could have.

The code MSVC outputs for insertion is actually not that interesting to look at. The assembly code does exactly what you'd expect, no curve balls. It's good to look, though, just in case.

Finally, I'll note that both algorithms can be optimized using SIMD, which has the potential to upset the balance. It could be seen as "unlocking the true potential" of those algorithms, so maybe it is fair in that sense. Or it could be seen as "going too far" - is that still representative of the algorithms or gone way past that into comparing specific snippets of assembly code, and unfair in that sense.

\$\endgroup\$
1
  • \$\begingroup\$ Interestingly, I found that with a newer GCC, the relative performance of the selection sort improved to the same factor of 2 slower that seems to be showing up in others' tests. In all cases I am compiling with a high optimization level enabled, on the assumption -- not necessarily fulfilled, as you point out -- that that will yield comparably good results for both algorithms. \$\endgroup\$ Aug 24 '20 at 23:24

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.