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

Question

I am currently doing some graph calculations that include adjacency matrices, and I'm in the process of optimizing each of its counts.

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

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

But for convenience, I will stick to the form indicated in the title:

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

What I don't like is the> 0 part (which is an adjacency matrix, in it the original form contains only 0 and 1, but as the program advances, zeros are replaced by numbers from 2 to until there are no more zeros.

I ran a test and removed part> 0 for a and b, and there was a significant improvement. Over 60,088 iterations had a decrease of 792 ms , from 3,672 m to 2,880 ms, which is 78% of the initial time, which is excellent for me.

So my question is: can you think of some way to optimize such a statement and have the same result in C #? Perhaps some bitwise operations or something similar, I am not completely familiar with them.

Respond to every idea that crosses your mind, even if it does not fit. I myself will conduct a speed test and let you know about the results.

EDIT: It is for the compiler that I am going to run it myself on my computer. What I just described is not the problem / bottleneck I'm complaining about. The program in this current form is great for my needs, but I just want to promote it and make it as simple and optimized as possible. Hope this clarifies a bit.

EDIT I think the full code is a useful thing, so here it is, but keep in mind what I said in the half-dinner below. I want to focus strictly on the if statement . The program essentially accepts an adjacency matrix and saves all route combinations that exist. Then they are sorted and trimmed according to some factors, but I did not include this.

 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(); } } } } 

Comments with profiling results in optimized assembly are added .

By the way, the synchronization results were obtained with this particular part of the code (without sorting and trimming, which significantly increases the execution time). There were no other parts in my measurements. Next to this code is Stopwatch.StartNew () and Console.WriteLine (EllapsedMilliseconds) immediately after.

If you want to imagine size, the adjacency matrix has 406 rows / columns. So basically there are only combined commands that do a lot of iterations, so I don't have many optimization options. Speed ​​is not a problem at present, but I want to make sure that I am ready when it becomes.

And to eliminate the problem of “optimizing another part”, there is an opportunity to talk with this subject, but for this specific question I just want to find a solution for this as an abstract problem / concept. This can help me and others understand how the C # compiler works and processes if-statements and comparisons, which is my goal here.

Answer 1

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

Similarly, the condition x == w can be expressed as (x - w)|(w - x) >= 0 , since for x != w either the sign bit will be switched to the left or the right side of the expression, which is saved by the battle or. All that was compiled would be (a-1)|(b-1)|(a+bw)|(wab) >= 0 , expressed as one comparison.

Alternatively, a small speed advantage may be related to probability in increasing order:

Most likely, (a|b)>=0 or (a+b)==w ?

Answer 2

I don’t know how well C # optimizes such things, but it’s not so difficult to try to keep adjMatrix[i][k] and adjMatrix[k][j] in temporary variables so as not to read the memory twice. See if this somehow makes a difference.

It is hard to believe that arithmetic and comparative operations are the bottleneck here. Most likely, this is access to memory or branching. Ideally, memory access should be linear. Can you do something to make it more linear?

It would be nice to see more code to offer something more specific.

Update: You can try using a two-dimensional array ( int[,] ) instead of a jagged array ( int[][] ). This can improve memory locality and element access speed.

Answer 3

The order of logic tests may be important (as indicated in other answers). Since you use the logical short circuit test (& & instead of &), then the conditions are evaluated from left to right, and the first, which it considers false, will cause the program to stop evaluating the conditional and continue execution (without executing the if block). Therefore, if there is one condition, it will be much more likely to be false than the rest, that you need to go first, and the next, most likely false , etc.

Another good optimization (I suspect that this is really what gave you an increase in performance - instead of just giving up some conditions) is to assign the values ​​you pull from arrays to local variables.

You use adjMatrix[i][k] twice (as well as adjMatrix[k][j] ), which causes the computer to dig an array to get the value. Instead, before the if statement, set each of them a local variable each time, then run your logic test against these variables.

Answer 4

I agree with others who say it is unlikely that this simple statement is your bottleneck and offers profiling before you decide to optimize this particular line. But, as a theoretical experiment, you can do several things:

• Zero checks: checking for a != 0 && b != 0 will probably be slightly faster than a >= 0 && b >= 0 . Since your adjacency matrix is ​​non-negative, you can safely do this.

• Reordering: if testing only a + b == c is faster, try using this test first and then check only a and b . I doubt it will be faster, because checking addition and equality is more expensive than zero, but this might work for your specific case.

• Avoid double indexing: look at the IL result using ILDASM or the equivalent to ensure that array indexes are dereferenced once rather than twice. If this is not the case, try putting them in local variables before checking.

Answer 5

If you do not call the function, you do not optimize the conventions. It's pointless. However, if you really want you to have a few simple things to keep in mind

Conditions are checked if something is equal to zero (or not), if the most significant bit is set (or not), and the comparison (== or! =) Is essentially ab and checks whether its zero (== 0) is equal to or not (! = 0). So a is unsigned, then a> 0 matches a! = 0. If a is signed, then <0 is pretty good (it uses the highest bit check), and better than a <= 0. But anyway just knowing these rules can help.

Also run the profiler, you will see that the conditional values ​​take 001% of the time. If anything, you should ask how to write something that does not require conventions.

Answer 6

Have you considered reversing logic?

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

can be rewritten to:

 if (a == 0 || b == 0 || a + b != c) continue; 

Since you do not want to do anything in the loop, if any of the statements is false, try aborting as soon as possible (if the runtime is so intelligent that I assume).

The operation, which is the most difficult, must be the last, because if the first statement is true, others do not need to be verified. I suggested that adding is the hardest part, but profiling may seem different.

However, I did not profile these scenarios myself with such trivial conventions; this may even be a drawback. It would be interesting to see your results.