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

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

1 голос
/ 15 мая 2019

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

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

1 Ответ

0 голосов
/ 15 мая 2019

Этот пример кода работает примерно на 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);
    }
}
...