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

Our goal is to fill a two-dimensional array with 1’s.

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

Could you say which version is faster and why?

Compartilhe este insight:

6 respostas

  1. Yan Justino Vou arriscar 😀 Acredito que apesar dos dois algoritimos aparentemente terem a mesma complexidade (Θ(nˆ2)), a degradação do segundo é maior, uma vez que pra cada “i” eu preciso realizar uma operação Θ(n) no “j”, enquanto na primeira estratégia o custo é pago na primeira iteração de “i” e as demais eu tenho um custo de Θ(1) para a sua leitura.

  2. Nice question, indeed.

    I didn’t run the code (yet), but probably the JxI method is slower.

    It has to do with memory layout and how the 10000^2 allocations will be performed, it can goes basically two ways… like:

    [0, 1]
    [0, 2]
    [0, 3]
    [0, …]

    or:

    [1, 0]
    [2, 0]
    [3, 0]
    […, 0]

    Depending on how memory is allocated by the runtime one of the two methods will be slower.

    The fastest one will basically reads memory addresses ‘sequentially’ and the other will ‘jump’ 10000 addresses on each iteration.

    The fastest one will have addresses nearby, the slower will not. The problem is not with the ‘jump’ per se, since accessing an array by its index is usually O(1).

    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).

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:

Há pouco menos de um ano, aceitei o desafio de liderar o time de tecnologia e estratégia de negócios da...
Ontem, dia 25/07/2018, a convite do Canal.NET, compartilhei alguns insights sobre modelagem de microsserviços a partir de processos de negócio....
If you ask me one tip to improve the performance of your applications, it would be: Design your objects to...
O ano era 2001 ou 2002. Não lembro ao certo. Eu era um jovem programador, pai recente, tentando “encontrar meu...
Este é o primeiro post de uma série onde pretendo compartilhar, com considerável nível de detalhe, como resolver problemas de...
No post anterior, eu mencionei uma série de post do Mario Fusco questionando a forma como desenvolvedores Java estão implementando os design...