c - 为什么我的快速排序在大量输入时会崩溃？

Question

我创建了一个中位数为 3 的标准快速排序实现，它对大量随机整数进行排序。我想至少增加到 1 亿个元素，但最好是 10 亿个。为了提高速度，我试图在 Cilk++ 中并行化算法。该算法使用双重递归，我生成 Cilk 任务来执行每个递归排序。

我的算法适用于最大大小为 10 000 000 的数组。如果没有 Cilk 关键字，我的顺序算法可以轻松处理 1 亿个元素，但是当我尝试使用 Cilk 时程序崩溃到桌面。我现在想找出原因。我是不是生成太多 Cilk 任务太快了？

我正在使用 Windows 7 64 位、Intel++ 编译器和集成在 Visual Studio 2010 中的 Intel Parallel Studio XE 2013。该程序被编译为 32 位应用程序。存储随机数据的内存分配为对 malloc 的单个调用，并检查指针。在中位数计算中，在计算中间元素时也防止了整数溢出。

这很可能是缓冲区溢出问题。

这是我的分区:

int pivotvalue = medianOf3(data, low, high);
// pivot is placed next to the last element

int left = low;
int right = high - 1;
while (left < right) {
    while (data[left] < pivotvalue) {
        left++;
        if (left > high) {
            break;
        }
    }
    while (data[right] >= pivotvalue) {
        right--;
        if (right < low) {
            break;
        }
    }

    if (left < right) {
        swap(data, left, right);
    }
}

// restore pivot
swap(data, left, high - 1);
return left;

Answer 1

我不知道 Cilk 是如何工作的，但我记得需要修复嵌入式平台上的快速排序实现，该实现可能会因递归而溢出堆栈。解决方法是对较小的“一半”数据使用递归调用，并在函数内处理较大的“一半”(即尾递归)。排序(或反向排序)列表总是会触发溢出，因为调用图的深度等于列表中的元素数。

您能使用调试器找出导致崩溃的原因吗？您能否将每次进入 swap() 的数据转储到日志文件中，然后查看函数在崩溃前调用的内容是什么样的？是否可以在每次调用时转储堆栈的大小？ 是否每个 Cilk 任务都有自己的堆栈，并且可能比非 Cilk 版本中使用的堆栈更小？

您可以通过将带有堆栈地址的参数添加到 swap() 来跟踪堆栈使用情况。第一次调用和任何新的 Cilk 线程都使用 NULL。每个递归调用都使用该参数(如果它不是 NULL)，或者使用其局部变量之一的地址来确定其堆栈所在的位置。转储地址差异，或在全局范围内跟踪它，并且仅在它超过之前的最大值时才报告它。