Incremento de rendimiento extraño en un índice de referencia simple

Ayer encontré un artículo de Christoph Nahr titulado ".NET Struct Performance" que comparó varios lenguajes (C ++, C #, Java, JavaScript) para un método que agrega dos estructuras de puntos ( doubletuplas).

Resultó que la versión de C ++ tarda unos 1000 ms en ejecutarse (1e9 iteraciones), mientras que C # no puede llegar a menos de ~ 3000 ms en la misma máquina (y funciona incluso peor en x64).

Para probarlo yo mismo, tomé el código C # (y lo simplifiqué ligeramente para llamar solo al método donde los parámetros se pasan por valor) y lo ejecuté en una máquina i7-3610QM (aumento de 3.1Ghz para un solo núcleo), 8GB RAM, Win8. 1, usando .NET 4.5.2, RELEASE build de 32 bits (x86 WoW64 ya que mi sistema operativo es de 64 bits). Esta es la versión 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);
    }
}

Con Pointdefinido como simplemente:

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

Ejecutarlo produce resultados similares a los del artículo:

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

Primera observación extraña

Dado que el método debería estar en línea, me pregunté cómo funcionaría el código si eliminara las estructuras por completo y simplemente alineara todo junto:

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

Y obtuve prácticamente el mismo resultado (en realidad, un 1% más lento después de varios reintentos), lo que significa que JIT-ter parece estar haciendo un buen trabajo optimizando todas las llamadas a funciones:

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

También significa que el punto de referencia no parece medir ningún structrendimiento y en realidad solo parece medir la doublearitmética básica (después de que todo lo demás se optimiza).

Las cosas raras

Ahora viene la parte extraña. Si simplemente agrego otro cronómetro fuera del ciclo (sí, lo reduje a este paso loco después de varios reintentos), el código se ejecuta tres veces más 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

¡Eso es ridículo! Y no Stopwatches que me esté dando resultados incorrectos porque puedo ver claramente que termina después de un solo segundo.

¿Alguien puede decirme qué podría estar pasando aquí?

(Actualizar)

Aquí hay dos métodos en el mismo programa, lo que muestra que la razón no es 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();
    }
}

Salida:

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

Aquí hay un pastebin. Debe ejecutarlo como una versión de 32 bits en .NET 4.x (hay un par de comprobaciones en el código para garantizar esto).

(Actualización 4)

Siguiendo los comentarios de @ usr sobre la respuesta de @Hans, verifiqué el desmontaje optimizado para ambos métodos, y son bastante diferentes:

Esto parece mostrar que la diferencia podría deberse a que el compilador actuó de manera extraña en el primer caso, en lugar de a una alineación de doble campo.

Además, si agrego dos variables (desplazamiento total de 8 bytes), todavía obtengo el mismo aumento de velocidad, y ya no parece que esté relacionado con la alineación de campo mencionada 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);
}

La Actualización 4 explica el problema: en el primer caso, JIT mantiene los valores calculados ( a, b) en la pila; en el segundo caso, JIT lo mantiene en los registros.

De hecho, Test1funciona lentamente debido al Stopwatch. Escribí el siguiente punto de referencia mínimo basado en 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);
    }
}

Los resultados en mi computadora:

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 rápidamente (porque a = a + busa los registros)
• WithStopwatchfunciona lentamente (porque a = a + busa la pila)
• WithTwoStopwatchesfunciona rápidamente de nuevo (porque a = a + busa los registros)

El comportamiento de JIT-x86 depende de una gran cantidad de condiciones diferentes. Por alguna razón, el primer cronómetro obliga a JIT-x86 a usar la pila, y el segundo cronómetro le permite usar los registros nuevamente.

Existe una forma muy sencilla de obtener siempre la versión "rápida" de su programa. Proyecto> Propiedades> pestaña Compilación, desmarque la opción "Preferir 32 bits", asegúrese de que la selección de destino de la plataforma sea AnyCPU.

Realmente no prefiere 32 bits, desafortunadamente siempre está activado de manera predeterminada para proyectos C #. Históricamente, el conjunto de herramientas de Visual Studio funcionó mucho mejor con procesos de 32 bits, un viejo problema que Microsoft ha ido solucionando. Es hora de eliminar esa opción, VS2015 en particular abordó los últimos obstáculos reales al código de 64 bits con un nuevo jitter x64 y soporte universal para Editar + Continuar.

Basta de charla, lo que descubrió es la importancia de la alineación de las variables. El procesador se preocupa mucho por ello. Si una variable está mal alineada en la memoria, entonces el procesador tiene que hacer un trabajo adicional para mezclar los bytes y ponerlos en el orden correcto. Hay dos problemas de desalineación distintos, uno es cuando los bytes todavía están dentro de una sola línea de caché L1, que cuesta un ciclo adicional para cambiarlos a la posición correcta. Y el extra malo, el que encontraste, donde parte de los bytes están en una línea de caché y parte en otra. Eso requiere dos accesos de memoria separados y pegarlos juntos. Tres veces más lento.

Los tipos doubley longson los causantes de problemas en un proceso de 32 bits. Tienen un tamaño de 64 bits. Y puede desalinearse en 4, el CLR solo puede garantizar una alineación de 32 bits. No es un problema en un proceso de 64 bits, todas las variables están garantizadas para estar alineadas con 8. También es la razón subyacente por la cual el lenguaje C # no puede prometer que sean atómicas . Y por qué las matrices de double se asignan en el montón de objetos grandes cuando tienen más de 1000 elementos. El LOH proporciona una garantía de alineación de 8. Y explica por qué agregar una variable local resolvió el problema, una referencia de objeto es de 4 bytes por lo que movió la variable doble en 4, ahora alineándola. Por accidente.

Un compilador C o C ++ de 32 bits realiza un trabajo adicional para garantizar que el doble no se pueda desalinear. No es exactamente un problema simple de resolver, la pila puede desalinearse cuando se ingresa una función, dado que la única garantía es que está alineada con 4. El prólogo de dicha función necesita hacer un trabajo adicional para alinearla con 8. El mismo truco no funciona en un programa administrado, el recolector de basura se preocupa mucho por dónde se ubica exactamente una variable local en la memoria. Necesario para que pueda descubrir que todavía se hace referencia a un objeto en el montón de GC. No puede lidiar adecuadamente con una variable de este tipo que se mueve 4 porque la pila estaba desalineada cuando se ingresó el método.

Este es también el problema subyacente con las fluctuaciones de .NET que no admiten fácilmente las instrucciones SIMD. Tienen requisitos de alineación mucho más estrictos, del tipo que el procesador tampoco puede resolver por sí mismo. SSE2 requiere una alineación de 16, AVX requiere una alineación de 32. No se puede obtener eso en el código administrado.

Por último, pero no menos importante, también tenga en cuenta que esto hace que el rendimiento de un programa C # que se ejecuta en modo de 32 bits sea muy impredecible. Cuando accede a un doble o largo que está almacenado como un campo en un objeto, el rendimiento puede cambiar drásticamente cuando el recolector de basura compacta el montón. Lo que mueve objetos en la memoria, tal campo ahora puede desalinearse repentinamente. Muy aleatorio, por supuesto, puede ser bastante molesto :)

Bueno, no hay soluciones simples, pero una, el código de 64 bits es el futuro. Elimine el jitter forzando siempre que Microsoft no cambie la plantilla del proyecto. Quizás la próxima versión cuando se sientan más seguros de Ryujit.

Lo redujo un poco (solo parece afectar el tiempo de ejecución de CLR 4.0 de 32 bits).

Observe que la ubicación de los var f = Stopwatch.Frequency;marca marca la diferencia.

Lento (2700 ms):

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

Parece haber algún error en el Jitter porque el comportamiento es aún más extraño. Considere el siguiente 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);
    }
}

Esto se ejecutará en 900ms, al igual que la caja exterior del cronómetro. Sin embargo, si eliminamos la if (!warmup)condición, se ejecutará en 3000ms. Lo que es aún más extraño es que el siguiente código también se ejecutará en 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);
}

Tenga en cuenta que he eliminado a.Xy a.Yreferencias de la Consolesalida.

No tengo idea de lo que está pasando, pero esto me huele bastante a errores y no está relacionado con tener un exterior Stopwatcho no, el problema parece un poco más generalizado.