qsort_b和qsort

Question

编写了一个程序，演示了不同的排序算法在C++的Mac。我发现了两个快速排序实现，qsort和qsort_b。

第一个当然是老式的，随处可见的qsort。但是还有qsort_b，它接受一个块而不是一个函数。下面是我的代码：

#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;
}

在这里我看到了巨大的速度差异，是什么导致了所有的差异。据我所知，块是用于并行处理的，在这种情况下，并行处理的速度不会比函数快。没有什么可以并行处理的，不是吗？

编辑: heapsort_b()、mergesort_b()和qsort_b()例程类似于没有_b后缀的相应例程，只是比较回调是块指针而不是函数指针。(FROM BSD MAN PAGE)

编辑:速度差异。在数据为1000000的情况下，qsort在146832 ns内完成，qsort_b在127391 ns内完成。考虑到它快了大约10%，这是一个相对较大的差异。

编辑:我已经对代码进行了编辑，使其可以拥有更大的整数数组。我个人最大的测试结果是100000000个整数，28136278 (28秒)对23870078 (24秒)。这对我来说是一个相当大的不同。

Answer 1

Objective-C Block是一种不同的动物。它可能看起来像MACRO(编译前的替换)和inline functions(告诉编译器“尽最大努力消除函数调用开销”)，但整体结构比这些结构更不同。

Block is an object，a stack object.允许在堆栈中创建的唯一对象(至少没有一些技巧)。

当在堆栈中创建Block对象时，编译器会添加所有局部变量、块变量、它引用的读/写变量的地址以及指向块的可执行代码的指针。因此，即使在开始执行之前，一切都已准备好进行计算，而无需任何堆栈操作。

它没有任何堆栈变量的PUSH和POP的函数调用开销。

作为你的问题的答案，qsort()和qsort_b()没有任何算法上的区别，但精心设计的结构，块与函数。

Answer 2

在我看来，这是优化的区别。在qsort_b中，编译器可能会内联比较，而在qsort中则不会。不同之处在于每次比较时函数调用的开销。