CPU-efficient method of checking if array position is null in C++

Question

A program I've written needs to check millions of points in a 2D array to see if they are not null. Here is the code I am using:

Particle *particleGrid[1920][1080];
bool Sensor::checkForParticle(int x, int y) {
    if (x > 1920 || x < 0) return 0;
    if (y > 1080 || y < 0) return 0;
    if (mainController->particleGrid[x][y] != NULL) {
        return 1;
    }
    return 0;
}

This function uses the most CPU in the entire application (~70% of the application's CPU usage is due to this function), even more than my implementation of the Bresenham line drawing algorithm (the example function is called on every point of the line generated by the Bresenham algorithm). Is there a more CPU-efficient way to perform the null-checking operation?

(~70% of the application's CPU usage is due to this function). How do you know that? — Sarfaraz Nawaz
– Sarfaraz Nawaz, Commented Dec 23, 2013 at 15:50
This question might be better suited for codereview. Anyways, is there a reaason why your x/y are signed? one unsgined comparison instead of two signed seems cheaper. — PlasmaHH
– PlasmaHH, Commented Dec 23, 2013 at 15:52
If it is inside a loop is the loop what is taking that much time. Have you considered to inline this? — Pedrom
– Pedrom, Commented Dec 23, 2013 at 15:53
beside any performance improvements in answers/other comments... are you sure you need to check every point on the line? if both start point and end point of a straight line are within your bounds then so are all the points in between. Unless most of your lines are outside the bounds you could save most of your processing by first checking the initial and end point only — msam
– msam, Commented Dec 23, 2013 at 16:05

SmacL · Accepted Answer · 2013-12-23 15:51:47Z

2

If it is called in a loop, you could get away without checking the arguments. It will also be faster row first as you're examining data close in memory location which will reduce cache hits.

answered Dec 23, 2013 at 15:51

SmacL

23k15 gold badges105 silver badges153 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

fredoverflow · Accepted Answer · 2013-12-23 16:04:53Z

If you compare against unsigned literals, you get the check against 0 for free, because negative numbers end up very large when converted to unsigned. Also, you don't need all those ifs:

bool Sensor::checkForParticle(int x, int y)
{
    return (x < 1920u) && (y < 1080u)   // note both "u" suffixes for unsigned
        && (mainController->particleGrid[x][y] != NULL);
}

By the way, why do you have your array in column-major order? Are your outer loops on x or y? If they are on y, switching to row-major will dramatically improve the efficiency due to cache-friendliness:

Particle *particleGrid[1080][1920];

bool Sensor::checkForParticle(int x, int y)
{
    return (x < 1920u) && (y < 1080u)
        && (mainController->particleGrid[y][x] != NULL);   // note switched order
}

Zac Howland · Accepted Answer · 2013-12-23 16:09:19Z

If the 2D array is sparse, something like this could help you speed up a tight loop:

Particle *particleGrid[1920][1080];

// somewhere before your tight loop
std::map<std::pair<unsigned int, unsigned int>, Particle*> createCache()
{
    std::map<std::pair<unsigned int, unsigned int>, Particle*> cache;
    for (unsigned int i = 0; i < 1920; ++i)
    {
        for (unsigned int j = 0; j < 1080; ++j)
        {
            if (mainController->particleGrid[i][j])
            {
                std::pair<unsigned int, unsigned int> coord = std::make_pair(i, j);
                cache[coord] = mainController->particleGrid[i][j];
            }
        }
    }
    return cache;
}

// then this is called in your tight loop
bool Sensor::checkForParticle(unsigned int x, unsigned int y, const std::map<std::pair<unsigned int, unsigned int>, Particle*>& cache) 
{
    std::pair<unsigned int, unsigned int> coord = std::make_pair(x, y);
    return cache.find(coord) != map.end();
}

If it is not sparse, this will not help at all.

Dietmar Kühl · Accepted Answer · 2013-12-23 16:14:44Z

0

Step 1: hoist the consistency check out of the loop:

bool Sensor::uncheckedCheckForParticle(int x, int y) {
    return mainController->particleGrid[y][x];
}

If you really need to guard against sloppy programming, you could assert() in the function and/or guard the call site. I'd bet that this will dramatically improve performance.

Step 2: make the now trivial function inline.

answered Dec 23, 2013 at 16:14

Dietmar Kühl

155k18 gold badges238 silver badges395 bronze badges

Comments

Casey · Accepted Answer · 2013-12-23 16:28:46Z

0

You could flatten the array from two-dimensional to one-dimensional (sadly, this may require refactoring elsewhere in the code though) :

Particle *particleGrid[1920 * 1080];
bool Sensor::checkForParticle(int x, int y) {
    return (mainController->particleGrid[x * 1080 + y] != NULL)
}

answered Dec 23, 2013 at 16:28

Casey

11k11 gold badges64 silver badges95 bronze badges

Collectives™ on Stack Overflow

CPU-efficient method of checking if array position is null in C++

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related