Ручное развертывание цикла в C++ Introsort выполняется неправильно

Я пишу простую интросортировку на месте на C++, в которой я пытаюсь вручную развернуть цикл внутри функции разделения для оптимизации. Программа, которую я приведу ниже, компилируется, но не может правильно отсортировать случайный список.

Эта программа компилируется для архитектуры RISC-V, и даже под -Ofast (riscv-64-unknown-elf-gcc) gcc, похоже, не разворачивает цикл самостоятельно, выполняя ручную проверку каждый цикл через чтобы обеспечить выполнение конечного условия. Я хотел бы отложить эту проверку, чтобы попытаться максимизировать производительность - насколько я понимаю, некоторые компиляторы делают это по умолчанию.

Я попытался разбить этот цикл на куски по 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. Функция разделения прекрасно встраивается, но по-прежнему выполняет проверку на каждой итерации.

Стоит отметить, что я всегда использую указатели по той же причине — компилятор не оптимизируется для экономии инструкций, которую мы получаем, когда нам не нужно преобразовывать индексы массива в фактические указатели.


person jaytlang    schedule 15.05.2019    source источник
comment
Я не большой поклонник метапрограммирования шаблонов, но опять же я не большой поклонник ручной оптимизации. Разве это не один из тех случаев, когда вы можете использовать шаблоны, чтобы позволить компилятору сгенерировать это для вас?   -  person CompuChip    schedule 15.05.2019
comment
Я слышал об этом здесь и там, и это кажется отличной идеей, хотя я действительно не знаком с концепцией/реализацией. Я буду исследовать дальше, но как можно создать шаблон для этого?   -  person jaytlang    schedule 15.05.2019
comment
Я хотел бы привести пример, но я боюсь, что все может быть перепутано. Возможно, мы должны использовать этот вопрос, чтобы решить проблему с циклом в первую очередь; тогда, если у вас есть работающий код, вы можете опубликовать отдельный вопрос здесь (или на CodeReview), и я буду рад предоставить шаблонную версию.   -  person CompuChip    schedule 15.05.2019
comment
Хорошо! Как только я смогу заставить это доказательство концепции работать и увидеть, как это влияет на количество инструкций, я спрошу о шаблонах и посмотрю, как далеко мы можем продвинуться с этим. Спасибо!   -  person jaytlang    schedule 15.05.2019
comment
Я не мог оставить это в покое, поэтому все равно сделал это, извините :-) godbolt.org/z/M4b050< /а>   -  person CompuChip    schedule 16.05.2019
comment
Это потрясающе - и кажется, что писать очень просто. Благодарю вас! Попробую позже сегодня и посмотрю его в действии с компилятором RISC.   -  person jaytlang    schedule 18.05.2019


Ответы (1)


Этот пример кода работает примерно на 11% быстрее в 64-битном режиме (больше регистров). Компилятор оптимизировал сравнение и условную копию pj[...] через tmp для использования регистра (и он циклически перебирал регистры, чтобы допустить некоторое совпадение).

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);
    }
}
person rcgldr    schedule 15.05.2019
comment
Спасибо - это работает хорошо! Цикл развернулся хорошо, и для моего тестового массива я увидел снижение с 228 000 циклов до 188 000 циклов для сортировки. Это невероятно полезно! - person jaytlang; 15.05.2019
comment
@jaytlang — это раздел Lomuto, который подходит для случайных данных, но если есть много дубликатов или если данные значительно предварительно упорядочены (или перевернуты), раздел Hoare будет работать быстрее, и нет смысла разворачивать его тесные циклы, так как в любом случае задействована условная ветвь. - person rcgldr; 16.05.2019