Cache friendly and faster way faster - `InvokeMe()`

Question

I am trying to figure out, if this really is the fastest approach. I want this to be as fast as possible, cache friendly, and serve a good time complexity.

DEMO: https://dotnetfiddle.net/BUGz8s

private static void InvokeMe() 
{
    int hz = horizontal.GetLength(0) * horizontal.GetLength(1);
    int vr = vertical.GetLength(0) * vertical.GetLength(1);
    int hzcol = horizontal.GetLength(1);
    int vrcol = vertical.GetLength(1);
    
    //Determine true from Horizontal information:
    for (int i = 0; i < hz; i++)
    {
        if(horizontal[i / hzcol, i % hzcol] == true)
           System.Console.WriteLine("True, on position: {0},{1}", i / hzcol, i % hzcol);
    }

    //Determine true position from vertical information:
    for (int i = 0; i < vr; i++)
    {
        if(vertical[i / vrcol, i % vrcol] == true)
           System.Console.WriteLine("True, on position: {0},{1}", i / vrcol, i % vrcol);
    }
}

Pages I read:

• Is there a "faster" way to iterate through a two-dimensional array than using nested for loops?
• Fastest way to loop through a 2d array?
• Time Complexity of a nested for loop that parses a matrix
• Determining the big-O runtimes of these different loops?

---

EDIT: The code example, is now, more towards what I am dealing with. It's about determining a true point x,y from a N*N Grid. The information available at disposal is: horizontal and vertical 2D arrays.

To NOT cause confusion. Imagine, that overtime, some positions in vertical or horizontal get set to True. This works currently perfectly well. All I am in for, is, the current approach of using one for-loop per 2D array like this, instead of using two for loops per 2D array.

Answer 1

Did you consider

for (int i = 0; i < row; i++)
{
    for (int j = 0; j < col; j++)
    {
        Console.Write(string.Format("{0:00} ", matrix[i, j]));
        Console.Write(Environment.NewLine + Environment.NewLine);
    }
}

It is basically the same loop as yours, but without / and % that compiler may or may not optimize.

Answer 2

Time complexity for approach with one loop and nested loops is the same - O(row * col) (which is O(n^2) for row == col as in your example for both cases) so the difference in the execution time will come from the constants for operations (since the direction of traversing should be the same). You can use BenchmarkDotNet to measure those. Next benchmark:

[SimpleJob]
public class Loops
{
    int[, ] matrix = new int[10, 10];
    [Benchmark]
    public void NestedLoops()
    {
        int row = matrix.GetLength(0);
        int col = matrix.GetLength(1);
        for (int i = 0; i < row ; i++)
        for (int j = 0; j < col ; j++)
        {
            matrix[i, j] = i * row + j + 1;
        }
    }
    
    [Benchmark]
    public void SingleLoop()
    {
        int row = matrix.GetLength(0);
        int col = matrix.GetLength(1);
        var l = row * col; 
        for (int i = 0; i < l; i++)
        {
            matrix[i / col, i % col] = i + 1;
        }
    }
}

Gives on my machine:

Method	Mean	Error	StdDev	Median
NestedLoops	144.5 ns	2.94 ns	4.58 ns	144.7 ns
SingleLoop	578.2 ns	11.37 ns	25.42 ns	568.6 ns

Making single loop actually slower.

If you will change loop body to some "dummy" operation - for example incrementing some outer variable or updating fixed (for example first) element of the martix you will see that performance of both loops is roughly the same.