qsort_b和qsort

Question

编写一个程序,在Mac上用C++演示不同的排序算法.我找到了两个quicksort实现,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后缀的相应例程,期望compar回调是块指针而不是函数指针.(来自BSD MAN PAGE)

编辑:速度差异.DATA为1000000时,qsort以146832 ns完成,qsort_b为127391 ns.考虑到它的速度提高了10%,这是一个相对较大的差异.

编辑:我编辑了代码,使得更大的整数数组成为可能.我个人最大的测试结果是1亿个整数,28136278(28s)和23870078(24s).这对我来说是一个很大的不同.

Answer 1

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

块是一个对象，更是一个栈对象。唯一允许在堆栈中创建的对象（至少没有一些技巧）。

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

因此，这不是优化问题，而是Block. 它没有任何堆栈变量的PUSH和POP的函数调用开销。

作为您问题的答案，qsort()并qsort_b()没有任何算法差异，而是详细的结构，块与函数。