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