[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:

Outro dia, tive o prazer de trocar ideias com um pessoal super interessante sobre microsserviços. Esse bate-papo ficou registrado em...
Frequentemente precisamos fazer referência para outros documentos e isso é natural. Entretanto, há cenários onde o documento que queremos referenciar...
The example which motivated this post comes from the excellent book Designing Distributed Systems by Brendan Burns (co-founder of the...
No post anterior, eu mencionei uma série de post do Mario Fusco questionando a forma como desenvolvedores Java estão implementando os design...
Entropia é um conceito oriundo da física que trata da quantidade de “desordem” em um sistema. As leis da termodinâmica...
In a previous post, I wrote about how to support sagas using a Workflow Engine as Saga Execution Coordinator (if...