Estrategias de optimización del rendimiento de último recurso [cerrado]

Bien, estás definiendo el problema hasta donde parece que no hay mucho margen de mejora. Eso es bastante raro, según mi experiencia. Intenté explicar esto en un artículo del Dr. Dobbs en noviembre de 1993, partiendo de un programa convencionalmente bien diseñado y no trivial, sin desperdicio evidente, y llevándolo a través de una serie de optimizaciones hasta que su tiempo de reloj de pared se redujo de 48 segundos. a 1,1 segundos y el tamaño del código fuente se redujo en un factor de 4. Mi herramienta de diagnóstico fue esta . La secuencia de cambios fue esta:

• El primer problema encontrado fue el uso de grupos de listas (ahora llamados "iteradores" y "clases de contenedor") que representaban más de la mitad del tiempo. Estos fueron reemplazados por un código bastante simple, lo que redujo el tiempo a 20 segundos.

• Ahora lo que más tiempo consume es la creación de listas. Como porcentaje, antes no era tan grande, pero ahora lo es porque se eliminó el problema mayor. Encuentro una manera de acelerarlo y el tiempo baja a 17 segundos.

• Ahora es más difícil encontrar culpables obvios, pero hay algunos más pequeños sobre los que puedo hacer algo, y el tiempo se reduce a 13 segundos.

Ahora parece que me he topado con una pared. Las muestras me dicen exactamente qué está haciendo, pero parece que no puedo encontrar nada que pueda mejorar. Luego reflexiono sobre el diseño básico del programa, sobre su estructura basada en transacciones, y pregunto si toda la búsqueda en listas que está haciendo está realmente exigida por los requisitos del problema.

Luego se me ocurrió un rediseño, en el que el código del programa se genera realmente (a través de macros de preprocesador) a partir de un conjunto más pequeño de fuentes, y en el que el programa no está constantemente descubriendo cosas que el programador sabe que son bastante predecibles. En otras palabras, no "interpretes" la secuencia de cosas a hacer, "compilala".

• Ese rediseño se realiza, reduciendo el código fuente en un factor de 4 y el tiempo se reduce a 10 segundos.

Ahora, como se está volviendo tan rápido, es difícil probarlo, así que le doy 10 veces más trabajo, pero los siguientes tiempos se basan en la carga de trabajo original.

• Un mayor diagnóstico revela que está dedicando tiempo a la gestión de colas. Colocarlos en línea reduce el tiempo a 7 segundos.

• Ahora lo que me lleva mucho tiempo es la impresión de diagnóstico que había estado haciendo. Enjuague eso - 4 segundos.

• Ahora las llamadas a malloc y free son las que más tiempo consumen . Reciclar objetos: 2,6 segundos.

• Continuando con el muestreo, todavía encuentro operaciones que no son estrictamente necesarias: 1,1 segundos.

Factor de aceleración total: 43,6

Ahora bien, no hay dos programas iguales, pero en el software que no es un juguete siempre he visto una progresión como esta. Primero obtienes las cosas fáciles y luego las más difíciles, hasta llegar a un punto de rendimientos decrecientes. Entonces, la información que obtenga puede conducir a un rediseño, iniciando una nueva ronda de aceleraciones, hasta que vuelva a alcanzar rendimientos decrecientes. Ahora bien, este es el punto en el que podría tener sentido preguntarse si ++io i++o for(;;)o while(1)son más rápidos: el tipo de preguntas que veo con tanta frecuencia en Stack Overflow.

PD: Quizás se pregunte por qué no utilicé un generador de perfiles. La respuesta es que casi cada uno de estos "problemas" era un sitio de llamada a funciones, que las muestras de pila señalan con precisión. Los perfiladores, incluso hoy en día, apenas se están dando cuenta de que las declaraciones y las instrucciones de llamada son más importantes de localizar y más fáciles de arreglar que funciones completas.

De hecho, construí un generador de perfiles para hacer esto, pero para una verdadera intimidad con lo que hace el código, no hay nada mejor que meter los dedos en él. No es un problema que el número de muestras sea pequeño, porque ninguno de los problemas encontrados es tan pequeño que sea fácil pasarlos por alto.

AÑADIDO: jerryjvl solicitó algunos ejemplos. Aquí está el primer problema. Consiste en una pequeña cantidad de líneas de código separadas, que juntas ocupan más de la mitad del tiempo:

 /* IF ALL TASKS DONE, SEND ITC_ACKOP, AND DELETE OP */
if (ptop->current_task >= ILST_LENGTH(ptop->tasklist){
. . .
/* FOR EACH OPERATION REQUEST */
for ( ptop = ILST_FIRST(oplist); ptop != NULL; ptop = ILST_NEXT(oplist, ptop)){
. . .
/* GET CURRENT TASK */
ptask = ILST_NTH(ptop->tasklist, ptop->current_task)

Estos usaban el grupo de listas ILST (similar a una clase de lista). Se implementan de la forma habitual, "ocultando información", lo que significa que se suponía que los usuarios de la clase no debían preocuparse por cómo se implementaban. Cuando se escribieron estas líneas (de aproximadamente 800 líneas de código), no se pensó en la idea de que podrían ser un "cuello de botella" (odio esa palabra). Son simplemente la forma recomendada de hacer las cosas. Es fácil decir en retrospectiva que deberían haberse evitado, pero en mi experiencia todos los problemas de rendimiento son así. En general, es bueno intentar evitar crear problemas de rendimiento. Es incluso mejor encontrar y corregir los que se crean, aunque "deberían haberse evitado" (en retrospectiva). Espero que eso le dé un poco de sabor.

Aquí está el segundo problema, en dos líneas separadas:

 /* ADD TASK TO TASK LIST */
ILST_APPEND(ptop->tasklist, ptask)
. . .
/* ADD TRANSACTION TO TRANSACTION QUEUE */
ILST_APPEND(trnque, ptrn)

Se trata de crear listas añadiendo elementos en sus extremos. (La solución fue recopilar los elementos en matrices y crear las listas todas a la vez). Lo interesante es que estas declaraciones solo costaron (es decir, estaban en la pila de llamadas) 3/48 del tiempo original, por lo que no estaban en De hecho, un gran problema al principio . Sin embargo, después de eliminar el primer problema, costaron 3/20 del tiempo y ahora eran un "pez más grande". En general, así es.

Debo agregar que este proyecto surgió de un proyecto real en el que ayudé. En ese proyecto, los problemas de rendimiento fueron mucho más dramáticos (al igual que las aceleraciones), como llamar a una rutina de acceso a la base de datos dentro de un bucle interno para ver si una tarea estaba terminada.

REFERENCIA AÑADIDA: El código fuente, tanto original como rediseñado, se puede encontrar en www.ddj.com , correspondiente al año 1993, en el archivo 9311.zip, archivos slug.asc y slug.zip.

EDITAR 26/11/2011: Ahora hay un proyecto SourceForge que contiene código fuente en Visual C++ y una descripción detallada de cómo se ajustó. Solo pasa por la primera mitad del escenario descrito anteriormente y no sigue exactamente la misma secuencia, pero aún así obtiene una aceleración de magnitud de 2 a 3.

May 29 '2009 19:05 Mike Dunlavey