Optimize if-statement (a > 0 && b > 0 && a + b == c) in C#

Question

I'm currently doing some graph calculations that involves adjacency matrices, and I'm in the process of optimizing every little bit of it.

One of the instructions that I think can be optimized is the one in the title, in it's original form:

if ((adjMatrix[i][k] > 0) && (adjMatrix[k][j] > 0) && (adjMatrix[i][k] + adjMatrix[k][j] == w))

But for ease I'll stick to the form provided in the title:

if (a > 0 && b > 0 && a + b == c)

What I don't like is the > 0 part (being an adjacency matrix, in it's initial form it contains only 0 and 1, but as the program progresses, zeros are replaced with numbers from 2 onwards, until there are no more zeros.

I've done a test and removed the > 0 part for both a and b, and there was a significant improvement. Over 60088 iterations there was a decrease of 792ms, from 3672ms to 2880ms, which is 78% of the original time, which to me is excellent.

So my question is: can you think of some way of optimizing a statement like this and having the same result, in C#? Maybe some bitwise operations or something similar, I'm not quite familiar with them.

Answer with every idea that crosses your mind, even if it's not suitable. I'll do the speed testing myself and let you know of the results.

EDIT: This is for a compiler that I'm gonna run it myself on my computer. What I just described it's not a problem / bottleneck that I'm complaining of. The program in it's current form runs fine for my needs, but I just want to push it forward and make it as basic and optimized as possible. Hope this clarifies a little bit.

EDIT I believe providing the full code it's a useful thing, so here it is, but keep in mind what I said in the bold below. I want to concentrate strictly on the if statement. The program essentially takes an adjacency matrix and stores all the route combinations that exists. Then there are sorted and trimmed according to some coefficients, but this I didn't included.

int w, i, j, li, k;
int[][] adjMatrix = Data.AdjacencyMatrix;
List<List<List<int[]>>> output = new List<List<List<int[]>>>(c);

for (w = 2; w <= 5; w++)
{
    int[] plan;

    for (i = 0; i < c; i++)
    {
        for (j = 0; j < c; j++)
        {
            if (j == i) continue;
            if (adjMatrix[i][j] == 0)
            {
                for (k = 0; k < c; k++) // 11.7%
                {
                    if (
                        adjMatrix[i][k] > 0 && 
                        adjMatrix[k][j] > 0 && 
                        adjMatrix[i][k] + adjMatrix[k][j] == w) // 26.4%
                    {
                        adjMatrix[i][j] = w;

                        foreach (int[] first in output[i][k])
                            foreach (int[] second in output[k][j]) // 33.9%
                            {
                                plan = new int[w - 1];
                                li = 0;

                                foreach (int l in first) plan[li++] = l;
                                plan[li++] = k;
                                foreach (int l in second) plan[li++] = l;

                                output[i][j].Add(plan);
                            }
                    }
                }

                // Here the sorting and trimming occurs, but for the sake of
                // discussion, this is only a simple IEnumerable<T>.Take()
                if (adjMatrix[i][j] == w)
                    output[i][j] = output[i][j].Take(10).ToList();
            }
        }
    }
}

Added comments with profiler results in optimized build.

By the way, the timing results were obtained with exactly this piece of code (without the sorting and trimming which dramatically increases execution time). There weren't another parts that were included in my measurement. There is a Stopwatch.StartNew() exactly before this code, and a Console.WriteLine(EllapsedMilliseconds) just after.

If you want to make an idea about the size, the adjacency matrix has 406 rows / columns. So basically there are only for-instructions combined which execute many many iterations, so I haven't got many options of optimizing. Speed is not currently a problem, but I want to make sure I'm ready when it'll become.

And to rule out the 'optimize another parts' problem, there is room for talk in this subject also, but for this specific matter, I just want to find solution for this as an abstract problem / concept. It may help me and others understand how the C# compiler works and treats if-statements and comparisons, that's my goal here.

Answer 1

You can replace a>0 && b>0 with (a-1)|(b-1) >= 0 for signed variables a and b.

Likewise, the condition x == w can be expressed as (x - w)|(w - x) >= 0, since when x != w either left or the right part of the expression will toggle the sign bit, which is preserved by bit-wise or. Everything put together would be (a-1)|(b-1)|(a+b-w)|(w-a-b) >= 0 expressed as a single comparison.

Alternatively a slight speed advantage may come from putting the probabilities in increasing order:

Which is more likely (a|b)>=0 or (a+b)==w ?

Answer 2

I don't know how well C# optimizes things like this, but it's not so difficult to try to store adjMatrix[i][k] and adjMatrix[k][j] in temporary variables not to read memory twice. See if that changes things in any way.

It's hard to believe that arithmetic and comparison operations are the bottleneck here. Most likely it's memory access or branching. Ideally memory should be accessed in a linear fashion. Can you do something to make it more linear?

It would be good to see more code to suggest something more concrete.

Update: You could try to use two-dimensional array (int[,]) instead of a jagged one (int[][]). This might improve memory locality and element access speed.