Aumento de desempenho estranho em benchmark simples

97

Ontem encontrei um artigo de Christoph Nahr intitulado ".NET Struct Performance" que comparou várias linguagens (C ++, C #, Java, JavaScript) para um método que adiciona duas estruturas de pontos ( doubletuplas).

Como se viu, a versão C ++ leva cerca de 1000 ms para executar (iterações 1e9), enquanto C # não pode ficar abaixo de ~ 3000 ms na mesma máquina (e tem desempenho ainda pior em x64).

Para testar eu mesmo, peguei o código C # (e simplifiquei um pouco para chamar apenas o método onde os parâmetros são passados ​​por valor) e o executei em uma máquina i7-3610QM (aumento de 3,1 GHz para núcleo único), 8 GB de RAM, Win8. 1, usando .NET 4.5.2, RELEASE build de 32 bits (x86 WoW64, pois meu sistema operacional é de 64 bits). Esta é a versão simplificada:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static Point AddByVal(Point a, Point b)
    {
        return new Point(a.X + b.Y, a.Y + b.X);
    }

    public static void Main()
    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);
    }
}

Com Pointdefinido como simplesmente:

public struct Point 
{
    private readonly double _x, _y;

    public Point(double x, double y) { _x = x; _y = y; }

    public double X { get { return _x; } }

    public double Y { get { return _y; } }
}

Executá-lo produz resultados semelhantes aos do artigo:

Result: x=1000000001 y=1000000001, Time elapsed: 3159 ms

Primeira observação estranha

Uma vez que o método deve ser embutido, eu me perguntei como o código funcionaria se eu removesse totalmente as estruturas e simplesmente colocasse tudo embutido juntos:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    public static void Main()
    {
        // not using structs at all here
        double ax = 1, ay = 1, bx = 1, by = 1;

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
        {
            ax = ax + by;
            ay = ay + bx;
        }
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms", 
            ax, ay, sw.ElapsedMilliseconds);
    }
}

E obteve praticamente o mesmo resultado (na verdade, 1% mais lento após várias tentativas), o que significa que o JIT-ter parece estar fazendo um bom trabalho otimizando todas as chamadas de função:

Result: x=1000000001 y=1000000001, Time elapsed: 3200 ms

Também significa que o benchmark não parece medir nenhum structdesempenho e, na verdade, parece medir apenas a doublearitmética básica (depois que todo o resto for otimizado).

As coisas estranhas

Agora vem a parte estranha. Se eu simplesmente adicionar outro cronômetro fora do loop (sim, reduzi-o a esta etapa maluca após várias tentativas), o código será executado três vezes mais rápido :

public static void Main()
{
    var outerSw = Stopwatch.StartNew();     // <-- added

    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    outerSw.Stop();                         // <-- added
}

Result: x=1000000001 y=1000000001, Time elapsed: 961 ms

Isso é ridículo! E não Stopwatché como se estivesse me dando resultados errados, porque posso ver claramente que termina após um único segundo.

Alguém pode me dizer o que pode estar acontecendo aqui?

(Atualizar)

Aqui estão dois métodos no mesmo programa, o que mostra que o motivo não é JITting:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static Point AddByVal(Point a, Point b)
    {
        return new Point(a.X + b.Y, a.Y + b.X);
    }

    public static void Main()
    {
        Test1();
        Test2();

        Console.WriteLine();

        Test1();
        Test2();
    }

    private static void Test1()
    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    private static void Test2()
    {
        var swOuter = Stopwatch.StartNew();

        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test2: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);

        swOuter.Stop();
    }
}

Resultado:

Test1: x=1000000001 y=1000000001, Time elapsed: 3242 ms
Test2: x=1000000001 y=1000000001, Time elapsed: 974 ms

Test1: x=1000000001 y=1000000001, Time elapsed: 3251 ms
Test2: x=1000000001 y=1000000001, Time elapsed: 972 ms

Aqui está um pastebin. Você precisa executá-lo como uma versão de 32 bits no .NET 4.x (há algumas verificações no código para garantir isso).

(Atualização 4)

Seguindo os comentários de @usr sobre a resposta de @Hans, verifiquei a desmontagem otimizada para ambos os métodos, e eles são bastante diferentes:

Teste1 à esquerda, Teste2 à direita

Isso parece mostrar que a diferença pode ser devido ao compilador estar agindo de forma estranha no primeiro caso, ao invés do alinhamento de campo duplo.

Além disso, se eu adicionar duas variáveis ​​(deslocamento total de 8 bytes), ainda obtenho o mesmo aumento de velocidade - e não parece mais que esteja relacionado à menção de alinhamento de campo por Hans Passant:

// this is still fast?
private static void Test3()
{
    var magical_speed_booster_1 = "whatever";
    var magical_speed_booster_2 = "whatever";

    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test2: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    GC.KeepAlive(magical_speed_booster_1);
    GC.KeepAlive(magical_speed_booster_2);
}
Groo
fonte
1
Ao lado do JIT, ele também depende das otimizações do compilador, o mais novo Ryujit faz mais otimizações e até introduziu suporte a instruções SIMD limitado.
Felix K.
3
Jon Skeet encontrou um problema de desempenho com campos somente leitura em structs: Micro-otimização: a surpreendente ineficiência dos campos somente leitura . Tente tornar os campos privados não somente leitura.
dbc de
2
@DBC: fiz um teste apenas com doublevariáveis locais , sem structs, então descartei as ineficiências de layout de estrutura / chamada de método.
Groo
3
Parece acontecer apenas em 32 bits, com RyuJIT, obtenho 1600ms nas duas vezes.
leppie de
2
Eu examinei a desmontagem de ambos os métodos. Não há nada interessante para ver. Test1 gera código ineficiente sem motivo aparente. Bug JIT ou por design. No Test1, o JIT carrega e armazena as duplas para cada iteração na pilha. Isso poderia ser para garantir a precisão exata porque a unidade x86 float usa a precisão interna de 80 bits. Descobri que qualquer chamada de função não embutida na parte superior da função a torna mais rápida.
usr de

Respostas:

10

A atualização 4 explica o problema: no primeiro caso, o JIT mantém os valores calculados ( a, b) na pilha; no segundo caso, o JIT o mantém nos registros.

Na verdade, Test1funciona lentamente por causa do Stopwatch. Eu escrevi o seguinte benchmark mínimo baseado no BenchmarkDotNet :

[BenchmarkTask(platform: BenchmarkPlatform.X86)]
public class Jit_RegistersVsStack
{
    private const int IterationCount = 100001;

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithoutStopwatch()
    {
        double a = 1, b = 1;
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // faddp       st(1),st
            a = a + b;
        }
        return string.Format("{0}", a);
    }

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithStopwatch()
    {
        double a = 1, b = 1;
        var sw = new Stopwatch();
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // fadd        qword ptr [ebp-14h]
            // fstp        qword ptr [ebp-14h]
            a = a + b;
        }
        return string.Format("{0}{1}", a, sw.ElapsedMilliseconds);
    }

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithTwoStopwatches()
    {
        var outerSw = new Stopwatch();
        double a = 1, b = 1;
        var sw = new Stopwatch();
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // faddp       st(1),st
            a = a + b;
        }
        return string.Format("{0}{1}", a, sw.ElapsedMilliseconds);
    }
}

Os resultados no meu computador:

BenchmarkDotNet=v0.7.7.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4702MQ CPU @ 2.20GHz, ProcessorCount=8
HostCLR=MS.NET 4.0.30319.42000, Arch=64-bit  [RyuJIT]
Type=Jit_RegistersVsStack  Mode=Throughput  Platform=X86  Jit=HostJit  .NET=HostFramework

             Method |   AvrTime |    StdDev |       op/s |
------------------- |---------- |---------- |----------- |
   WithoutStopwatch | 1.0333 ns | 0.0028 ns | 967,773.78 |
      WithStopwatch | 3.4453 ns | 0.0492 ns | 290,247.33 |
 WithTwoStopwatches | 1.0435 ns | 0.0341 ns | 958,302.81 |

Como podemos ver:

  • WithoutStopwatchfunciona rapidamente (porque a = a + busa os registros)
  • WithStopwatchfunciona lentamente (porque a = a + busa a pilha)
  • WithTwoStopwatchesfunciona rapidamente de novo (porque a = a + busa os registros)

O comportamento do JIT-x86 depende de uma grande quantidade de condições diferentes. Por alguma razão, o primeiro cronômetro força o JIT-x86 a usar a pilha e o segundo cronômetro permite que ele use os registradores novamente.

AndreyAkinshin
fonte
Isso realmente não explica a causa. Se você verificar meus testes, parece que o teste que tem um adicional Stopwatché executado mais rápido . Mas se você trocar a ordem na qual eles são chamados no Mainmétodo, o outro método será otimizado.
Groo
75

Existe uma maneira muito simples de obter sempre a versão "rápida" do seu programa. Projeto> Propriedades> guia Compilar, desmarque a opção "Preferir 32 bits" e certifique-se de que a seleção de destino da plataforma seja AnyCPU.

Você realmente não prefere 32 bits, infelizmente está sempre ativado por padrão para projetos C #. Historicamente, o conjunto de ferramentas do Visual Studio funcionava muito melhor com processos de 32 bits, um problema antigo que a Microsoft vem eliminando. É hora de remover essa opção, o VS2015 em particular abordou os últimos obstáculos reais para o código de 64 bits com um jitter de x64 totalmente novo e suporte universal para Editar + Continuar.

Chega de conversa, o que você descobriu é a importância do alinhamento para as variáveis. O processador se preocupa muito com isso. Se uma variável estiver desalinhada na memória, o processador terá que fazer um trabalho extra para embaralhar os bytes e colocá-los na ordem correta. Existem dois problemas distintos de desalinhamento, um é quando os bytes ainda estão dentro de uma única linha de cache L1, que custa um ciclo extra para colocá-los na posição correta. E o extra ruim, aquele que você encontrou, onde parte dos bytes estão em uma linha de cache e parte em outra. Isso requer dois acessos de memória separados e colá-los. Três vezes mais lento.

Os tipos doublee longsão os criadores de problemas em um processo de 32 bits. Eles têm 64 bits de tamanho. E pode ficar assim desalinhado em 4, o CLR só pode garantir um alinhamento de 32 bits. Não é um problema em um processo de 64 bits, todas as variáveis ​​têm a garantia de estar alinhadas a 8. Além disso, a razão subjacente pela qual a linguagem C # não pode prometer que sejam atômicas . E por que matrizes de double são alocadas no Large Object Heap quando elas têm mais de 1000 elementos. O LOH fornece uma garantia de alinhamento de 8. E explica porque adicionar uma variável local resolveu o problema, uma referência de objeto tem 4 bytes, então moveu a variável dupla por 4, agora alinhando-a. Por acaso.

Um compilador C ou C ++ de 32 bits faz um trabalho extra para garantir que o double não possa ser desalinhado. Não é exatamente um problema simples de resolver, a pilha pode ficar desalinhada quando uma função é inserida, visto que a única garantia é que ela está alinhada a 4. O prólogo de tal função precisa de um trabalho extra para alinhá-la a 8. O mesmo truque não funciona em um programa gerenciado, o coletor de lixo se preocupa muito sobre onde exatamente uma variável local está localizada na memória. Necessário para que possa descobrir que um objeto no heap do GC ainda está referenciado. Ele não pode lidar adequadamente com essa variável sendo movida em 4 porque a pilha estava desalinhada quando o método foi inserido.

Esse também é o problema subjacente com os jitters do .NET não suportando facilmente as instruções SIMD. Eles têm requisitos de alinhamento muito mais rígidos, do tipo que o processador também não consegue resolver sozinho. SSE2 requer um alinhamento de 16, AVX requer um alinhamento de 32. Não é possível obter isso em código gerenciado.

Por último, mas não menos importante, observe também que isso torna o desempenho de um programa C # executado no modo de 32 bits muito imprevisível. Quando você acessa um double ou long que está armazenado como um campo em um objeto, o perf pode mudar drasticamente quando o coletor de lixo compacta o heap. O que move objetos na memória, tal campo pode agora de repente ficar desalinhado. Muito aleatório, é claro, pode ser muito complicado :)

Bem, nenhuma correção simples, mas um, o código de 64 bits é o futuro. Remova a força de jitter, desde que a Microsoft não altere o modelo do projeto. Talvez na próxima versão quando eles se sentirem mais confiantes sobre Ryujit.

Hans Passant
fonte
1
Não tenho certeza de como o alinhamento atua nisso quando as variáveis ​​duplas podem ser (e estão no Teste2) registradas. Test1 usa a pilha, Test2 não.
usr de
2
Esta questão está mudando muito rápido para que eu acompanhe. Você tem que estar atento para o próprio teste afetando o resultado do teste. Você precisa colocar [MethodImpl (MethodImplOptions.NoInlining)] nos métodos de teste para comparar maçãs com laranjas. Agora você verá que o otimizador pode manter as variáveis ​​na pilha da FPU em ambos os casos.
Hans Passant de
4
Omg, é verdade. Por que o alinhamento do método tem algum impacto nas instruções geradas ?! Não deve haver nenhuma diferença para o corpo do loop. Todos devem estar em registros. O prólogo de alinhamento deve ser irrelevante. Ainda parece um bug do JIT.
usr de
3
Tenho que revisar significativamente a resposta, que chatice. Vou resolver isso amanhã.
Hans Passant de
2
@HansPassant, você vai pesquisar as fontes JIT? Isso seria divertido. Neste ponto, tudo que sei é que é um bug aleatório do JIT.
usr
5

Limitou um pouco (parece afetar apenas o tempo de execução do CLR 4.0 de 32 bits).

Observe que o posicionamento do var f = Stopwatch.Frequency;faz toda a diferença.

Lento (2700ms):

static void Test1()
{
  Point a = new Point(1, 1), b = new Point(1, 1);
  var f = Stopwatch.Frequency;

  var sw = Stopwatch.StartNew();
  for (int i = 0; i < ITERATIONS; i++)
    a = AddByVal(a, b);
  sw.Stop();

  Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms",
      a.X, a.Y, sw.ElapsedMilliseconds);
}

Rápido (800ms):

static void Test1()
{
  var f = Stopwatch.Frequency;
  Point a = new Point(1, 1), b = new Point(1, 1);

  var sw = Stopwatch.StartNew();
  for (int i = 0; i < ITERATIONS; i++)
    a = AddByVal(a, b);
  sw.Stop();

  Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms",
      a.X, a.Y, sw.ElapsedMilliseconds);
}
leppie
fonte
Modificar o código sem tocar Stopwatchtambém altera drasticamente a velocidade. Alterar a assinatura do método Test1(bool warmup)e adicionar uma condicional na Consolesaída: if (!warmup) { Console.WriteLine(...); }também tem o mesmo efeito (descobri isso ao construir meus testes para reproduzir o problema).
Entre
@Entre: eu vi, algo está suspeito. Também só acontece em structs.
leppie de
4

Parece haver algum bug no Jitter porque o comportamento é ainda mais estranho. Considere o seguinte código:

public static void Main()
{
    Test1(true);
    Test1(false);
    Console.ReadLine();
}

public static void Test1(bool warmup)
{
    Point a = new Point(1, 1), b = new Point(1, 1);

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < ITERATIONS; i++)
        a = AddByVal(a, b);
    sw.Stop();

    if (!warmup)
    {
        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }
}

Isso será executado em 900ms, o mesmo que o caso do cronômetro externo. No entanto, se removermos a if (!warmup)condição, ele será executado em 3000ms. O que é ainda mais estranho é que o seguinte código também será executado em 900ms:

public static void Test1()
{
    Point a = new Point(1, 1), b = new Point(1, 1);

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < ITERATIONS; i++)
        a = AddByVal(a, b);
    sw.Stop();

    Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
        0, 0, sw.ElapsedMilliseconds);
}

Observe que removi a.Xe as a.Yreferências da Consolesaída.

Não tenho ideia do que está acontecendo, mas isso me cheira muito mal e não está relacionado a ter um externo Stopwatchou não, o problema parece um pouco mais generalizado.

Entre
fonte
Quando você remove chamadas para a.Xe a.Y, o compilador provavelmente está livre para otimizar praticamente tudo dentro do loop, porque os resultados da operação não são usados.
Groo
@Groo: sim, isso parece razoável, mas não quando você leva em consideração o outro comportamento estranho que estamos vendo. Removendo a.Xe a.Ynão fazendo com que ele vá mais rápido do que quando você inclui a if (!warmup)condição ou os OPs outerSw, o que implica em não otimizar nada, é apenas eliminar qualquer bug que esteja fazendo o código rodar em uma velocidade abaixo do ideal ( 3000ms em vez de 900ms).
Entre
2
Ah, ok, eu pensei que a melhora na velocidade aconteceu quando warmupera verdade, mas nesse caso a linha nem é impressa, então o caso em que ela é impressa realmente faz referência a. No entanto, gosto de ter certeza de que estou sempre referenciando resultados de cálculos em algum lugar próximo ao final do método, sempre que estou fazendo benchmarking.
Groo