Jump to content
  • Advertisement
Sign in to follow this  
data2

Code that needs to be optimized

This topic is 3895 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi there, First some introductory words: I'm writing a graphics related application that works on 2D images. An image needs to be tiled (i.e. repeated in an infinite plane) or mirrored (i.e. repeated in a way that every odd tile is flipped in x and y respectively). I've an image class that can take any coordinate (also outside the image's dimensions and negative). To access a pixel, the coordinate is "brought back" to the corresponding coordinate (depending on the tiling or mirroring). This "bringing back" code gets executed millions of times and is the bottle neck of the application. Since the running time takes up to half an hour I try to optimize my code. Below you find my current implementation. My question is whether it is possible to optimize this code (I don't know how) or to compute the coordinates in a different -- more efficient -- way. Many thanks and Cheers, Data
/// A simple 2D point
class Point2D {
    int X, Y;
};

/// The image class
class Image2D {
    /// some stuff, like member variables and so on

    Point2D Tile(const Point2D& coord) const
    {
        int x = coord.X % (int)m_width;
        int y = coord.Y % (int)m_height;
        if(x < 0)
        {
            x += m_width;
        }
        if(y < 0)
        {
            y += m_height;
        }

        return Point2D(x, y);
    };

    Point2D Mirror(const Point2D& coord) const
    {
        Point2D result = Tile(coord);

        // handle negative coordinates 
        if(coord.X < 0)
        {
            int x = -coord.X - 1;    // note that negative coords do not start with 0

            // even tiles are flipped
            if(((x / m_width) % 2) == 0)
            {
                result.X = m_width - result.X - 1;
            }
        }
        // odd tiles are flipped
        else if(((coord.X / m_width) % 2) != 0)
        {
            result.X = m_width - result.X - 1;
        }


        // handle negative coordinates 
        if(coord.Y < 0)
        {
            int y = -coord.Y - 1;    // note that negative coords do not start with 0

            // even tiles are flipped
            if(((y / m_height) % 2) == 0)
            {
                result.Y = m_height - result.Y - 1;
            }
        }
        // odd tiles are flipped
        else if(((coord.Y / m_height) % 2) != 0)
        {
            result.Y = m_height - result.Y - 1;
        }

        return result;
    };

};

Share this post


Link to post
Share on other sites
Advertisement
For the "tile" option all you need to do is a simple modulus. The conditionals aren't needed - modulus should have well-defined behaviour for negative numbers. All that should be needed is:

return Point2D(coord.x % m_width, y % m_height);

If m_width and m_height are floats, consider storing them as integers instead. Float to integer conversions are computationally expensive. Also, you may want to consider avoiding returning large data types - I usually don't return anything larger than 4 bytes. But in this case it should be fine (8 bytes).

Although I'm not sure how to do mirror mode.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sc4Freak
For the "tile" option all you need to do is a simple modulus. The conditionals aren't needed - modulus should have well-defined behaviour for negative numbers. All that should be needed is:

return Point2D(coord.x % m_width, y % m_height);


I tried it out and actually the result of a modulus is negative if the left hand side is negative. So I still need the if statements...

Share this post


Link to post
Share on other sites
Quote:
Original post by data2
Quote:
Original post by Sc4Freak
For the "tile" option all you need to do is a simple modulus. The conditionals aren't needed - modulus should have well-defined behaviour for negative numbers. All that should be needed is:

return Point2D(coord.x % m_width, y % m_height);


I tried it out and actually the result of a modulus is negative if the left hand side is negative. So I still need the if statements...

Yes you're absolutely right they can't just be left out, or you still get negative values.

You have a few float to int conversions in there by the looks of it. I suggest adding extra member variables m_intHeight, and m_intWidth which hold the height and width pre-converted to integers. That should speed it up a lot, assuming they are floats or doubles.
Then, by expanding the definition of Tile into Mirror, we are able to take advantage of the fact that coord.X in Mirror is only negative when x in Tile is negative (same for coord.Y and y). This finally does remove those if statements.
Next we replace % 2 with & 1, in case we are using a braindead compiler here.
I've then grouped all the X and Y calculations together.
This brings me to the below code. Note that you might not need 'Tile' any more if it isn't used elsewhere. There is certainly more that can be done though. If the height and/or width is always power of two then it can be sped up much more.
    Point2D Tile(const Point2D& coord) const
{
int x = coord.X % m_intWidth;
int y = coord.Y % m_intHeight;
if(x < 0)
{
x += m_intWidth;
}
if(y < 0)
{
y += m_intHeight;
}

return Point2D(x, y);
};

Point2D Mirror(const Point2D& coord) const
{
Point2D result;

result.X = coord.X % m_intWidth;
// handle negative coordinates
if (coord.X < 0)
{
result.X += m_intWidth;
int x = -coord.X - 1; // note that negative coords do not start with 0

// even tiles are flipped
if (((x / m_intWidth) & 1) == 0)
{
result.X = m_intWidth - result.X - 1;
}
}
// odd tiles are flipped
else if ((coord.X / m_intWidth) & 1)
{
result.X = m_intWidth - result.X - 1;
}

result.Y = coord.Y % m_intHeight;
// handle negative coordinates
if (coord.Y < 0)
{
result.Y += m_intHeight;
int y = -coord.Y - 1; // note that negative coords do not start with 0

// even tiles are flipped
if (((y / m_intHeight) & 1) == 0)
{
result.Y = m_intHeight - result.Y - 1;
}
}
// odd tiles are flipped
else if ((coord.Y / m_intHeight) & 1)
{
result.Y = m_intHeight - result.Y - 1;
}

return result;
};




[Edited by - iMalc on November 21, 2007 12:15:20 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
I've then grouped all the X and Y calculations together.
*** Source Snippet Removed ***


You're better off not doing that. Leave result.Y = coord.Y % m_intHeight; at the start of the function and let the compiler schedule the divide early, before you need the result for the Y-half of the function. The memory moves for result.Y also give you some space between the time result.X is first calculated and the time it is needed.

Share this post


Link to post
Share on other sites
Might I suggest providing a line iterator? It's much shorter to compute the "next pixel to the right" given the current pixel, than it is to compute the "texture-space coordinates of pixel x+1", so looping over the pixels in a give line by extracting the iterator to that line's start, and the incrementing it to traverse all pixel addresses should provide an increase in performance.

Also, note that mirroring an image can be resolved simply by creating an image twice as large and manually mirroring the relevant parts.

Share this post


Link to post
Share on other sites
Actually, looking over your code again, I'm thinking now that m_height and m_width are already integers. Those (int) casts are just there to fool us right?

Share this post


Link to post
Share on other sites
If you enforce power of 2 textures, you could use:

return Point2D(coord.x & (m_Width - 1), coord.y & (m_Height - 1));

for tiling.

Share this post


Link to post
Share on other sites
Thanks for all the replies and suggestions.

(1) m_width and m_height are unsigned int. That's why there are casts
(2) The image is not necessarily pow2, even though often the case (I might think of introducing special routines for pow2 images -- any suggestions of how to optimize Mirror() in case of pow2 textures?)
(3) I need to access pixels very randomly and do not really iterate over them. So an iterator wouldn't be of much help. However, I introduced direct access to the raw data and can loop over the memory with pointers if I have to.

@iMalc The idea of moving the Tile function's calculations into Mirror looks quite nice. It is not that much code, so I don't really need to call an extra function.

@outRider What is that with the compiler optimizations? I never think of how the compiler optimizes code, so I'm curious...

Cheers,
data

[Edited by - data2 on November 21, 2007 3:50:11 PM]

Share this post


Link to post
Share on other sites
I'm thinking that maybe you should mirror the entire texture, and save the mirrored texture? then mirroring reduces to a modulus as well.

Sometimes it is not the algorithm that needs to be optimized, but the design. Are you sure you need to do this millions of times?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!