Categoría: Insights

Decía el gran Donald Knuth algo así como que premature optimization is the root of all evil. Santificado sea su nombre…

Calidad de código

Una vez citadas las sagradas escrituras, debo reconocer que mi lado hereje cumple otros mandamientos:

• Peor que la optimización prematura, es no optimizar nunca. Una vez escuché una mala excusa sobre un programa que tardaba 25 horas en cargar un fichero: «es que nadie me dijo que tenía que ser rápido». Los ordenadores existen, precisamente, para hacer las cosas más rápidamente. No sólo porque es interés directo del usuario del programa que éste termine antes, sino que, además, le interesa el ahorro en electricidad y en el desgaste del propio aparato.
• Si estás escribiendo una aplicación, te puedes permitir el lujo de esperar a que funcione para buscar los puntos críticos de eficiencia. Pero si estás escribiendo una librería, que se va a utilizar en formas que aún no sospechas… mejor que todo vaya como la seda desde el principio.
• La mayoría de las optimizaciones (yo diría más bien mejoras) caen en una categoría que yo llamo «mejoras de chico listo», y tienen que ver con la calidad del código que cada programador puede generar sin esfuerzo adicional.

Las optimizaciones de chico listo, por supuesto, dependen de la experiencia del programador, de lo bien que le funcione la memoria y de lo bien que se le dé la detección de patrones, por lo que se trata de una categoría difícil de delimitar. Programar es un arte.

Un ejemplo

En cualquier caso, el propósito de esta entrada es mostrarle algunas de las optimizaciones que he aprendido mirando el código fuente de .NET. Yo las tengo ya en mi memoria de trabajo: las aplico automáticamente cuando detecto que son aplicables.

Trabajando con una implementación de la función erf, tropecé con este código, que evalúa un polinomio en un punto, usando los coeficientes de una tabla:

private static double Evaluate(double z, double[] coefficients)
{
    if (coefficients == null)
        throw new ArgumentNullException(nameof(coefficients));
    int n = coefficients.Length;
    if (n == 0)
        return 0;
    double sum = coefficients[n - 1];
    for (int i = n - 2; i >= 0; --i)
    {
        sum *= z;
        sum += coefficients[i];
    }
    return sum;
}

Esta función se ejecuta varias veces, con distintos coeficientes. Un ejemplo de tabla de coeficientes es ésta:

static readonly double[] ErvInvImpAn =
{
    -0.000508781949658280665617, -0.00836874819741736770379,
    0.0334806625409744615033, -0.0126926147662974029034,
    -0.0365637971411762664006, 0.0219878681111168899165,
    0.00822687874676915743155, -0.00538772965071242932965
};

Este método es un método privado de una clase, y una rápida ojeada me confirmó que las tablas que se le pasan son siempre no nulas, y con longitud mayor que cero. ¿A qué vienen las dos comprobaciones iniciales? Respuesta: es uno de los problemas que causa la «modularidad». Escribes software que no sabes cómo se puede usar, y lo proteges de las cosas más inverosímiles. Pero si es un método privado, tanta precaución sobra. Empezamos por esta simplificación, para ir haciendo boca y verlo todo más claro:

private static double Evaluate(double z, double[] coefficients)
{
    int n = coefficients.Length;
    double sum = coefficients[n - 1];
    for (int i = n - 2; i >= 0; --i)
    {
        sum *= z;
        sum += coefficients[i];
    }
    return sum;
}

El siguiente paso seguramente le sorprenderá: sustituyo la tabla de coeficientes, que ahora es un campo estático de sólo lectura, por esto:

static ReadOnlySpan<double> ErvInvImpAn => new[]
{
    -0.000508781949658280665617, -0.00836874819741736770379,
    0.0334806625409744615033, -0.0126926147662974029034,
    -0.0365637971411762664006, 0.0219878681111168899165,
    0.00822687874676915743155, -0.00538772965071242932965
};

Sorprendente, ¿verdad? Es un truco poco conocido, pero que Microsoft usa a diestra y siniestra en el código de .NET Core. Por razones que en parte se me escapan, el compilador de C# y el JIT transforman esta construcción en una zona de datos dentro de los metadatos del código IL. Y el JIT lo maneja más eficientemente. No hay mucha lógica en que tengamos que usar precisamente un ReadOnlySpan<double>, o que haya que convertir el campo en una propiedad de sólo lectura. Se trata de una marca, o un guiño de complicidad, que utilizan el JIT y el compilador para generar código más eficiente.

Esto me obliga a crear una nueva versión del amigo Evaluate que acepte un ReadOnlySpan<double> como origen de sus coeficientes. Esta es la nueva versión, con dos optimizaciones adicionales:

private static double Evaluate(
    double z, ReadOnlySpan<double> coeffs)
{
    int n = coeffs.Length;
    ref double rd = ref MemoryMarshal.GetReference(coeffs);
    double sum = Unsafe.Add(ref rd, n - 1);
    for (int i = n - 2; i >= 0; --i)
        sum = Math.FusedMultiplyAdd(
            z, sum, Unsafe.Add(ref rd, i));
    return sum;
}

De las dos nuevas mejoras, la más sencilla es el uso de Math.FusedMultiplyAdd: un método de la clase Math que combina la multiplicación y la suma en una sola instrucción de la CPU, y puede darnos más velocidad y precisión. En este caso, además, he medido que realmente sea ventajosa, porque no siempre lo es.

El segundo cambio tiene dos partes. Como el bucle for utilizado no es un bucle convencional, el JIT actual no puede deducir que no habrán referencias fuera de rango para eliminar las comprobaciones de los índices en tiempo de ejecución. El bucle es descendente, y ni siquiera comienza por el último elemento. No le podemos exigir tanto al JIT.

Lo primero que hago es pedir una managed reference a la primera celda de la tabla de coeficientes:

    ref double rd = ref MemoryMarshal.GetReference(coeffs);
    // Equivalente a:
    // ref double rd = ref coeffs[0];

Esto es más o menos parecido a pedir un puntero al inicio de la tabla. En realidad, C# nos permitiría pedir un puntero al inicio de la tabla, pero el precio sería «fijar» la tabla en memoria para que el recolector de basura no vaya a pensar que no la estamos usando. El puntero que conseguimos con esta técnica es uno que el recolector de basura puede identificar y tener en cuenta. Y la forma normal de pedirlo es la que muestro en los comentarios del fragmento. ¿Por qué no la he usado? Pues porque implicaría una comprobación de rango innecesaria: el JIT generaría una comparación y un salto para verificar si la tabla no está vacía. Para evitarlo, uso MemoryMarshal.GetReference, que es otro truco sucio de Microsoft, para conseguir un puntero al inicio de un array sin costes ocultos.

Lo que sigue es más sencillo: utilizo el método Add de la clase Unsafe para llegar a cada una de las celdas que contienen los coeficientes. Sí, todo es un poco enrevesado, pero una vez que te lo aprendes, no te cuesta nada escribir estas cosas de carrerilla. Me siento en el deber de contárselas. Ya usted decidirá si merece la pena o no usarlas en su propio código cuando lo crea necesario. No son cosas para usar en una aplicación que tienes que escribir en tres meses. Pero creo que tienen un lugar en una librería de código.

Y hay más, claro

Hay montones de trucos similares en el código fuente de .NET. Por ejemplo, imagine que hay que tiene que hacer una comprobación de rango de un índice:

if (0 <= index && index < length) ...

Dos comparaciones, y dos saltos. Las comparaciones son lo de menos. Los dos saltos ralentizan todo. ¿Qué hace Microsoft en estos casos?

if ((uint)index < length) ...

La variable index suele ser un entero con signo. No cuesta nada pedir que el compilador la trate, momentáneamente, como un entero del mismo tamaño, pero sin signo. Si el índice fuese negativo, al tratarlo como un entero sin signo, el valor sería inevitablemente superior al de length. Una sola comparación, y un único salto potencial.

Veamos una variante derivada de este truco. El analizador lexical de Austra tiene que comprobar muchas veces si un carácter es un dígito decimal:

if ('0' <= ch && ch <= '9') ...

La forma más eficiente, sin embargo, es la siguiente:

if ((uint)(ch - '0') < 10u) ...

He introducido una resta, que se ejecuta eficientemente, y he quitado un salto potencial.

De todas maneras, una de mis optimizaciones de chico listo preferidas es muy sencilla. En vez de escribir:

x * x - y * y

un servidor prefiere:

(x + y) * (x - y)

Y es que en la segunda expresión hay una suma de más, pero una multiplicación de menos.

Es agradable tener un cerebro cargado, y estar dispuestos a usarlo.