Categorías
Insights

La mentalidad predominante

Intentaré ser breve.

Hace ya más de diez años, a una persona muy inteligente y a mí nos pusieron a trabajar a destajo en dos proyectos paralelos en Java cuyo núcleo técnico era bastante parecido: había que enviar precios en una red local a toda leche. Por entonces, Java iba sólo por la versión 7, y había una estructura de datos en Java que se había puesto de moda: el «patrón Disruptor». No pongo enlaces porque no se lo merece. La idea del famoso disruptor era sustituir la típica cola bloqueante (o el Channel que ahora tiene .NET Core) por una cola circular, sin bloqueos… y con un hilo dedicado, girando como un demonio constantemente, calentando la CPU y robando recursos. Teóricamente, este desperdicio se traduciría en menos latencia entre procesos… lo cual incluso puede ser cierto.

A esta idea del bucle en perpetuo movimiento se le añadía un poco de polvo de hadas: la cola circular estaba pensada para evitar pedir memoria dentro de lo posible (un problema que provoca el propio Java), y estaba todo calculado para evitar cosas con nombres tan feos como el false sharing (que es un problema real cuando hay concurrencia). Es decir, por estar hecho en Java, el disruptor era ya la leche… aunque terminó teniendo versiones en C# y supongo que hasta en Python. Toda la mierda que los gatos tiran al suelo termina cayendo en una librería de Python y ahí se hace eterna.

La cruda realidad

Como soy incrédulo, sobre todo de las cosas que no me gustan, lo que hicimos (la persona inteligente y yo) fue crear una demo. Probamos el disruptor contra la cola bloqueante de serie de Java, y ganaba el disruptor, aunque no por KO. El ganador absoluto, sin embargo, fue una variante de la cola bloqueante, con el añadido de recuperar e insertar los elementos en lotes. Es una idea estúpidamente simple y efectiva. Si miras la cola y ves que tienes cuatro elementos pendientes de recuperar, aprovecha y tráetelos todos. En Java tienes que ser cuidadoso con estas cosas, y no crear un array cada vez que te traigas n objetos, pero esto tiene una solución tan sencilla como adosar un array a la cola bloqueante en lotes, y reaprovecharlo todo el tiempo.

¿Cuál era el problema del disruptor? Pues que la idea de quemar un hilo empieza pareciendo atractiva, hasta que te das cuenta de que, si esta filosofía la sigues aplicando al resto de la aplicación, te quedas sin CPU en un plisplás. Creo que la única aplicación del disruptor que llegó a usarse en mi empresa de entonces fue en un proceso de logging sin bloqueos. Me dio un ataque de risa cuando me lo contaron, y todavía creo que quien me lo contó bromeaba.

¡Más Java!

Hay un meme rondando Internet y sacado de una peli barata, sobre un productor musical que todo lo resolvía añadiendo more cowbell, es decir, más cencerro, a la pista de percusión de cualquier canción. En el mundo de la programación, el equivalente es añadir más Java a Java. Me explico:

La otra gran decisión a tomar en el par de proyectos paralelos de hace más de diez años era qué íbamos a utilizar para leer y escribir en sockets. Como uno es un idiota iletrado que conoce poco Java, mi razonamiento es que, a no ser que montase una librería de muy bajo nivel en código nativo, cualquier librería basada en sockets que no implementase algún protocolo experimental no iba a ser mejor que la que ya venía en Java. Todas las librerías de sockets de terceros, y había para escoger, lo único que aportaban eran «abstracciones» como superestructura, que presuntamente podían simplificar la programación, pero jamás iban a conseguir que todo fuese más rápido. Por eso, yo me quedé con los sockets de toda la vida, y mi amigo, que es un experto en Java, se decidió por una librería de la famosa fundación Apache.

Y llegó el día del estreno. Mi aplicación llegaba a leer hasta 250.000 mensajes por cada hilo o canal que habilitase en el proceso. La otra aplicación reventó por un límite absurdo que imponía la librería de terceros. El problema se solucionó, por supuesto, tras algo de trabajo adicional. Pero yo, que soy un idiota, me quedé con una moraleja: añadir más Java a Java no suele aportar nada de valor.

Tiempos modernos

Como sospechará el lector, nadie saca una historia de hace diez años si no ha pasado algo parecido recientemente. En efecto. Una librería escrita en C# resuelve un problema de negocios muy interesante. Pero es una librería a secas, y el equipo que la mantiene no da abasto para conectarla a todas las diferentes fuentes de datos posibles. El tiempo de respuesta, además, es sumamente importante, en este caso.

Entonces apareció un Fervoroso Creyente de la Religión Verdadera, que es Java (y Martin Fowler es uno de sus profetas). La solución propuesta fue añadir Java, y polvos de unicornio. Y, como Java iba a estar obligatoriamente en otro proceso, traer un equivalente moderno del disruptor: una librería de comunicaciones que «resuelve» el problema de la «latencia» poniendo un proceso intermedio que gira como un púlsar al que se le ha ido la olla, y un par de hilos en cada extremo haciendo lo mismo. Es decir, la idea del hilo eterno del disruptor multiplicada por tres. Lo probaron en una máquina razonable, con sólo esos tres componentes: un publicador, el intermediario, y un subscriptor. El invento añadió sólo una decena de microsegundos, o eso me contaron, a la transmisión. Eso ya me habría hecho dudar, si lo hubiese sabido a tiempo. El problema es que la aplicación necesita transmitir datos de unos ocho canales. Tres por ocho, aquí y en Javalandia, siempre ha sido igual a veinticuatro. Estoy escribiendo en la máquina a la que llamo El Pepino, y que es un Core i9 con 8 núcleos físicos y 16 núcleos virtuales por hyperthreading. Es decir, menor estrictamente que veinticuatro.

Creo que todavía están apretado y soltando tuercas para intentar que la cosa funcione. Best of the luck, my friends.

Prometí ser breve, pero no lo conseguí.

Categorías
C# Insights

Smart boy’s optimizations

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.

Categorías
Insights Música

Sonata en Mi menor

Llevo un mes practicando esta pieza, en este arreglo:

No es difícil. Ólafsson le añade al arreglo original para piano, de August Stradal, una sección final en la que dobla el ritmo de la mano derecha. Los puristas del Barroco suelen ser críticos con este tipo de arreglos, pero no es mi problema. La pieza es el segundo movimiento (suele ser un Andante) de la Sonata en Mi menor para órgano de Bach. Esta es una ejecución de la partitura original:

Naturalmente, la primera diferencia tiene que ver con cómo adaptas una pieza para dos manuales y una pedalera para un piano. Hay otra pequeña diferencia: los trinos escritos para el órgano no se tocan siempre en el piano. Cuestión de gusto del intérprete. Al fin y al cabo, la ornamentación es sólo un adorno (excepto en el Aria de las Variaciones Goldberg, en la que es difícil separar la pieza de la ornamentación «a la francesa»).

Categorías
Insights

Filosofía vital

Categorías
Insights

Prelude

Este va a ser un blog de Informática, pero no sólo de ella. Voy a utilizarlo también para anotar ideas relacionadas: matemáticas, finanzas, música, física, y lo que se me ocurra.

¿Por qué empiezo un nuevo blog, en vez de retomar alguno de los antiguos? Pues porque mi trabajo ha cambiado mucho en los últimos años. Sigo programando, principalmente en C# y Java, pero cada vez tengo que ocuparme más de la parte matemática de mis proyectos. La gota que, en el buen sentido, ha colmado el vaso, es cierta proof of concept de algoritmos financieros para ordenadores cuánticos, en la que estoy participando. Sorprendente, pero cierto.

Así que… welcome back, my friends, to the show that never ends.