Ускорение цикла do-while с помощью разворачивания цикла

Я пытаюсь ускорить код в функции, которая может вызываться много раз (возможно, более миллиона). Код связан с установкой двух переменных в случайные числа и нахождением квадрата расстояния. Моей первой идеей для этого является развертывание цикла, но я немного запутался в том, как мне это выполнить, из-за условия while, которое диктует это.

Чтобы ускорить мою программу, я заменил встроенную в С++ функцию rand() пользовательской, но я не знаю, как сделать мою программу еще быстрее.

do {
    x = customRand();
    y = customRand();
    distance = x * x + y * y; // euclidean square distance
} while (distance >= 1.0);

c++ do-while loop-unrolling
person Saul    schedule 25.05.2019    source источник
comment
Развертывание цикла сегодня — это микрооптимизация, которую ваш компилятор более чем способен определить, есть ли какая-либо польза от этого типа оптимизации в вашем случае. Лучше сосредоточиться на написании ясного, хорошо документированного кода, а микрооптимизацию оставить компилятору (он сделает работу гораздо лучше в 9999 случаях из 10000, с гораздо меньшей вероятностью ошибки).   -  person David C. Rankin    schedule 25.05.2019
comment
Это действительно зависит от того, что возвращает customRand(). От 0 до 100 намного сложнее получить distance < 1.0, но от 0 до 1 это происходит быстрее.   -  person Hatted Rooster    schedule 25.05.2019
comment
У вас будет несколько строк if (x*x+y*y<1) break; в цикле. Но я сомневаюсь, что это ускорит казнь. Вы должны сравнить время выполнения между кодом, оптимизированным компилятором, и вашей собственной оптимизацией.   -  person Dialecticus    schedule 25.05.2019
comment
Вы не должны использовать rand. Я не хочу недооценивать ваши навыки программирования, но вы уверены, что <random> библиотека хуже, чем ваша customRand?   -  person Quimby    schedule 25.05.2019
comment
Скорость вашего кода, скорее всего, продиктована сложностью генератора случайных чисел.   -  person mfnx    schedule 25.05.2019
comment
Во-первых, используйте <random> и найдите подходящий генератор, отвечающий вашим потребностям. Вместо того, чтобы продолжать генерировать случайные значения до тех пор, пока вы не получите пару, отвечающую вашим требованиям, преобразуйте значения x и y так, чтобы они однозначно соответствовали вашим требованиям. Например, если вы выбираете генератор, который гарантированно генерирует значение от 0 до 10, простое добавление 1 к x и y гарантирует выполнение вашего условия. Не нужно вычислять distance, не нужно его проверять и вообще не нужен цикл.   -  person Peter    schedule 25.05.2019
comment
Развертывание цикла является оптимизацией только в том случае, если оно может амортизировать условие завершения цикла. Явно не практично в данном случае. Вы можете оптимизировать его, этот цикл может занять значительное время, только если случайные числа малы. Нет смысла делать пулю, чтобы добраться до 1.0 с хорошо распределенными случайными числами. Просто дайте ему преимущество и начните, скажем, с расстояния = 0,9;   -  person Hans Passant    schedule 25.05.2019

Ответы (2)


arrow_upward
1
arrow_downward

Вы не должны ожидать, что ваша программа ускорится за счет развертывания цикла, потому что при правильно выбранном диапазоне ([-1, 1]) для вывода генератора случайных чисел тело вашего цикла будет выполнено только один раз более чем в 3/4 случаев.

Что вы можете сделать, чтобы помочь компилятору, так это пометить ваше условие while как «маловероятное». Например, в GCC это будет:

#define unlikely(x) __builtin_expect((x),0)

do {
    x = customRand();
    y = customRand();
    distance = x * x + y * y; // euclidean square distance
} while (unlikely(distance >= 1.0));

Тем не менее, даже это вряд ли заметно ускорит ваш код.

Если вы про гарантированное время а не скорость, то для равномерного случайного распределения внутри круга, при customRand() равномерно распределенном в [-1, 1]

r = std::sqrt(std::abs(customRand()));
t = M_PI * customRand();
x = r * std::cos(t);
y = r * std::sin(t);

бы сделать свое дело.

person Kit.    schedule 25.05.2019
comment
В этой конкретной ситуации GCC генерирует точно такой же ассемблерный код с __builtin_expect и без него: godbolt.org/z/NWi- р9. - person Evg; 25.05.2019
comment
Это зависит от того, может ли компилятор увидеть тело customRand() и что это за тело. Например, здесь генерируется другой код. Но, как я уже сказал, вряд ли это что-то заметно ускорит в данной конкретной задаче. - person Kit.; 25.05.2019
comment
Соглашаться. Забавный у вас пример: цикл do вырождается в бесконечный тривиальный A: jmp A;, и вы либо прыгаете в него после однократного выполнения тела do, либо нет. - person Evg; 25.05.2019

arrow_upward
0
arrow_downward

Это похоже на математическую задачу XY, но сначала я сосредоточусь на ваш вопрос об ускорении цикла. Я все же буду заниматься математикой.

Таким образом, базовое ускорение может использовать раннее continue, если любое из x или y больше или равно 1.0. Нет никаких шансов, что x*x + y*y < 1.0, когда одно из x или y больше, чем 1.

do {
    float x = customRand();
    if (x >= 1.0) {
        continue;
    }
    float y = customRand();
    if (y >= 1.0) {
        continue;
    }
    distance = x * x + y * y; // euclidean square distance
} while (distance >= 1.0);

К сожалению, это, скорее всего, испортит механизм прогнозирования ветвлений современных процессоров и все еще может не дать большого ускорения. Ориентиры, как всегда, потребуются.

Кроме того, поскольку самый быстрый код — это тот, который не запускается, давайте обсудим потенциальную проблему XY. Кажется, вы создаете точку, ограниченную кругом с радиусом 1.0. В декартовой системе это трудная задача, но очень простая в полярной системе, где каждая точка на диске описывается радиусом и углом и может быть легко преобразована в декартову. Я не знаю, какое распределение вы ожидаете по области диска, но см. здесь ответы на эту проблему: Создать случайную точку внутри круга ( равномерно)

PS. Есть несколько правильных замечаний о <random>, которая как библиотека std также может привести к некоторому ускорению.

person R2RT    schedule 25.05.2019