qsort_b和qsort提问

Question

在Mac上编写一个展示不同排序算法的C++程序。我发现了两个快速排序的实现，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手册页）

编辑：速度差异。对于DATA为1000000，qsort在146832 ns内完成，而qsort_b在127391 ns内完成。考虑到它约快10％，这是一个相对较大的差异。

编辑：我已经编辑了代码，使得可能拥有更大的整数数组。我的个人最大测试结果是100000000个整数，28136278（28秒）与23870078（24秒）。对我来说，这是一个相当大的差异。

- Shane Hsu

---

@KarthikT 我不确定计量单位，但我认为是纳秒。使用qsort，结果为146832，使用qsort_b，结果为127391。其中DATA的值为1000000。 - Shane Hsu

我已经使用越来越大的数据进行了测试，100000000个整数。它是28136278（28秒）对23870078（24秒）。对我来说，这是一个相当大的差异。 - Shane Hsu

似乎是一种非标准函数，因为这个"qsort_b"是我能找到唯一提到的。 - Rapptz

@Rapptz 您是正确的，它是非标准的，并且只出现在我的 Mac 上。我可以在我提供的链接中找到它在 BSD 手册上的参考。 - Shane Hsu

@0x69 我认为块无法通过宏模拟 - 块可以传递给编译库函数，这些函数无法访问调用者的源代码，因此无法展开宏。对于像 qsort_b 这样的函数也是如此 - 调用可能更快，但真正的内联无法发生，因为 qsort_b 本身已经被编译。 - user4815162342

Answer 1

Objective-C中的Block是一种不同类型的实体。它可能看起来像MACRO(在编译前替换)和inline functions(告诉编译器"尽你最大努力消除函数调用开销")，但总体结构比这些结构都要不同得多。

Block是一个对象，更进一步说是一个堆栈对象。唯一允许在堆栈中创建的对象(至少没有一些技巧).

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

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

回答你的问题，qsort()和qsort_b()在算法上没有任何区别，但在结构上有所不同，主要是块与函数的区别。

- Cahit Gungor

Answer 2

我认为这是优化上的差异。使用qsort_b时，编译器可能会内联比较操作，而使用qsort则不会。因此，每次比较都需要额外的函数调用开销。

- hyde

---

你必须是正确的。如果我错了，请纠正我，块在这种特定情况下就像内联函数。而内联函数被认为比函数调用更快。(https://dev59.com/UW865IYBdhLWcg3wCqHI) - Shane Hsu

@ShaneHsu 我对这些“块”一无所知，除了刚刚从http://en.wikipedia.org/wiki/Blocks_(C_language_extension)上读到的内容，因此无法评论编译器为它们生成什么样的代码。如果您想真正理解正在发生的事情，请添加编译器命令行开关以产生asm源文件（而不是目标文件），并将两种情况进行比较。另一个实验可能是尝试关闭优化后的两个版本，然后将其最大化，并查看它如何影响相对性能。 - hyde

稍后会进行实验。谢谢！ - Shane Hsu

如果qsort_b是一个已经以编译形式存在于系统中的库函数，我不认为它能够内联调用块。也许qsort_b只是使用了更好的排序算法，或者块具有稍微更有效的调用约定？ - user4815162342