qsort_b and qsort

问题:

Writing a program that demonstrate different sorting algorithm in C++ on Mac. I found two quicksort implementation, qsort and qsort_b.

The first one is of course the old-fashioned, seen-everywhere qsort. But there's qsort_b, which takes an block rather than a function. Here's my code:

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <ctime>

#define DATA 1000000

using namespace std;

int compare(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

int main(int argc, char *argv[])
{
    int* array = new int[DATA];

    srand(time(0));

    for ( int i = 0 ; i < DATA ; ++ i )
    {
        array[i] = rand() % 2147483647;
    }

    clock_t begin = clock();

    qsort(array, DATA, sizeof(array[0]), compare);
    //qsort_b(array, DATA, sizeof(array[0]), ^(const void* a, const void* b) { return *(int*)a - *(int*)b; });

    clock_t end = clock();

    cout << "Time it takes to sort " << DATA << " integers with quicksort: " << end - begin;
}

Here I see big speed difference, what's causing all that difference. To my understanding, blocks is for parallel processing, which in this case won't be faster than functions. There's nothing to parallel process, is there?

EDIT: The heapsort_b(), mergesort_b(), and qsort_b() routines are like the corresponding routines without the _b suffix, expect that the compar callback is a block pointer instead of a function pointer. (FROM BSD MAN PAGE)

EDIT: The speed difference. With DATA being 1000000, qsort finished it in 146832 ns, with qsort_b, in 127391 ns. It's a relatively big difference considering it's about 10% faster.

EDIT: I've edited the code to make it possible to have even bigger array of integers. My personal biggest test result are 100000000 integers, 28136278 (28s) vs. 23870078 (24s). It's a considerably big difference to me.

回答1:

Objective-C Block is a different kind of animal. It may seem like MACRO(substitution before compilation), and inline functions(telling compiler "Do your best to eliminate function call overhead"), but the overall structure is much more different than those structures.

Block is an object, furthermore, a stack object. The only object that is allowed to be created in the stack (at least without some tricks).

When a Block object created in the stack, compiler adds all local variables, block variables, the addresses of read/write variables it references, and a pointer to block's executable code. So even before starting to execute, everything is ready for computation without any stack operation.

So, it is not an optimization issue, rather an attribute of the Block. It does not have any function call overhead of PUSH and POP s of stack variables.

As an answer to your question, qsort() and qsort_b() does not have any algorithmic difference, but the elaborated structure, block vs function.

回答2:

Looks like optimization difference to me. With qsort_b, the compiler probably inlines the comparison, while with qsort does not. The difference is overhead of function call per comparison.