CODEWITHSUNDEEP
c++do-whileloop-unrolling
Saul
Saul

Reputation: 311

Speeding up a do-while loop with loop unrolling

I am trying to speed up code in a function that may be called many times over (maybe more than a million). The code has to do with setting two variables to random numbers and finding squared distance. My first idea for this is loop unrolling but I am a bit confused on how I should execute this because of the while condition that dictates it.

To speed up my program I have replaced the c++ built in rand() function with a custom one but I am stumped on how to make my program even faster. 

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

Upvotes: 1

Views: 539

Answers (2)

Kit.
Kit.

Reputation: 2406

You shouldn't expect to make your program faster by loop unrolling, because with a properly selected range ([-1, 1]) for the random number generator output your loop's body will be executed just once in more than 3/4 of the cases.

What you might want to do to help the compiler is to mark your while condition as "unlikely". For example, in GCC it would be:

#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));

Still, even this is unlikely to speed up your code in a measurable way.

If you were about guaranteed time and not speed, then for an uniform random distribution within a circle, with customRand() uniformly distributed in [-1, 1]

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

would do the trick.

Upvotes: 1

R2RT
R2RT

Reputation: 2146

It smells like a math-based XY problem, but I will first focus on your question about loop speedup. I will still do some math though.

So basic speedup may use early continue if any of x or y is bigger or equal 1.0. There is no chance that x*x + y*y < 1.0 when one of x or y is bigger than 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);

Unfortunately, it most likely screws up modern CPUs branch prediction mechanism and still may not give big speedup. Benchmarks, as always, would be required.

Also, as the fastest code is the one which does not run, let's discuss the potential XY problem. You seem to generate point which is bounded by circle with radius 1.0. In Cartesian system it is tough task, but it is really easy in polar system, where each point in disk is described with radius and angle and can be easily converted to Cartesian. I don't know what distribution do you expect over disk area, but see answers for this problem here: Generate a random point within a circle (uniformly)

PS. There are some valid comments about <random>, which as std library may lead to some speedup as well.

Upvotes: 0

Related Questions