[ANSWER] Which version of this function is faster? Why?

In the previous post, I asked which function, in the following code, would fill the array with 1’s faster and the reason for that.

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace ToArrays
{
    public class Program
    {
        public const int Size = 10000;

        private static void Main()
        {
            BenchmarkRunner.Run<Program>();
        }

        [Benchmark]
        public void IxJ()
        {
            var array = new int[Size, Size];
            for (var i = 0; i < Size; i++)
            {
                for (var j = 0; j < Size; j++)
                {
                    array[i, j] = 1;
                }
            }
        }

        [Benchmark]
        public void JxI()
        {
            var array = new int[Size, Size];
            for (var i = 0; i < Size; i++)
            {
                for (var j = 0; j < Size; j++)
                {
                    array[j, i] = 1;
                }
            }
        }
    }
}

In this post, I will answer these questions.

Which one is faster?

The algorithm complexities for both functions are the same. But the execution times are different.

Here is the output produced by BenchmarkDotNet on my machine:

/ * Summary *

BenchmarkDotNet=v0.11.3, OS=Windows 10.0.17134.407 (1803/April2018Update/Redstone4)
Intel Core i7-8550U CPU 1.80GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
Frequency=1945312 Hz, Resolution=514.0564 ns, Timer=TSC
.NET Core SDK=2.1.403
  [Host]     : .NET Core 2.1.5 (CoreCLR 4.6.26919.02, CoreFX 4.6.26919.02), 64bit RyuJIT
  DefaultJob : .NET Core 2.1.5 (CoreCLR 4.6.26919.02, CoreFX 4.6.26919.02), 64bit RyuJIT


 Method |       Mean |     Error |    StdDev |     Median |
------- |-----------:|----------:|----------:|-----------:|
    IxJ |   472.8 ms |  9.543 ms |  23.41 ms |   476.8 ms |
    JxI | 1,619.6 ms | 88.361 ms | 253.53 ms | 1,723.1 ms |

As you can see, “IxJ” is ~4x faster than “JxI”

Why?

Cleber Dantas nailed it in the comments of the last post.

The real problem is CPU cache; the slower method will perform a lot of cache misses, forcing the CPU to access RAM (which is slower than cache).

Learned lesson

Whenever it is possible, access memory sequentially.

Compartilhe este insight:

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Elemar Júnior

Sou fundador e CEO da EximiaCo e atuo como tech trusted advisor ajudando diversas empresas a gerar mais resultados através da tecnologia.

Mais insights para o seu negócio

Veja mais alguns estudos e reflexões que podem gerar alguns insights para o seu negócio:

C++ é uma linguagem de programação velha, charmosa para os iniciados, assustadora para aqueles que conhecem pouco dela. Bjarne Stroustrup desenvolveu...
Nunca trabalhei em um circo, tampouco criei elefantes! Portanto, advirto que os “fatos” que lerá aqui foram relatados por amigos,...
Uma das vantagens de estudar diversas linguagens, frameworks, técnicas e prática é encontrar inspiração inusitada para nosso código. Nesse post...
If you need to improve the performance of .NET applications, then at some point you will need to understand how...
Um de nossos objetivos, nesse momento, é  melhorar a comunicação, compartilhando a visão do nosso fluxo de trabalho com a...
Last post, I asked an explanation about the execution result of the following code. using System; using System.Threading.Tasks; using static...