在 C++ Introsort 中手动展开循环运行不正确

Question

我正在用 C++ 编写一个简单的就地 introsort，其中我试图在分区函数中手动展开一个循环以进行优化。我将在下面包含的程序可以编译，但无法正确排序随机列表。

这个程序正在为 RISC-V 架构编译，甚至在 -Ofast 下，(riscv-64-unknown-elf-gcc) gcc 似乎并没有自行展开循环，使手动检查每个循环以确保满足结束条件。我想 space 此检查以尝试最大化性能 - 据我了解，某些编译器默认情况下最终会这样做。

我已经尝试将这个循环分成 5 个块，以便在我进一步研究之前证明这个概念（可能有多个部分，例如尝试通过 32 组然后尝试通过 16 组等），然后像以前一样处理数组的最后几个元素。展开前程序运行良好，但现在排序失败，我不确定如何继续。

这里是有问题的分区函数：

int* partition(int *startptr, int *endptr) {
    int x = *endptr; // threshold
    int *j, tmp, tmp2, *i = startptr - 1;
    for (j = startptr; j+5 < endptr; j+=5) {

        int pj = *j;
        if (pj <= x) {
            i += 1;
            tmp = *i;
            *i = pj;
            *j = tmp;
        }

        pj = j[1];
        if (pj <= x) {
            i += 1;
            tmp = *i;
            *i = pj;
            *j = tmp; }

        pj = j[2];
        if (pj <= x) {
            i += 1;
            tmp = *i;
            *i = pj;
            *j = tmp; }

        pj = j[3];
        if (pj <= x) {
            i += 1;
            tmp = *i;
            *i = pj;
            *j = tmp; }

        pj = j[4];
        if (pj <= x) {
            i += 1;
            tmp = *i;
            *i = pj;
            *j = tmp; }
        }

    j -= 5; 
    for (int *y = j; y < endptr; y++) {
        int py = y[0];
        if (py <= x) {
            i += 1;
            tmp = *i;
            *i = py;
            *y = tmp;
            } 
        }

    int *incrementedi = i + 1;
    tmp = *incrementedi;   //p[i+1]
    tmp2 = *endptr; //p[end]
    *endptr = tmp;
    *incrementedi = tmp2;
    return i + 1;
 }

在程序结束时，我打印出数组并循环遍历，断言这是按预期升序排列的。输出似乎按小块排序，但并不完全准确，我不确定如何继续。谢谢！

编辑澄清：我正在通过查看 ...-gcc -S 的输出来验证循环实际上并未展开。分区函数很好地内联，但它仍会在每次迭代时执行检查。

值得注意的是，出于类似的原因，我尽可能地使用指针 - 当我们不必将数组索引转换为实际指针时，编译器不会优化我们获得的指令节省。

Answer 1

此示例代码有效，在 64 位模式（更多寄存器）下速度提高了大约 11%。编译器通过 tmp 优化了 pj[...] 的比较和条件副本以使用寄存器（并且循环通过寄存器以允许一些重叠）。

int * Partition(int *plo, int *phi)
{
    int *pi = plo;
    int *pj = plo;
    int pvt = *phi;
    int tmp;
    int *ph8 = phi - 8;
    for (pj = plo; pj < ph8; pj += 8)
    {
        if (pj[0] < pvt)
        {
            tmp = pj[0];
            pj[0] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[1] < pvt)
        {
            tmp = pj[1];
            pj[1] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[2] < pvt)
        {
            tmp = pj[2];
            pj[2] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[3] < pvt)
        {
            tmp = pj[3];
            pj[3] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[4] < pvt)
        {
            tmp = pj[4];
            pj[4] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[5] < pvt)
        {
            tmp = pj[5];
            pj[5] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[6] < pvt)
        {
            tmp = pj[6];
            pj[6] = *pi;
            *pi = tmp;
            ++pi;
        }
        if (pj[7] < pvt)
        {
            tmp = pj[7];
            pj[7] = *pi;
            *pi = tmp;
            ++pi;
        }
    }
    for (; pj < phi; ++pj)
    {
        if (*pj < pvt)
        {
            tmp = *pj;
            *pj = *pi;
            *pi = tmp;
            ++pi;
        }
    }
    tmp  = *phi;
    *phi = *pi;
    *pi  = tmp;
    return pi;
}

void QuickSort(int *plo, int *phi)
{
int *p;
    if (plo < phi)
    {
        p = Partition(plo, phi);
        QuickSort(plo, p-1);
        QuickSort(p+1, phi);
    }
}

在 C++ Introsort 中手动展开循环运行不正确

Manual loop unrolling within a C++ Introsort Runs Incorrectly

c++

optimization

quicksort

loop-unrolling