Ускорение цикла do-while с развертыванием цикла

Question

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

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

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

Answer 1

Вы не должны ожидать, что ваша программа будет быстрее за счет разворачивания цикла, потому что при правильно выбранном диапазоне ([-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);

, получилось бы.

Answer 2

Пахнет как математическая 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 библиотека может также привести к некоторому ускорению.