CODEWITHSUNDEEP
c++performance
GilLevi
GilLevi

Reputation: 2137

C++ speed up map access

I defined the following map:

class xy_angle {
public:
    int x;
    int y;
    int angle;

    xy_angle(int x, int y, int angle) :x(x), y(y), angle(angle){};

};

class xy_angleComparator {
public:
    bool operator () (const xy_angle &a, const xy_angle &b) const {
        if (a.x != b.x)
            return a.x < b.x;
        else if (a.y != b.y)
            return a.y < b.y;
        else if (a.angle != b.angle)
            return a.angle < b.angle;
        else
            return false;
    }
};

std::map<xy_angle, std::pair<int, int>, xy_angleComparator> transformed_coordinates_lut_;

I fill it up when I initialize the class that contains it:

//creating LUTs
int half_patch_size=48;
for (int x_start = -half_patch_size; x_start <= half_patch_size; x_start++){
    for (int y_start = -half_patch_size; y_start <= half_patch_size; y_start++){
        for (int angle = -314; angle < 314; angle++){
            float angle_f = (float)angle / 100.f;
            double cos_theta = cos(angle_f);
            double sin_theta = sin(angle_f);

            int x_tranformed = (int)(((float)x_start)*cos_theta - ((float)y_start)*sin_theta);
            int y_tranformed = (int)(((float)x_start)*sin_theta + ((float)y_start)*cos_theta);

            if (x_tranformed > half_patch_size)
                x_tranformed = half_patch_size;

            if (x_tranformed < -half_patch_size)
                x_tranformed = -half_patch_size;

            if (y_tranformed > half_patch_size)
                y_tranformed = half_patch_size;

            if (y_tranformed < -half_patch_size)
                y_tranformed = -half_patch_size;

            transformed_coordinates_lut_[xy_angle(x_start, y_start, angle)] = std::pair<int, int>(x_tranformed, y_tranformed);
        }
    }
}

And I access it using the following code:

int ax2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].first;
int ay2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].second;

I measured the map's access running time using a large set of random keys and it's quite insane. It totally dominates the running time of the functions that uses it.

It there any way to speed it up?

Thanks!

Gil.

Upvotes: 2

Views: 353

Answers (2)

Barry
Barry

Reputation: 302817

Regardless of which container you use, this code is bad:

int ax2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].first;
int ay2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)].second;

You're doing the same lookup twice! Definitely cache the result:

auto& a2 = transformed_coordinates_lut_[xy_angle(ax, ay, theta)];
int ax2 = a2.first;
int ay2 = a2.second;

Now as far as speeding up the work goes. The least work up front would be just to sub out a different associative container type: 

using MapType = std::unordered_map<xy_angle,
                                   std::pair<int, int>,
                                   xy_angle_hash>; // implement this hash

That will give you O(1) lookup instead of the O(lg N) you are currently seeing in your code with std::map. But if you really want to spend a lot of time exploring this container, I'd suggest just wrapping it so you can control the implementation:

class TransformMap
{
public:
    std::pair<int, int>& operator()(const xy_angle& );

private:
    // is it std::map?
    // or std::unordered_map?
    // or 3D-array or vector or ... ?
};

Upvotes: 1

kraskevich
kraskevich

Reputation: 18556

You can use a 3-D array instead: f[x_start][y_start][angle]. It would occupy the same(or less) space because you have all possible keys anyway. Of course, you can also emulate a 3-D array with a flat vector using appropriate indices. This approach guarantees you constant time lookup.

Upvotes: 3

Related Questions