¿Cómo documentar y enseñar a otros código "optimizado más allá del reconocimiento" computacionalmente intensivo?

Ocasionalmente, existe el 1% del código que es computacionalmente lo suficientemente intensivo y necesita el tipo más pesado de optimización de bajo nivel. Ejemplos son el procesamiento de video, el procesamiento de imágenes y todo tipo de procesamiento de señales, en general.

Los objetivos son documentar y enseñar las técnicas de optimización, para que el código no sea imposible de mantener y propenso a su eliminación por parte de los desarrolladores más nuevos. (*)

(*) No obstante la posibilidad de que la optimización particular sea completamente inútil en algunas CPU futuras imprevisibles, de modo que el código se eliminará de todos modos.

Teniendo en cuenta que las ofertas de software (comercial o de código abierto) conservan su ventaja competitiva al tener el código más rápido y hacer uso de la arquitectura de CPU más nueva, los escritores de software a menudo necesitan ajustar su código para que se ejecute más rápido y obtener la misma salida para un determinado tarea, lista blanca que tolera una pequeña cantidad de errores de redondeo.

Por lo general, un escritor de software puede mantener muchas versiones de una función como documentación de cada reescritura de algoritmo / optimización que tiene lugar. ¿Cómo se hacen disponibles estas versiones para que otros estudien sus técnicas de optimización?

Relacionado:

• Código legible limpio vs código rápido difícil de leer. ¿Cuándo cruzar la línea?

Respuesta corta

Mantenga las optimizaciones locales, hágalas obvias, documentelas bien y facilite la comparación de las versiones optimizadas entre sí y con la versión no optimizada, tanto en términos de código fuente como de rendimiento en tiempo de ejecución.

Respuesta completa

Si tales optimizaciones son realmente importantes para su producto, entonces necesita saber no solo por qué las optimizaciones fueron útiles antes, sino también proporcionar suficiente información para ayudar a los desarrolladores a saber si serán útiles en el futuro.

Idealmente, debe incorporar las pruebas de rendimiento en su proceso de compilación, para saber cuándo las nuevas tecnologías invalidan las optimizaciones antiguas.

Recuerda:

La primera regla de optimización del programa: no lo hagas.

La segunda regla de optimización de programas (¡solo para expertos!): No lo hagas todavía ".

- Michael A. Jackson

Para saber si ahora es el momento, se requiere evaluación comparativa y pruebas.

Como mencionó, el mayor problema con el código altamente optimizado es que es difícil de mantener, por lo que, en la medida de lo posible, debe mantener las porciones optimizadas separadas de las porciones no optimizadas. Ya sea que haga esto mediante la vinculación en tiempo de compilación, las llamadas a funciones virtuales en tiempo de ejecución o algo intermedio no debería importar. Lo que debería importar es que cuando ejecuta sus pruebas, desea poder probar todas las versiones en las que está interesado actualmente.

Me inclinaría a construir un sistema de tal manera que la versión básica no optimizada del código de producción siempre pudiera usarse para comprender la intención del código, luego construir diferentes módulos optimizados junto con este que contenga la versión o versiones optimizadas, documentando explícitamente donde sea La versión optimizada difiere de la línea base. Cuando ejecuta sus pruebas (unidad e integración), lo ejecuta en la versión no optimizada y en todos los módulos optimizados actuales.

Ejemplo

Por ejemplo, supongamos que tiene una función de Transformación rápida de Fourier . Quizás tengas una implementación algorítmica básica fft.cy pruebas en fft_tests.c.

Luego viene el Pentium y usted decide implementar la versión de punto fijo al fft_mmx.cusar las instrucciones MMX . Más tarde, el Pentium 3 llega y decide añadir una versión que utiliza las extensiones Streaming SIMD en fft_sse.c.

Ahora desea agregar CUDA , así que agrega fft_cuda.c, pero descubra que con el conjunto de datos de prueba que ha estado utilizando durante años, ¡la versión CUDA es más lenta que la versión SSE! Hace un análisis y termina agregando un conjunto de datos que es 100 veces más grande y obtiene la aceleración que espera, pero ahora sabe que el tiempo de configuración para usar la versión CUDA es significativo y que con conjuntos de datos pequeños debe usar un algoritmo sin ese costo de instalación.

En cada uno de estos casos, está implementando el mismo algoritmo, todos deberían comportarse de la misma manera, pero funcionarán con diferentes eficiencias y velocidades en diferentes arquitecturas (si es que funcionan). Sin embargo, desde el punto de vista del código, puede comparar cualquier par de archivos de origen para averiguar por qué la misma interfaz se implementa de diferentes maneras y, por lo general, la forma más fácil será volver a consultar la versión original no optimizada.

Lo mismo ocurre con una implementación OOP donde una clase base que implementa el algoritmo no optimizado y las clases derivadas implementan diferentes optimizaciones.

Lo importante es mantener las mismas cosas que son iguales , para que las diferencias sean obvias .

Específicamente, ya que ha tomado el ejemplo del procesamiento de video e imagen, uno puede mantener el código como parte de la misma versión pero activo o inactivo según el contexto.

Si bien no lo ha mencionado, supongo que Caquí.

La forma más simple en el Ccódigo, uno hace la optimización (y también se aplica cuando se trata de hacer que las cosas sean portátiles) es mantener

 
#ifdef OPTIMIZATION_XYZ_ENABLE 
   // your optimzied code here... 
#else  
   // your basic code here...

Cuando habilita #define OPTIMIZATION_XYZ_ENABLEdurante la compilación en Makefile, todo funciona en consecuencia.

Por lo general, cortar algunas líneas de código en el medio de las funciones podría volverse desordenado cuando hay demasiadas funciones optimizadas. Por lo tanto, en este caso, se definen diferentes punteros de función para realizar una función específica.

el código principal siempre se ejecuta a través de un puntero de función como

   codec->computed_idct(blocks); 

Pero los punteros de función se definen según el tipo de ejemplo (por ejemplo, aquí la función idct está optimizada para diferentes arquitecturas de CPU.

if(OPTIMIZE_X86) {
  codec->computed_idct = compute_idct_x86; 
}
else if(OPTIMZE_ARM) {
  codec->computed_idct = compute_idct_ARM;
}
else {
  codec->computed_idct = compute_idct_C; 
}

debería ver el código libjpeg y el código libmpeg2 y puede ser ffmpeg para tales técnicas.

Como investigador, termino escribiendo un poco del código de "cuello de botella". Sin embargo, una vez que se pone en producción, la responsabilidad de integrarlo en el producto y proporcionar soporte posterior recae en los desarrolladores. Como puede imaginar, comunicar con claridad qué y cómo se supone que debe operar el programa es de suma importancia.

He descubierto que hay tres ingredientes esenciales para completar este paso con éxito

1. El algoritmo utilizado debe ser absolutamente claro.
2. El propósito de cada línea de implementación debe ser claro.
3. Las desviaciones de los resultados esperados deben identificarse lo antes posible.

Para el primer paso, siempre escribo un documento técnico corto que documenta el algoritmo. El objetivo aquí es escribirlo para que otra persona pueda implementarlo desde cero usando solo el documento técnico. Si es un algoritmo conocido y publicado, es suficiente para dar las referencias y repetir las ecuaciones clave. Si se trata de un trabajo original, deberá ser un poco más explícito. Esto le dirá lo que se supone que debe hacer el código .

La implementación real que se entrega al desarrollo debe documentarse de tal manera que todas las sutilezas se hagan explícitas. Si adquiere bloqueos en un orden particular para evitar un punto muerto, agregue un comentario. Si itera sobre las columnas en lugar de sobre las filas de una matriz debido a problemas de coherencia de caché, agregue un comentario. Si haces algo incluso un poco inteligente, coméntalo. Si puede garantizar el documento técnico y el código nunca se separará (a través de VCS o un sistema similar), puede consultar el documento técnico. El resultado puede ser fácilmente superior al 50% de comentarios. Eso está bien. Esto le dirá por qué el código hace lo que hace.

Finalmente, debe poder garantizar la corrección ante los cambios. Afortunadamente, somos una herramienta útil en pruebas automatizadas y plataformas de integración continua . Estos le dirán qué está haciendo realmente el código .

Mi recomendación más cordial sería no escatimar en ninguno de los pasos. Los necesitarás más tarde;)

Creo que esto se resuelve mejor a través de comentarios completos del código, hasta el punto en que cada bloque significativo de código tenga comentarios explicativos de antemano.

Los comentarios deben incluir citas de las especificaciones o material de referencia de hardware.

Utilice la terminología de la industria y los nombres de algoritmos cuando corresponda, por ejemplo, 'la arquitectura X genera trampas de CPU para lecturas no alineadas, por lo que este dispositivo de Duff se llena hasta el próximo límite de alineación'.

Usaría el nombre de variables en su cara para garantizar que no haya malentendidos de lo que está sucediendo. No es húngaro, pero cosas como 'zancadas' para describir la distancia en bytes entre dos píxeles verticales.

También complementaría esto con un documento corto, legible por humanos que tiene diagramas de alto nivel y diseño de bloques.