c - 如何改进基数排序的实现？

Question

我正在实现 2 字节基数排序。其概念是使用计数排序，对整数的低 16 位进行排序，然后对高 16 位进行排序。这允许我在两次迭代中运行排序。我的第一个想法是试图找出如何处理底片。由于负数的符号位将被翻转，因此以十六进制形式，这将使负数大于正数。为了解决这个问题，我在符号位为正时翻转符号位，以使 [0, 2 bil) = [128 000 000 000, 255 255...)。当它为负数时，我翻转所有位，使其范围从 (000 000 .., 127 255 ..) 开始。这个site帮助我了解了这些信息。为了完成它，我会根据 channel 将整数拆分为顶部或底部 16 位。以下是允许我执行此操作的代码。

static uint32_t position(int number, int pass) {
    int mask;
    if (number <= 0) mask = 0x80000000;
    else mask = (number >> 31) | 0x80000000;
    uint32_t out = number ^ mask;
    return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff;
}

为了开始实际的基数排序，我需要形成一个大小为 65536 个元素的直方图。我遇到的问题是当输入的元素数量非常大时。创建直方图需要一段时间，因此我使用进程和共享内存并行实现它。我将数组划分为大小为/8 的子部分。然后，在大小为 65536 * 8 的共享内存数组上，我让每个进程创建自己的直方图。之后，我将它们汇总在一起形成一个直方图。以下是相关代码:

for (i=0;i<8;i++) {
    pid_t pid = fork();
    if (pid < 0) _exit(0);
    if (pid == 0) {
        const int start = (i * size) >> 3;
        const int stop  = i == 7 ? size : ((i + 1) * size) >> 3;
        const int curr  = i << 16;
        for (j=start;j<stop;++j)
            hist[curr + position(array[j], pass)]++;
        _exit(0);
    }
}
for (i=0;i<8;i++) wait(NULL);

for (i=1;i<8;i++) {
    const int pos = i << 16;
    for (j=0;j<65536;j++)
        hist[j] += hist[pos + j];
}

接下来的部分是我花了大部分时间分析缓存如何影响前缀和性能的地方。通过 8 位和 11 位传递基数排序，所有直方图都适合 L1 缓存。对于 16 位，它只适合 L2 缓存。最后，16 位直方图计算总和的速度最快，因为我只需要用它运行 2 次迭代。我还按照 CUDA 网站的建议并行运行前缀和。对于 2.5 亿个元素，其运行速度比 16 位整数慢约 1.5 秒。所以我的前缀和最终看起来像这样:

for (i=1;i<65536;i++)
    hist[i] += hist[i-1];

剩下的唯一事情就是向后遍历数组并将所有元素放入临时数组中各自的位置。因为我只需要执行两次，而不是从临时文件复制回数组，然后再次运行代码。我首先使用数组作为输入，并使用 temp 作为输出来运行排序。然后使用 temp 作为输入和 array 作为输出第二次运行它。这使我无法两次将内存复制回数组。对于实际排序，代码如下所示:

histogram(array, size, 0, hist);
for (i=size-1;i>=0;i--)
    temp[--hist[position(array[i], 0)]] = array[i];

memset(hist, 0, arrSize);
histogram(temp, size, 1, hist);
for (i=size-1;i>=0;i--)
    array[--hist[position(temp[i], 1)]] = temp[i];

This link包含我迄今为止拥有的完整代码。我对快速排序进行了测试，对于整数和 float ，它的运行速度快了 5 到 10 倍，而对于 8 字节数据类型，它的运行速度大约快 5 倍。有没有办法改进这个问题？

Answer 1

我的猜测是，在运算期间处理整数的符号是​​不值得的。它会使代码变得复杂并减慢速度。我会进行第一次排序，如无符号，然后执行第二条路径，仅对两半重新排序并反转其中一个负数。

另外，从您的代码中，我不明白您如何让不同的进程一起运行。如何收集父级中的直方图？你有一个进程共享变量吗？无论如何，在这里使用 ptrhead 会更合适。