Optimize a function in a search biggest square algorithm

Question

I'm kind of new to optimization and I'm in a friendly contest to code the fastest algorithm to find a square in a field with obstacles. I think my algorithm is pretty fast (2.07s in a 10k * 10k grid with 70% density) but I'd like to make it faster. My most used function is the one finding the max size for given coordinates in the square. Here it is :

int     max_size(int i, int j, int **tab, int offset)
{
int a;

a = offset;
if (i > 0 && j > 0)
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] - tab[i + a][j - 1] - tab[i - 1][j + a] + tab[i - 1][j - 1] == 0)
        a++;
    return (a);
}
else if (i > 0 && j == 0)
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] - tab[i - 1][j + a] == 0)
        a++;
    return (a);
}
else if (i == 0 && j > 0)
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] - tab[i + a][j - 1] == 0)
        a++;
    return (a);
}
else
{
    while (i + a < g_ymax && j + a < g_xmax && tab[i + a][j + a] == 0)
        a++;
    return (a);
}
}

So this is very ugly and I'd like to optimize it. Would make it an inline function help or not at all ? I tried to run some tests but I didn't see much differences.

Answer 1

First of all, it doesn't make much sense to speak of performance or manual optimizations without a specific system in mind. Generally, in order to optimize better than the compiler for that system, you have to be an expert of that particular system.

But lets assume this is some mainstream high-end system like x86, PowerPC or ARM. What then matters most for performance by far, is how the grid is stored in memory.

You have int **tab and treat it as a 2D array, which is code smell. This most likely means that tab points at some pointer-based look-up table, probably allocated on the heap. Accessing such a look-up table will give significant performance loss on a system with data cache memory, since the segmentation of the data will block efficient data cache utilization. See Correctly allocating multi-dimensional arrays for advice how to radically improve performance in this regard.

Once you have moved the grid to contiguous memory, the next step is to ensure that you iterate over it in such a manner that the right-most dimension is the one changing the most frequently. That is, given array[i][j], make sure to iterate so that j is the iterator that changes most frequently. This is also related to cache memory use and possibly alignment as well.

You can gain a minor performance boost by reducing the number of comparisons, by for example using a truth table. The fewer comparisons, the better the branch prediction.

Inlining the function might indeed give a slight performance gain, though the compiler should be able to make a better decision there, as inlining comes at the expense of executable size and perhaps also memory use.

If 10k*10k is max, then a minor performance gain could be achieved by swapping int for uint_fast16_t, although that's mostly an optimization for 8 and 16 bit CPUs.

Answer 2

I am not sure about this, it might help compiler to keep those two values in registers:

int max_size(int i, int j, int **tab, int offset)
{
   int a;
   const int ymax = g_ymax;
   const int xmax = g_xmax;

   // Use ymax and xmax in the rest of code.

If g_ymax and g_xmax are constants like:

   static const int g_xmax = 1234;

then this won't help.

Answer 3

Use local variables in your function to simplify the conditions in your while loops. For example your first loop could be simplified as:

int   Limit;
int * C1=tab[i-1];
int   C2=C1[j - 1];

if (g_ymax-i < g_xmax-j)
{
  Limit = g_ymax-i;
}
else
{
  Limit = g_xmax-j;
}

while ((a < Limit) && (tab[i + a][j + a] - tab[i + a][j - 1] - C1[j + a] + C2 == 0) )
{
  a++;
}

return (a);

De-referencing a pointer also consumes clock cycles. That's why I've used C1, and C2 when the index of the array is constant.

Answer 4

we compare 'for(;;)' and 'while(1)', I read the corresponding assembly language codes:

'for(;;)', its assembly language doesn't have judgement sentence.

'while(1)', its assembly language has one judgement, to judge 1 is need to continue looping.