“Cualquiera puede resolver la paradoja gris con delfines, e intentas hacerlo sin delfines. "
En realidad, planeé pasar el fin de semana de una manera ligeramente diferente, ir a Copter Huck (no es que fuera fanático de los helicópteros, solo para ver qué inventaban los jóvenes, pasar el rato así), pero la hermana mayor estaba categóricamente en contra. Por supuesto, insistí (es decir, me reí un par de veces y dije: "Bueno, tal vez ... será divertido, de todos modos"), pero ella era implacable, y cuando mi esposa se puso de su lado, no había posibilidad de un viaje. Bueno, está bien, "Realmente no lo quería", pero me senté un poco sobre un rompecabezas divertido del campo de la programación, que pensé por mí mismo, sobre el que estoy informando.
(Nota necesaria: el fin de semana anterior fue así, siempre es así: escribir un programa requiere un par de horas, escribir un informe al respecto y cinco días de viaje en transporte público no se han completado).
En una publicación reciente, el autor consideró el problema de acelerar (entre otras cosas) el cálculo de las curvas de Bezier (KB) en MK con parámetros relativamente débiles. Bueno, de hecho, estos parámetros están al nivel del mainframe promedio de los años 70, pero en la actualidad se consideran claramente insuficientes. Como resultado de ciertas acciones, el autor logró acelerar un poco los cálculos, en mi opinión, claramente no es suficiente, así que decidí escribir cómo debería hacerse esto como una primera aproximación. Sé perfectamente la receta universal para resolver problemas con la velocidad: tomar MK con una frecuencia más alta o cambiarme a otra familia, pero vengo del momento en que aprendimos a sobrevivir con lo que tenemos, simplemente porque no había nada más, de la palabra. En la actualidad, el enfoque está desactualizado, pero me pareció que no sería poco interesante para los lectores modernos de Habr.
Establecemos el problema: queremos calcular las coordenadas de los puntos en la curva de Bezier definida por los puntos extremos A y B y el foco imaginario C. lo más rápido posible. La fórmula para calcular el punto P en la curva viene dada por
donde T varía de 0 a 1 inclusive. (En Wiki escriben que esta fórmula fue secreta alguna vez, era extraño así, pero todo es posible). Está claro que no lo tomaremos en una forma compleja, sino que buscaremos por separado las coordenadas X e Y. Calcularemos la complejidad del cálculo utilizando esta fórmula, simplemente contando el número de signos de operaciones aritméticas en esta expresión: 7 multiplicaciones y 5 adiciones (=> 7 * 5 + ) Es posible que un buen compilador (y ahora todos los compiladores son buenos y se optimizarán perfectamente si no los prohíbe explícitamente) reducirá los costos a 7 * 3 +, aunque sería mejor ayudarlo calculando (1-T) por adelantado. En términos generales, un buen compilador generalmente puede hacer maravillas si todos los valores de la fórmula están representados por constantes, pero suponemos que todos los valores están estáticamente indefinidos.
Primera parte, matemática
Comenzamos el proceso de optimización, para lo cual expandimos los corchetes y agrupamos los términos en T (quizás algún día el compilador podrá hacer esto por nosotros, pero hasta ahora esta parte del trabajo se asigna a la inteligencia natural), obteniendo
=> 5 * 5 +, que es claramente mejor que el valor inicial de 7 * 5 +, pero 7 * 3 + relativamente mejorado aún debe considerarse.
Si nos tomamos el tiempo para completar la operación de suma como uno, entonces el tiempo para completar la multiplicación será exactamente no menos de uno, como regla, más tiempo, pero cuánto depende de la implementación de MK (primero escribió - en la arquitectura, pero esto no es del todo cierto). Cuando no hay un multiplicador de hardware en el cristal, el tiempo de ejecución de la multiplicación será decenas (30+) veces mayor que uno, y cuando esté presente, será varias veces (1-6). Por lo tanto, podemos creer con confianza que reemplazar la multiplicación por la suma da una ganancia (y a menudo significativa) en el tiempo de ejecución casi siempre. Bueno, notaremos de inmediato que la transición de números de punto fijo a un punto flotante (dejamos de lado la prueba de este hecho) conduce a un aumento en el tiempo de ejecución en más de 20 veces para la suma (la alineación es muy influyente aquí), pero solo a un ligero aumento para la multiplicación . Por lo tanto, para los números de coma flotante, los tiempos de suma y multiplicación difieren poco, especialmente en términos relativos (podemos esperar un máximo de 2 veces), pero aún difieren y no están a favor de la multiplicación, por lo que aquí hay una ganancia.
Volviendo al párrafo anterior, encontramos que para PT la calificación 5 * 5 + no debería tener una ventaja significativa sobre 7 * 3 +, pero aún tenemos reservas. Preste atención al hecho de que debemos calcular el conjunto de valores de puntos en la curva de Bezier cuando el parámetro T cambia, y todos los demás parámetros de la curva son fijos (pero no constantes, pero una lástima), entonces el resto de la fórmula se puede calcular por adelantado y obtener
=> 3 * 2 +, donde
y
ya está bien, pero si recuerdas el esquema de Horner y escribes
=> 2 * 2 +, en comparación con la decisión "en la frente" tenemos que ganar más de 2 veces, casi 3, y estas optimizaciones son completamente obvias.
Verifiquemos la teoría con práctica (aunque esto es completamente redundante, confiamos en nuestras estimaciones, pero de repente subestimé el compilador), para lo cual necesitamos medir el tiempo real de ejecución de diferentes opciones en hardware real. Bueno, sucedió que en casa tengo muchos tipos de placas de depuración para MK de varias compañías (incluyendo rarezas como las de Debian de Luminary Micro o Intel Edisson, intente comprar una ahora), pero no hay una sola placa Arduino ("Bueno no tenemos piñas "). Parece un callejón sin salida, pero hay opciones: un sitio muy interesante, tinkercad.com, nos ayuda, en el que puede construir su circuito en una placa de prueba utilizando el módulo Arduino, escribir un boceto e inmediatamente ejecutarlo. Al mismo tiempo, puede establecer puntos de interrupción, ejecutar el programa paso a paso e incluso (algo sin precedentes para un Arduino real) ver los valores de las variables en el momento de la ruptura.
Pasamos a este sitio y comenzamos a medir. Para comenzar, verificamos nuestras suposiciones sobre el tiempo de ejecución de las operaciones y, después de eliminar las circunstancias circundantes, obtenemos los siguientes datos para enteros:
8 + 8 => 8-1 latido, 16 + 16 => 16-2,
8 * 8 => 16 - 2, 16 * 16 => 16 - 14 (lo único que resultó ser inesperado, pensé que obtener 4 * 2 + 4 * 2 = 16, hay optimizaciones interesantes),
8/8 => 8-230, 16/16 => 16-230.
Preste atención a los últimos dos dígitos, de ellos queda claro que la operación de división está prohibida si realmente queremos contar rápidamente. Ahora (finalmente) medimos el tiempo que lleva realizar operaciones en los números de PT con una mantisa de 24 bits
a + b - 126 (y depende en gran medida de los operandos), a * b - 140, a / b - 482.
Los datos obtenidos se correlacionan bien con nuestros supuestos teóricos, está claro que hay una implementación de hardware a bordo de este MK: para multiplicación, para división, no para operaciones, PT.
Ahora comenzamos a medir el tiempo de cálculo completo. Establecemos los valores A = 140, B = 120, C = 70 y construimos 170 puntos distribuidos uniformemente en la oficina de diseño. ¿Por qué precisamente estos valores? Se dieron en la publicación especificada al evaluar el rendimiento. A continuación se muestran los algoritmos y el tiempo de ejecución de la prueba correspondiente.
Fórmula (1) => 20 ms o 1.900 ciclos de reloj por muestra
Fórmula (1) => 18 ms o 1660 ciclos de reloj por muestra (considere por separado 1-T)
Fórmula (2) => 16 ms o 1540 ciclos de reloj por muestra
Fórmula (3) => 10 ms o 923 ciclos de reloj por muestra
Fórmula (4) => 8 ms o 762 medidas por conteo
Se puede ver que la reducción resultante en el tiempo de ejecución (de 20 ms a 8 ms) se correlaciona bien con la esperada y pudimos acelerar los cálculos más de 2 veces. Tenga en cuenta que, además de las consideraciones completamente obvias y las matemáticas, que no van más allá del curso de la escuela secundaria, no lo necesitamos.
Y ahora hablemos sobre qué hacer si el resultado no es suficiente, y ya hemos eliminado todo de las fórmulas de cálculo. Me escribieron aquí (en los comentarios a otra publicación) que, en general, cualquier problema puede reducirse a la computación con FT y, a pesar de la evidente controversia de la suposición (intente hacer esto para la solución numérica de las ecuaciones de Navier-Stokes), en este caso particular, esta recomendación es aplicable Aunque, como siempre, hay matices.
Segunda parte, computación
Una vez que se agotan las modificaciones al algoritmo, solo quedan las estructuras de datos y entramos en el suelo de los números de punto fijo. Aquí encontraremos muchas trampas en las que no pensamos para PT: rango y precisión (en general, para PT uno debería pensar en estos problemas, pero aquí todo es más simple, se ha hecho mucho por nosotros). Es necesario realizar un pequeño estudio del problema para determinar la representación necesaria de FT (seleccionado en el post 9.7 mencionado anteriormente, a juzgar por los resultados, es claramente insuficiente), pero propongo tomar un camino ligeramente diferente. Por cierto, si no damos 170 pasos en el intervalo, sino 128 (no veo ninguna razón que nos prohíba este paso), entonces esta idea nos convendría perfectamente. Si tenemos en cuenta el hecho de que las constantes que definen la KB están dadas por números enteros, y el único parámetro T puede representarse por una fracción de la forma y / y usaremos el resultado para representar en la pantalla, es decir, traducir a coordenadas enteras, entonces podemos simplemente haga todo en enteros, que procesan mucho más rápido.
Usamos solo la última fórmula y la reescribimos en la nueva notación
(=> 2 * 2 + 2 /), donde A1 y B1 se calculan de la misma manera que para PT. Obviamente, todos los números son enteros y las operaciones correspondientes deben realizarse mucho más rápido. Para no perder precisión durante la operación de división entera (2/3 = 1! = 1.5) y hacer la división en el último momento, transformamos ligeramente la fórmula a la forma
(=> 4 * 2 + 2 /). Todos los números FT, por lo que implementamos este algoritmo y obtenemos ... aquí estás, abuela y el día de Yuryev ... 1869 ciclos, pero esto es mucho peor que para FT, comenzamos desde esto, algún tipo de basura, porque los enteros son mucho más rápidos.
Comenzamos el informe y resulta que simplemente cambiar el tipo de variables no es suficiente. Primero, debemos usar números no 8 o incluso 16, sino 32 bits, de lo contrario se producirá un desbordamiento, y números largos, aunque más rápidos que PT, pero no lo suficiente como para compensar las fallas en el algoritmo. En segundo lugar, estas fallas están en nuevamente tuvimos constantes calculadas en cada medida; las eliminamos mediante el cálculo preliminar B2 = B1 * I, A2 = A * I * I. Entonces tenemos
(=> 2 * 2 + 2 /) con un resultado de 1684 es mejor que el anterior, pero aún así no nos escapamos.
Excluimos el cálculo de una constante más And2 = Y * Y obtenemos
(=> 2 * 2 + 1 /), con el tiempo de ejecución de 956 ciclos, pero esto es interesante, la exclusión de una operación condujo a un aumento significativo en la productividad.
Eso es lo que nos frena: la división, porque es una operación que requiere mucho tiempo, pero tenemos un truco interesante para enfrentarla. Para calcular la expresión 1 / Y podemos llevar a cabo transformaciones elementales 1 / = 1 / * ( / ) = 1 * ( / ) / . Si elegimos el grado de dos como H, entonces la división por H puede ser reemplazada por cambios, y si el exponente es un múltiplo de 8, entonces no serán necesarios incluso los cambios. Y el valor de N / A tendrá que calcularse honestamente, pero solo una vez, después de lo cual solo queda la multiplicación en el ciclo de cálculo.
Preste atención al hecho de que hicimos una conversión no muy correcta y reemplazamos el N / A con su valor redondeado K para pasar a operaciones exclusivamente con números enteros. La incorrección consiste en la pérdida de precisión y se deben realizar investigaciones adicionales para demostrar la aplicabilidad de este enfoque en nuestro caso. Escribimos H / I en la forma (K * I + d) / I = K + (d / I), donde q es menor que I. Entonces el error absoluto al ir a H / I a K será d / I, y el error relativo será d / I I / (K + d / I)> = d / I / (K + 1) ~ d / I / K, siempre que K >> 1 (esto no es un cambio). Se deduce que el valor de H debe elegirse lo más grande posible, ya que el error de cálculo absoluto es igual a A * d / I / K> = A * 1 / N / I. Si queremos que el error no sea más que la unidad, debemos soportar la condición A / K <= 1, luego K> = A, convertimos K * I> = A * I, lo que significa H> = A * I, entonces no perdiendo en precisión. En nuestro caso, A <= 256 e I <= 256, obtenemos H> = 2 ** 16, lo cual es bastante aceptable. Obviamente, en las fórmulas anteriores, se deben usar los módulos de los números originales.
Observamos para el futuro que si redondeamos no hacia abajo, sino hacia el número entero más cercano, entonces los requisitos se reducen un poco y H debería ser suficiente la mitad, aunque hay matices.
En cualquier caso, podemos proporcionar la precisión requerida y obtener el siguiente algoritmo: H = 2 ** 16; K = [N / A] (I <256); 0 <= y <= AND;
(=> 4 * 2 + 2 >> 16) donde todas las operaciones se llevan a cabo en enteros largos. Implementamos este algoritmo y obtenemos 583 ciclos de reloj ... pero esto ya está cerca del ideal, pero aún no lo es.
Luego vienen las configuraciones pequeñas para un MK específico: trabajar con variables globales es más rápido. que con los locales, pero aún más rápido con el registro local, lo que lleva a una reducción en el tiempo a 506 ciclos de reloj.
Además, observamos que la última multiplicación antes del cambio se puede llevar a cabo con números de 16 bits, lo que dará 504, un poco, pero agradable.
En total, aceleramos los cálculos en comparación con la implementación de "frente" en 1900/504, más de 3 veces, y no perdimos exactamente la palabra. Este es el resultado que llamo optimización de tiempo, y no el 20% recibido en la publicación original.
¿Es posible lograr indicadores aún mejores? Es posible, pero este es el tema de la próxima publicación.