[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 um comentário

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:

I believe that, from time to time, it is interesting to learn a new language or framework that takes us...
Aprendemos que a priorização das atividades deve ser feita, invariavelmente, pelo time do negócio. Na prática, entretanto, em nosso time,...
Compete ao arquiteto corporativo a responsabilidade de descrever, analisar e comunicar os diversos aspectos da arquitetura corporativa, bem como registrar...
Aqui, um registro da apresentação que realizei na abertura do IoT Weekend. O que você acha do que foi dito?
As an experienced .NET developer, you have to deal with NullReferenceException occurrences every day. Am I right? I firmly believe...
Este é o primeiro post da série em que vou compartilhar algum conhecimento sobre como desenvolver uma aplicação de verdade...
× Precisa de ajuda?