¿Cómo medir la complejidad en la práctica en su gran proyecto de software?

11

En la universidad, en nuestros cursos de algoritmos, aprendemos cómo calcular con precisión la complejidad de varios algoritmos simples que se utilizan en la práctica, como las tablas hash o la clasificación rápida.

Pero ahora en un gran proyecto de software, cuando queremos hacerlo más rápido, todo lo que hacemos es mirar piezas individuales: unos pocos bucles anidados que pueden reemplazarse por una tabla hash más rápida, una búsqueda lenta aquí que puede acelerarse mediante una técnica más sofisticada, pero nunca calculamos la complejidad de toda nuestra tubería.

¿Hay alguna manera de hacerlo? ¿O las personas en la práctica solo confían en "localmente" el uso de un algoritmo rápido, para hacer que toda la aplicación sea más rápida, en lugar de considerar globalmente la aplicación como un todo?

(Debido a que me parece no trivial mostrar que si acumula una gran cantidad de algoritmos que se sabe que son muy rápidos por sí mismos, también terminará con una aplicación rápida en su conjunto).

Estoy preguntando esto, porque tengo la tarea de acelerar un proyecto grande que alguien más ha escrito, donde muchos algoritmos interactúan y trabajan en datos de entrada, por lo que no tengo claro cómo el impacto de hacer un algoritmo único más rápido en Toda la aplicación.

usuario7088941
fuente
1) Esto requiere un enfoque de prueba, para encontrar los puntos a mejorar. Pruebas de referencia, pruebas de durabilidad, pruebas dinámicas (mediante el monitoreo de métricas de memoria / CPU de cada componente). 2) Después de encontrar los puntos para mejorar, encontrará la causa raíz de esos puntos. 3) Encuentre una solución para resolver la causa raíz, manteniendo la corrección.
intercambio excesivo
necesita algunas herramientas para estas pruebas que se mencionan en el punto 1
intercambio excesivo
1
El análisis Big O no te dice cómo funcionará un algoritmo. Le dice cómo escalará el rendimiento , a medida que naumenta.
John Wu

Respuestas:

5

Los grandes proyectos de software consisten en muchos componentes diferentes, y no todos son típicamente un cuello de botella. Todo lo contrario: para casi cualquier programa que haya visto en mi vida donde el bajo rendimiento era un problema, se aplicaba el principio de Pareto : más del 80% de las ganancias de rendimiento se pueden lograr optimizando menos del 20% del código (en realidad, yo creo que los números fueron a menudo más del 95% al ​​5%).

Entonces comenzar a mirar piezas individuales es a menudo el mejor enfoque. Es por eso que la creación de perfiles (como se explica en la respuesta de David Arno ) está bien, ya que le ayuda a identificar el 5% mencionado del código en el que la optimización le dará la "mayor inversión". La optimización de "toda la aplicación" conlleva un cierto riesgo de ingeniería excesiva, y si optimiza ese 95% incluso en un factor de 10, a menudo no tendría un efecto medible. Tenga en cuenta también que la creación de perfiles le dice mucho más que cualquier estimación hipotética de la complejidad del algoritmo, ya que un algoritmo simple que necesita O (N ^ 3) pasos aún puede ser más rápido que un algoritmo complejo que requiere O (N log (N)) siempre que N es lo suficientemente pequeño

Después de que el perfil reveló los puntos calientes, uno puede optimizarlos. Por supuesto, un "punto caliente" puede ser más grande que solo una o dos líneas de código, a veces uno tiene que reemplazar un componente completo para hacerlo más rápido, pero eso normalmente será una pequeña parte de la base de código en un programa más grande .

Las técnicas típicas de optimización incluyen

  • Mejorar el uso de algoritmos y estructuras de datos

  • puesta a punto de la primera

  • micro optimizaciones en algunos puntos calientes reales

  • recodificación de secciones críticas utilizando código de ensamblaje o CUDA

Tenga en cuenta que estas técnicas están trabajando en diferentes niveles de abstracción, algunas de ellas viendo un componente más "en su conjunto" que otras. Por lo tanto, depende de lo que quiera decir con "todo lo que hacemos es mirar piezas individuales" . Si solo tenía en mente las micro optimizaciones, no estoy de acuerdo con que "nosotros" trabajemos solo en eso. Pero si te refieres a aplicar esas optimizaciones a gran escala en partes o componentes aislados, entonces "nosotros" probablemente estamos trabajando en las partes correctas, y debes cuestionar tus expectativas.

Doc Brown
fuente
13

La forma estándar, probada y probada es perfilar el código . Realiza un análisis dinámico del sistema en ejecución para medir tiempos, uso de memoria, etc. Luego analiza los resultados para encontrar cuellos de botella en el rendimiento.

Esos cuellos de botella se reescriben experimentalmente y el resultado se perfila una vez más para determinar que se ha logrado un aumento de la velocidad, una reducción en el uso de la memoria, etc. Este proceso se repite hasta que se logra una ganancia de rendimiento aceptable.

David Arno
fuente
1
Esto resuelve el problema de rendimiento, por eso lo hacemos, pero no responde la pregunta original. Creo que en el peor de los casos, la complejidad del tiempo o el espacio se resolvería mejor utilizando una herramienta de análisis de programa estático, que puede faltar. Las pruebas de rendimiento son excelentes para escenarios específicos, pero no le dicen mucho sobre las peores situaciones posibles.
Frank Hileman
3
@FrankHileman Creo que el punto aquí es que el rendimiento es una preocupación práctica y solo se puede medir prácticamente. No usa las matemáticas para encontrar el cuello de botella de su software, incluso si puede resolverlo una vez que se encuentre usando matemáticas (algoritmos).
Comodín
En una nota relacionada, en la presentación de diapositivas de antaño (diapositivas de vidrio), había toda una tecnología pretendida de cómo calcular minuciosamente la densidad promedio de una diapositiva de linterna matemáticamente para determinar el brillo de la luz a usar. Completamente inútil: si la imagen no se ve bien, ¡obtienes una luz más brillante!
Comodín
@Wildcard Si bien el rendimiento solo se puede medir en tiempo de ejecución, se puede predecir estáticamente. Una mala elección de una estructura de datos puede verse bien, en cuanto al rendimiento, en las pruebas de rendimiento, pero puede fallar miserablemente en casos extremos que podrían predecirse en un análisis estático. Esta es la misma razón por la que analizamos los análisis de complejidad del peor de los casos para las estructuras de datos en general.
Frank Hileman
@Wildcard: tienes razón, sin embargo, Frank también es muy correcto al decir que esta publicación no responde la pregunta.
Doc Brown
3

Aunque las otras respuestas son correctas y brindan alguna orientación, creo que pierden un paso. En un sistema complejo como el que está trabajando ahora, comprender los diferentes componentes que componen el sistema es clave para comprender por qué algo es lento.

Mi primer paso sería conseguir un diagrama de arquitectura detallado o crear uno yo mismo. Averigua qué pasos se toman según qué componentes del software y cuánto tiempo lleva cada paso.

Además, descubra cómo los componentes interactúan entre sí. Esto puede hacer toda la diferencia.

Por ejemplo, he visto código en C # donde la interfaz entre dos componentes estaba pasando un IEnumerable construido por el primer componente, que luego fue enumerado por el segundo componente. En C # esto requiere un cambio de contexto, que puede ser costoso bajo ciertas circunstancias. Resolverlo no tiene impacto en el algoritmo. Un simple .ToList () asegura que el resultado se recopile antes de que el siguiente paso resuelva este problema.

Otra cosa a considerar es el impacto en el sistema en el que está ejecutando el código. Obviamente, las interacciones de hardware pueden ser un factor en los sistemas complejos. Busque Disk IO, asignaciones de memoria grande y Network IO. A veces, estos se pueden resolver de manera más eficiente ajustando el sistema o incluso reemplazando el hardware.

Jonathan van de Veen
fuente