7
\$\begingroup\$

I am trying to learn how branch optimization works.

For an experiment, I have a recursive fractal terrain generation and I have moved all if statements to binary tables (don't know the words, will comment in code).

Is doing what I have done in the code better than using if's, it runs about 15% faster.

Is there a better way of doing this so that the generation is faster?

Again, I am just trying to learn how I would make this code more efficient, I have no real need for it to be though.

TerrainChunkGenerator.h

#include <cstdlib>
#include <ctime>
#include <chrono>
#include <functional>
#include <map>
#include "TerrainChunk.h"
class TerrainChunkGenerator{
private:
    TerrainChunk* chunk_;
    unsigned width_, length_, lod_;
    unsigned num_bytes_, num_vertices_, num_triangles_;
    // Recursive Generator variables
    float x0_, x1_;
    float y0_, y1_;
    float mx_, my_;
    float h_;
    float avg_d_;
    float avg_s0_, avg_s1_, avg_s2_, avg_s3_;
    float divisor_;

    // These are the binary things I was talking about
    std::function<void()> sq_step_funcs_mx_y0_[2];
    std::function<void()> sq_step_funcs_mx_y1_[2];
    std::function<void()> sq_step_funcs_x1_my_[2];
    std::function<void()> sq_step_funcs_x0_my_[2];

    std::function<void()> quadrant_functions_[4];
    std::map<float, std::map<float, float>> points_; // height map
    float* mesh_; // triangles woven from vertices_
public:
    TerrainChunkGenerator();
    TerrainChunkGenerator(unsigned width, unsigned length, unsigned lod = 6u);
    void Generate();
    TerrainChunk* chunk();
private:
    void GenPoints();
    void Recurse(unsigned count, unsigned quad, float x0, float y0, float x1, float y1);
    float Random();
};

In the cpp the Generate func is called to start generation. In the Generate func there is a GenMesh func which calls Recurse and that is where the start of the lambda calling and the stand ins for if statements exists.

TerrainChunkGenerator.cpp

#include "TerrainChunkGenerator.h"

TerrainChunkGenerator::TerrainChunkGenerator(){}
TerrainChunkGenerator::TerrainChunkGenerator(unsigned width, unsigned length, unsigned lod){
    width_ = width;
    length_ = length;
    lod_ = lod;
    num_triangles_ = 2 * pow(4, lod_);
    num_vertices_ = 3 * num_triangles_;
    num_bytes_ = sizeof(float) * 3 * num_vertices_;

    // Lambdas
    auto void_lambda = [&]{ return; };
    // Square Step Functions
    // Top: mx y0
    sq_step_funcs_mx_y0_[0] =
        [&]{
        points_[mx_][y0_] =
            ((points_[x0_][y0_] + points_[x1_][y0_]) / 2.0f) // Top Edge
            + (Random() / divisor_);
    };
    sq_step_funcs_mx_y0_[1] = void_lambda;

    // Bottom: mx y1
    sq_step_funcs_mx_y1_[0] =
        [&]{
        points_[mx_][y1_] =
            ((points_[x1_][y1_] + points_[x0_][y1_]) / 2.0f) // Bottom Edge
            + (Random() / divisor_);
    };
    sq_step_funcs_mx_y1_[1] = void_lambda;

    // Right: x1 my
    sq_step_funcs_x1_my_[0] =
        [&]{
        points_[x1_][my_] =
            ((points_[x1_][y0_] + points_[x1_][y1_]) / 2.0f) // Right Edge
            + (Random() / divisor_);
    };
    sq_step_funcs_x1_my_[1] = void_lambda;

    // Left: x0 my
    sq_step_funcs_x0_my_[0] =
        [&]{
        points_[x0_][my_] =
            ((points_[x0_][y1_] + points_[x0_][y0_]) / 2.0f) // Left Edge
            + (Random() / divisor_);
    };
    sq_step_funcs_x0_my_[1] = void_lambda;

    // THIS STEP IS OF MOST INTEREST TO ME
    // Instead of checking if there is something already set in the points_ map
    // I get a yes or no if it has a set element...
    // points_[..][..] will equal 0.0f which makes
    // the bool expression return false and the array will point at 
    // a lambda function to execute, either a func to put something in the map
    // or a function that just returns.
    // Is this better than branching with if statements?
    // Quadrant Functions
    quadrant_functions_[0] =
        [&]{
        sq_step_funcs_mx_y0_[(points_[mx_][y0_] != 0.0f)](); // Top
        sq_step_funcs_mx_y1_[(points_[mx_][y1_] != 0.0f)](); // Bottom
        sq_step_funcs_x1_my_[(points_[x1_][my_] != 0.0f)](); // Right
        sq_step_funcs_x0_my_[(points_[x0_][my_] != 0.0f)](); // Left
    };
    quadrant_functions_[1] =
        [&]{
        sq_step_funcs_mx_y0_[(points_[mx_][y0_] != 0.0f)](); // Top
        sq_step_funcs_mx_y1_[(points_[mx_][y1_] != 0.0f)](); // Bottom
        sq_step_funcs_x1_my_[(points_[x1_][my_] != 0.0f)](); // Right
    };
    quadrant_functions_[2] =
        [&]{
        sq_step_funcs_mx_y1_[(points_[mx_][y1_] != 0.0f)](); // Bottom
        sq_step_funcs_x1_my_[(points_[x1_][my_] != 0.0f)](); // Right
        sq_step_funcs_x0_my_[(points_[x0_][my_] != 0.0f)](); // Left
    };
    quadrant_functions_[3] =
        [&]{
        sq_step_funcs_mx_y1_[(points_[mx_][y1_] != 0.0f)](); // Bottom
        sq_step_funcs_x0_my_[(points_[x0_][my_] != 0.0f)](); // Left
    };
}
void TerrainChunkGenerator::Generate(){
    time_t current_time;
    time(&current_time);
    srand((int)(current_time));
    GenPoints();
    mesh_ = new float[3 * num_vertices_];

    [... Stitch together mesh ...]

    points_.clear();

    chunk_ = new TerrainChunk{ num_vertices_, mesh_ };

}
TerrainChunk* TerrainChunkGenerator::chunk(){
    return chunk_;
}

// Private
void TerrainChunkGenerator::GenPoints(){

    // Starting corners
    points_[0.0f][0.0f] = 0.0f;
    points_[0.0f][length_] = 0.0f;
    points_[width_][0.0f] = 0.0f;
    points_[width_][length_] = 0.0f;

    h_ = 1.05f; // Rougness

    [...Measure Time Change...]
    Recurse(0U, 0U, 0U, 0U, width_, length_);
    [...Measure Time Change...]
}
void TerrainChunkGenerator::Recurse(unsigned count, unsigned quad, float x0, float y0, float x1, float y1){
    if (count == lod_) return;

    // need local variant b/c the globals will be overwritten b4 used in the recurse down below.
    float mx, my;
    mx_ = mx = (x1 + x0) / 2.0f;
    my_ = my = (y1 + y0) / 2.0f;

    // used in the quadrant_function lambdas
    x0_ = x0;
    x1_ = x1;
    y0_ = y0;
    y1_ = y1;

    divisor_ = powf(h_ * 2.0f, count);

    // Diamond step
    avg_d_ = points_[x0][y0] + points_[x0][y1] + points_[x1][y0] + points_[x1][y1];
    avg_d_ /= 4.0f;
    points_[mx][my] = avg_d_ + (Random() / divisor_); // Middle Middle

    // THIS STEP IS OF INTEREST TO ME
    // instead of using a switch statement I use an array of funcs that 
    // do an operation that is specific to that quadrant
    // Square step
    quadrant_functions_[quad]();

    count++;
    // Recurse for each quadrant
    Recurse(count, 0u, x0, y0, mx, my);    // Top Left Square
    Recurse(count, 1u, mx, y0, x1, my);   // Top Right Square
    Recurse(count, 2u, mx, my, x1, y1);  // Bottom Right Square
    Recurse(count, 3u, x0, my, mx, y1); // Bottom Left Square

}

float TerrainChunkGenerator::Random(){
    return 32.0f * ((float)(rand()) / RAND_MAX) - 16.0f;
}
\$\endgroup\$
1
  • \$\begingroup\$ Added an addendum with some more info that might help you in my answer. \$\endgroup\$
    – Emily L.
    Commented Jan 26, 2015 at 16:53

1 Answer 1

6
\$\begingroup\$

What you are doing is called a Branch (Jump) Table

It is a well known technique for avoiding costly branching instructions when one wants to execute a block of code depending on the value of one variable. Most respectable compilers will compile a dense switch on a integer argument into a jump table if some conditions are met and it will also add a guard before the jump table to catch the default block and avoiding jumping and executing random data.

Your method of doing it manually saves the execution time of the guard (which is a branch) to check if the argument is in range. For example if quad in

quadrant_functions_[quad]();

is >3 you will get undefined behavior while the switch approach with a default statement would just execute the default block. You know internally this can't happen so it's OK and slightly faster.

If speed is the name of the game, then I find your approach acceptable provided that it's documented.

You may also be interested in Lookup Tables (LUT).

Addendum

Modern desktop CPUs will try to predict which branch is going to be taken by some unspecified method, and will typically speculatively execute along that path (some may execute along both paths). If at a later point it turns out that the actual branch taken was a different one the CPU will "rewind" to the branch point and start over on the right track.

A branch instruction can be very costly if it is consecutively miss predicted causing the CPU to have to drop any issued instructions effectively breaking the highly efficient pipe-lining going on which is the key to obtaining high Instructions Per Cycle (IPC). However a branch that is easily predicted (i.e. almost always true, or almost always false) will have a small overhead as the prediction will likely be correct and execution continues.

Interesting case in point: Why is processing a sorted array faster than an unsorted array?

Of course, avoiding the branch all together saves an instruction or two on top, see predicated instructions. For example cmov: Why is a conditional move not vulnerable for Branch Prediction Failure?.

\$\endgroup\$
3
  • \$\begingroup\$ How could a lookup table be applied here? \$\endgroup\$ Commented Jan 26, 2015 at 16:37
  • \$\begingroup\$ I just added the link as "additional reading", I didn't look close enough at your code to see where and if it can be applied. :) \$\endgroup\$
    – Emily L.
    Commented Jan 26, 2015 at 16:38
  • \$\begingroup\$ Haha, ok then :) \$\endgroup\$ Commented Jan 26, 2015 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.