Estrategias de optimización del rendimiento de último recurso

Ya hay muchas preguntas de rendimiento en este sitio, pero se me ocurre que casi todas son muy específicas de los problemas y bastante limitadas. Y casi todos repiten el consejo para evitar la optimización prematura.

Asummos:

  • el código ya está funcionando correctamente
  • los algoritmos elegidos ya son óptimos para las circunstancias del problema
  • el código ha sido medido, y las rutinas ofensivas han sido aisladas
  • todos los bashs de optimizar también se medirán para garantizar que no empeoren las cosas

Lo que estoy buscando aquí son estrategias y trucos para exprimir hasta el último porcentaje en un algoritmo crítico cuando no queda nada más por hacer, sino lo que sea necesario.

Idealmente, trate de hacer que las respuestas sean independientes del lenguaje, e indique cualquier inconveniente de las estrategias sugeridas cuando corresponda.

Agregaré una respuesta con mis propias sugerencias iniciales, y espero con interés lo que la comunidad de Stack Overflow pueda pensar.

De acuerdo, estás definiendo el problema donde parece que no hay mucho que mejorar. Eso es bastante raro, en mi experiencia. Intenté explicar esto en un artículo del Dr. Dobbs en noviembre de 1993, al partir de un progtwig no trivial convencionalmente bien diseñado sin desperdicios obvios y llevarlo a cabo a través de una serie de optimizaciones hasta que el tiempo del 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 esto . La secuencia de cambios fue esta:

  • El primer problema encontrado fue el uso de clústeres de listas (ahora llamados “iteradores” y “clases de contenedor”) que representan más de la mitad del tiempo. Esos fueron reemplazados por un código bastante simple, reduciendo el tiempo a 20 segundos.

  • Ahora, el que más tiempo toma es más creación de listas. Como porcentaje, no era tan grande antes, pero ahora es porque se eliminó el problema más grande. Encuentro una forma de acelerarlo, y el tiempo desciende 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 desciende a 13 segundos.

Ahora parece que choqué contra una pared. Las muestras me dicen exactamente lo que está haciendo, pero parece que no puedo encontrar nada que pueda mejorar. Luego reflexiono sobre el diseño básico del progtwig, en su estructura impulsada por las transacciones, y me pregunto si toda la búsqueda de listas que está haciendo realmente es obligatoria según los requisitos del problema.

Luego me encuentro con un rediseño, donde el código del progtwig se genera realmente (a través de macros de preprocesador) de un conjunto de fonts más pequeño, y en el que el progtwig no está constantemente descifrando cosas que el progtwigdor sabe que son bastante predecibles. En otras palabras, no “interpretes” la secuencia de cosas para hacer, “comstack”.

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

Ahora, porque se está poniendo tan rápido, es difícil de probar, por lo que le doy 10 veces más trabajo, pero los siguientes tiempos se basan en la carga de trabajo original.

  • Más diagnóstico revela que está pasando tiempo en la gestión de colas. Al alinearlos, se reduce el tiempo a 7 segundos.

  • Ahora, una gran parte del tiempo es la impresión de diagnóstico que he estado haciendo. Enjuague eso – 4 segundos.

  • Ahora los que toman más tiempo son llamadas a malloc y gratuitas . Reciclar objetos – 2.6 segundos.

  • Continuando con la muestra, todavía encuentro operaciones que no son estrictamente necesarias: 1.1 segundos.

Factor de aceleración total: 43.6

Ahora no hay dos progtwigs iguales, pero en el software que no es de juguete siempre he visto una progresión como esta. Primero obtienes lo fácil, y luego lo más difícil, hasta que llegas a un punto de rendimientos decrecientes. Entonces, la percepción que obtengas bien puede conducir a un rediseño, comenzando una nueva ronda de aceleraciones, hasta que vuelvas a obtener rendimientos decrecientes. Ahora bien, este es el punto en el que podría tener sentido preguntarse si ++i o i++ o for(;;) o while(1) son más rápidos: el tipo de preguntas que veo con tanta frecuencia en SO.

PD. Puede preguntarse por qué no usé un generador de perfiles. La respuesta es que casi todos estos “problemas” eran un sitio de llamadas a función, que las muestras de la stack localizan con precisión. Los perfiladores, incluso hoy en día, apenas están llegando a la idea de que las declaraciones y las instrucciones de las llamadas son más importantes de localizar y más fáciles de corregir que las funciones completas. De hecho, construí un generador de perfiles para hacer esto, pero para una verdadera intimidad sucia con lo que el código está haciendo, no hay sustituto para meter los dedos en él. No es un problema que la cantidad de muestras sea pequeña, porque ninguno de los problemas que se encuentran es tan pequeño que se pueden perder fácilmente.

AGREGADO: jerryjvl pidió algunos ejemplos. Aquí está el primer problema. Consiste en una pequeña cantidad de líneas de código separadas, que toman la mitad del tiempo juntas:

  /* 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 estaban usando el ILST del clúster de listas (similar a una clase de lista). Se implementan de la forma habitual, con “ocultamiento de información”, lo que significa que no se supone que los usuarios de la clase tengan que preocuparse de cómo se implementaron. 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. En retrospectiva, es fácil decir que deberían haberse evitado, pero según mi experiencia, todos los problemas de rendimiento son así. En general, es bueno tratar de evitar la creación de problemas de rendimiento. Incluso es mejor encontrar y corregir los que se crean, aunque “deberían haberse evitado” (en retrospectiva). Espero que le dé un poco del sabor.

Este es 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) 

Estas son listas de construcción al agregar elementos a sus fines. (La solución era recolectar los elementos en matrices y comstackr todas las listas a la vez.) Lo interesante es que estas sentencias solo cuestan (es decir, estaban en la stack de llamadas) 3/48 del tiempo original, por lo que no estaban en hecho un gran problema al principio . Sin embargo, después de eliminar el primer problema, costaron 3/20 de las veces y ahora eran un “pez más grande”. En general, así es como va.

Debo agregar que este proyecto fue extraído 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 ciclo interno para ver si una tarea había finalizado.

REFERENCIA AGREGADA: El código fuente, tanto original como rediseñado, se puede encontrar en http://www.ddj.com , para 1993, en el archivo 9311.zip, archivos slug.asc y slug.zip.

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

Sugerencias:

  • Precalcular en lugar de volver a calcular : cualquier bucle o llamadas repetidas que contengan cálculos que tengan un rango relativamente limitado de entradas, considere hacer una búsqueda (matriz o diccionario) que contenga el resultado de ese cálculo para todos los valores en el rango válido de entradas. Luego, use una búsqueda simple dentro del algoritmo.
    Aspectos negativos : si se usan realmente algunos de los valores precalculados, esto puede empeorar las cosas, también la búsqueda puede llevar una memoria significativa.
  • No utilice métodos de biblioteca : la mayoría de las bibliotecas deben escribirse para funcionar correctamente en una amplia gama de escenarios, y realizar comprobaciones nulas de parámetros, etc. Al volver a implementar un método, es posible que pueda eliminar una gran cantidad de lógica que no se aplica en la circunstancia exacta en que lo está usando.
    Abajo : escribir código adicional significa más área de superficie para los errores.
  • Utilice métodos de biblioteca : para contradecirse, las bibliotecas de idiomas las escriben personas que son mucho más inteligentes que usted o yo; lo más probable es que lo hicieron mejor y más rápido. No lo implemente usted mismo a menos que pueda hacerlo más rápido (es decir, ¡siempre mida!)
  • Truco : en algunos casos, aunque puede existir un cálculo exacto para su problema, es posible que no necesite ‘exacto’, a veces una aproximación puede ser ‘suficientemente buena’ y mucho más rápida en el trato. Pregúntate, ¿realmente importa si la respuesta está fuera del 1%? 5%? incluso el 10%?
    Abajo : Bueno … la respuesta no será exacta.

Cuando ya no puede mejorar el rendimiento, vea si puede mejorar el rendimiento percibido .

Es posible que no pueda hacer su algoritmo fooCalc más rápido, pero a menudo hay formas de hacer que su aplicación parezca más receptiva para el usuario.

Algunos ejemplos:

  • anticipando lo que el usuario va a solicitar y comenzar a trabajar en eso antes
  • mostrando resultados a medida que entran, en lugar de todos al mismo tiempo al final
  • Medidor de progreso preciso

Esto no hará que tu progtwig sea más rápido, pero podría hacer que tus usuarios estén más contentos con la velocidad que tienes.

Paso la mayor parte de mi vida en este lugar. Los trazos generales son ejecutar su generador de perfiles y hacer que grabe:

  • Caché falla . La memoria caché de datos es la principal fuente de puestos en la mayoría de los progtwigs. Mejore la tasa de aciertos de caché mediante la reorganización de estructuras de datos ofensivas para tener una mejor localidad; empaquetar estructuras y tipos numéricos hacia abajo para eliminar los bytes desperdiciados (y, por lo tanto, las recuperaciones de caché desperdiciadas); recuperar datos siempre que sea posible para reducir puestos.
  • Load-hit-stores . Las suposiciones del comstackdor sobre el alias de punteros y los casos en que los datos se mueven entre conjuntos de registros desconectados a través de la memoria pueden provocar un cierto comportamiento patológico que causa que toda la interconexión de CPU se borre en una operación de carga. Encuentra lugares donde flotantes, vectores e ints se lanzan entre ellos y elimínalos. Utilice __restrict liberalmente para prometer al comstackdor sobre aliasing.
  • Operaciones microcodificadas . La mayoría de los procesadores tienen algunas operaciones que no se pueden canalizar, sino que ejecutan una pequeña subrutina almacenada en la ROM. Los ejemplos en PowerPC son múltiplos enteros, divisiones y cantidades por turnos. El problema es que toda la tubería se detiene mientras se ejecuta esta operación. Intente eliminar el uso de estas operaciones o al menos divídalas en las operaciones de pipelines que lo componen para que pueda obtener el beneficio del despacho superescalar en lo que sea que haga el rest de su progtwig.
  • Sucurpaciones erróneas Estos también vacian la tubería. Busque casos en los que la CPU esté gastando mucho tiempo llenando la tubería después de una derivación, y use la sugerencia de derivación si está disponible para que prediga correctamente con mayor frecuencia. O mejor aún, reemplace las twigs con movimientos condicionales siempre que sea posible, especialmente después de las operaciones de coma flotante porque su tubería suele ser más profunda y leer las banderas de condición después de que fcmp pueda causar un locking.
  • Operaciones de punto flotante secuencial . Haz estos SIMD.

Y una cosa más que me gusta hacer:

  • Configure su comstackdor para mostrar listados de ensamblaje y observe qué emite para las funciones de zona activa en su código. ¿Todas esas optimizaciones inteligentes que “un buen comstackdor debería poder hacer por usted automáticamente”? Es probable que su comstackdor real no los haga. He visto a GCC emitir un verdadero código WTF.

¡Lanza más hardware a eso!

Mas sugerencias:

  • Evite E / S : cualquier E / S (disco, red, puertos, etc.) siempre será mucho más lenta que cualquier código que realice cálculos, así que elimine cualquier E / S que no necesite estrictamente.

  • Mueva la E / S por adelantado : cargue todos los datos que va a necesitar para un cálculo adelantado, de modo que no tenga repetidas espera de E / S dentro del núcleo de un algoritmo crítico (y tal vez como resultado, se repita disco busca, al cargar todos los datos en un golpe puede evitar buscar).

  • Retardo de E / S : no escriba sus resultados hasta que termine el cálculo, guárdelos en una estructura de datos y luego elimínelos de una vez al final cuando haya terminado el trabajo.

  • E / S roscada : para aquellos que se atreven lo suficiente, combine ‘I / O por adelantado’ o ‘Delay I / O’ con el cálculo real moviendo la carga en un hilo paralelo, de modo que mientras esté cargando más datos, pueda trabajar en un cálculo sobre los datos que ya tiene, o mientras calcula el siguiente lote de datos, puede escribir simultáneamente los resultados del último lote.

Dado que muchos de los problemas de rendimiento involucran problemas con la base de datos, le daré algunas cosas específicas a tener en cuenta al ajustar las consultas y los procedimientos almacenados.

Evite los cursores en la mayoría de las bases de datos. Evite bucle también. La mayoría de las veces, el acceso a los datos debe estar basado en la configuración, no en el registro por procesamiento de registros. Esto incluye no reutilizar un único procedimiento almacenado de registros cuando desee insertar 1,000,000 de registros a la vez.

Nunca use seleccionar *, solo devuelva los campos que realmente necesita. Esto es especialmente cierto si hay alguna unión, ya que los campos de unión se repetirán y, por lo tanto, provocarán una carga innecesaria tanto en el servidor como en la red.

Evite el uso de subconsultas correlacionadas. Use combinaciones (incluidas las uniones a tablas derivadas cuando sea posible) (sé que esto es cierto para Microsoft SQL Server, pero pruebe los consejos cuando utilice un backend diferente).

Índice, índice, índice. Y obtenga esas estadísticas actualizadas si corresponde a su base de datos.

Haga la consulta sargable . Es decir, evitar cosas que imposibilitan el uso de índices, como usar un comodín en el primer carácter de una cláusula similar o una función en la unión o como la parte izquierda de una instrucción where.

Usa los tipos de datos correctos. Es más rápido hacer la fecha matemática en un campo de fecha que tener que intentar convertir un tipo de datos de cadena a un tipo de datos de fecha, luego hacer el cálculo.

¡Nunca coloque un bucle de ningún tipo en un gatillo!

La mayoría de las bases de datos tienen una forma de verificar cómo se realizará la ejecución de la consulta. En Microsoft SQL Server esto se llama un plan de ejecución. Verifique los primeros para ver dónde se encuentran las áreas problemáticas.

Tenga en cuenta la frecuencia con la que se ejecuta la consulta y el tiempo que tarda en ejecutarse al determinar qué debe optimizarse. A veces puede obtener más rendimiento desde un ligero ajuste a una consulta que se ejecuta millones de veces al día que lo que puede al borrar el tiempo de una consulta larga de ejecución que solo se ejecuta una vez al mes.

Utilice algún tipo de herramienta de creación de perfiles para averiguar qué se está enviando realmente a la base de datos y desde ella. Recuerdo una vez en el pasado en la que no pudimos entender por qué la página cargaba tan lentamente cuando el procedimiento almacenado era rápido y se descubrió a través del perfil que la página web solicitaba la consulta muchas veces en lugar de una vez.

El generador de perfiles también te ayudará a encontrar quién está bloqueando a quién. Algunas consultas que se ejecutan rápidamente mientras se ejecutan solos pueden volverse realmente lentas debido a lockings de otras consultas.

El factor limitante más importante hoy es la memoria limitada bandwitdh . Las multicores lo empeoran, ya que el ancho de banda se comparte entre núcleos. Además, el área de chip limitada dedicada a la implementación de cachés también se divide entre los núcleos e hilos, empeorando aún más este problema. Finalmente, la señalización entre chips necesaria para mantener las diferentes cachés coherentes también aumenta con un mayor número de núcleos. Esto también agrega una penalización.

Estos son los efectos que necesita administrar. A veces, a través de la administración de su código micro, pero a veces a través de una cuidadosa consideración y refactorización.

Muchos comentarios ya mencionan el código de caché. Hay al menos dos sabores distintos de esto:

  • Evite las latencias de recuperación de memoria.
  • Menor presión del bus de memoria (ancho de banda).

El primer problema específicamente tiene que ver con hacer que sus patrones de acceso a datos sean más regulares, lo que permite que el precapturador de hardware funcione de manera eficiente. Evite la asignación de memoria dinámica que distribuye sus objetos de datos en la memoria. Use contenedores lineales en lugar de listas enlazadas, hashes y árboles.

El segundo problema tiene que ver con mejorar la reutilización de datos. Modifique los algoritmos para que funcionen en subconjuntos de sus datos que sí quepan en el caché disponible, y reutilice esos datos tanto como sea posible mientras aún estén en el caché.

Al empaquetar los datos de forma más estricta y asegurarse de utilizar todos los datos en las líneas de caché en los bucles activos, se evitarán estos otros efectos y se permitirán datos más útiles en la memoria caché.

  • ¿En qué hardware se está ejecutando? ¿Puedes usar optimizaciones específicas de plataforma (como vectorización)?
  • ¿Puedes obtener un mejor comstackdor? Por ejemplo, ¿cambiar de GCC a Intel?
  • ¿Puedes hacer que tu algoritmo se ejecute en paralelo?
  • ¿Se pueden reducir los errores de caché reorganizando los datos?
  • ¿Puedes desactivar las afirmaciones?
  • Micro-optimize para su comstackdor y plataforma. En el estilo de, “en un if / else, ponga primero la statement más común”
  • Rutinas en línea (eliminar llamada / devolución y empujar parámetro)
  • Intente eliminar las pruebas / interruptores con búsquedas de tablas (si son más rápidas)
  • Desenrollar los bucles (dispositivo de Duff) hasta el punto en que simplemente encajan en el caché de la CPU
  • Localiza el acceso a la memoria para no explotar tu caché
  • Localice los cálculos relacionados si el optimizador no lo está haciendo
  • Elimine las invariantes de bucle si el optimizador no lo está haciendo

Probablemente debería considerar la “perspectiva de Google”, es decir, determinar cómo su aplicación se puede paralelizar y concurrir en gran medida, lo que inevitablemente significará en algún momento analizar la distribución de su aplicación a través de diferentes máquinas y redes, de modo que pueda escalar idealmente de forma casi lineal. con el hardware que le arrojas.

Por otro lado, la gente de Google también es conocida por lanzar muchos recursos humanos y recursos para resolver algunos de los problemas en proyectos, herramientas e infraestructura que están utilizando, como por ejemplo la optimización del progtwig completo para gcc al contar con un equipo dedicado de ingenieros hackear las internas de gcc para prepararlo para escenarios de casos de uso típicos de Google.

Del mismo modo, perfilar una aplicación ya no significa simplemente crear un perfil del código del progtwig, sino también todos sus sistemas e infraestructura circundantes (redes de pensamiento, switches, servidores, matrices RAID) para identificar redundancias y potencial de optimización desde el punto de vista de un sistema.

Aunque me gusta la respuesta de Mike Dunlavey, de hecho es una gran respuesta, de hecho, con un ejemplo de apoyo, creo que podría expressse muy simplemente así:

Averigüe lo que toma la mayor cantidad de tiempo primero, y entienda por qué.

Es el proceso de identificación de los cerdos temporales lo que le ayuda a comprender dónde debe refinar su algoritmo. Esta es la única respuesta agnóstica del lenguaje que abarca todo lo que puedo encontrar para un problema que ya se supone que está completamente optimizado. También suponiendo que quieres ser independiente de la architecture en tu búsqueda de velocidad.

Por lo tanto, aunque el algoritmo puede optimizarse, la implementación del mismo puede no serlo. La identificación le permite saber qué parte es cuál: algoritmo o implementación. Por lo tanto, cualquiera que sea el momento más importante es su principal candidato para la revisión. Pero como dices que quieres exprimir los últimos%, también podrías examinar las partes menores, las partes que no has examinado de cerca al principio.

Por último, un poco de prueba y error con las cifras de rendimiento sobre diferentes formas de implementar la misma solución, o algoritmos potencialmente diferentes, puede aportar ideas que ayudan a identificar los que pierden el tiempo y ahorran tiempo.

HPH, asoudmove.

  • Cuando llega al punto de que está utilizando algoritmos eficientes, es una cuestión de lo que necesita más velocidad o memoria . Use el almacenamiento en caché para “pagar” en la memoria para obtener más velocidad o use cálculos para reducir la huella de memoria.
  • Si es posible (y más rentable) arroje hardware al problema : una CPU más rápida, más memoria o HD podría resolver el problema más rápido que intentar codificarlo.
  • Utilice la paralelización si es posible: ejecute una parte del código en varios subprocesos.
  • Use la herramienta correcta para el trabajo . algunos lenguajes de progtwigción crean un código más eficiente, utilizando el desarrollo acelerado del código administrado (es decir, Java / .NET), pero los lenguajes de progtwigción nativos crean un código de ejecución más rápido.
  • Micro optimize . Solo fueron aplicables, puede usar un ensamblaje optimizado para acelerar piezas pequeñas de código, utilizando optimizaciones de SSE / vector en los lugares correctos que pueden boost enormemente el rendimiento.

Divide y conquistaras

Si el conjunto de datos que se está procesando es demasiado grande, buclee fragmentos de él. Si ha hecho bien su código, la implementación debería ser fácil. Si tienes un progtwig monolítico, ahora lo sabes mejor.

En primer lugar, como se menciona en varias respuestas anteriores, aprenda qué muerde su rendimiento: ¿es memoria o procesador o red o base de datos u otra cosa? Dependiendo de eso …

  • … si es memoria, encuentre uno de los libros escritos hace mucho tiempo por Knuth, una de las series de “The Art of Computer Programming”. Lo más probable es que se trate de ordenar y buscar; si mi memoria es incorrecta, entonces tendrá que averiguar en qué habla sobre cómo lidiar con el almacenamiento lento de datos en cinta. Transformar mentalmente su par de memoria / cinta en su par de caché / memoria principal (o en un par de caché L1 / L2) respectivamente. Estudia todos los trucos que describe: si no encuentras algo que resuelva tu problema, contrata a un científico informático profesional para que realice una investigación profesional. Si su problema de memoria es por casualidad con FFT (errores de caché en índices invertidos en bits al hacer mariposas radix-2), no contrate a un científico; en su lugar, optimice manualmente los pases uno a uno hasta que gane o consiga al callejón sin salida. Mencionaste exprimir hasta el último porcentaje, ¿no? Si es poco , lo más probable es que ganes.

  • … si se trata de un procesador: cambie al lenguaje ensamblador. Especificación del procesador de estudio: lo que hace ticks , VLIW, SIMD. Las llamadas a funciones son, muy probablemente, tic-eaters reemplazables. Aprenda las transformaciones de bucle: canalizar, desenrollar. Las multiplicaciones y divisiones pueden ser reemplazables / interpoladas con cambios de bit (las multiplicaciones por enteros pequeños pueden ser reemplazables por adiciones). Pruebe trucos con datos más cortos: si tiene suerte, una instrucción con 64 bits podría resultar reemplazable con dos en 32 o incluso 4 en 16 u 8 en 8 bits, vaya figura. Pruebe también datos más largos , por ejemplo, los cálculos de flotación pueden ser más lentos que los dobles en un procesador en particular. Si tiene cosas trigonométricas, luche con tablas precalculadas; también tenga en cuenta que el seno de pequeño valor podría reemplazarse con ese valor si la pérdida de precisión está dentro de los límites permitidos.

  • … si se trata de una red: piensa en comprimir los datos que pasas por encima. Reemplazar la transferencia XML con binario. Protocolos de estudio. Pruebe UDP en lugar de TCP si puede manejar la pérdida de datos de alguna manera.

  • … si se trata de una base de datos, vaya a cualquier foro de base de datos y pida consejo. Rejilla de datos en memoria, optimización del plan de consulta, etc. etc.

HTH 🙂

Creo que esto ya se ha dicho de otra manera. Pero cuando se trata de un algoritmo intensivo de procesador, debe simplificar todo dentro del bucle más interno a expensas de todo lo demás.

Eso puede parecer obvio para algunos, pero es algo en lo que bash enfocarme independientemente del idioma con el que estoy trabajando. Si está tratando con bucles nesteds, por ejemplo, y encuentra una oportunidad para bajar un código en un nivel, en algunos casos puede acelerar drásticamente su código. Como otro ejemplo, hay pequeñas cosas en las que pensar como trabajar con enteros en lugar de variables de coma flotante siempre que sea posible, y usar la multiplicación en lugar de la división siempre que sea posible. Nuevamente, estas son cosas que deberían considerarse para su ciclo más interno.

Algunas veces puede encontrar el beneficio de realizar sus operaciones matemáticas en un entero dentro del bucle interno, y luego escalarlo a una variable de coma flotante con la que pueda trabajar después. Ese es un ejemplo de sacrificar velocidad en una sección para mejorar la velocidad en otra, pero en algunos casos la recompensa puede valer la pena.

¡Caché! Una forma barata (en esfuerzo de progtwigdor) de hacer casi cualquier cosa más rápida es agregar una capa de abstracción de almacenamiento en caché a cualquier área de movimiento de datos de su progtwig. Ya sea E / S o simplemente pasar / crear objetos o estructuras. A menudo es fácil agregar cachés a las clases de fábrica y lectores / escritores.

A veces, la memoria caché no te hará ganar mucho, pero es un método fácil de simplemente agregar el almacenamiento en caché y luego deshabilitarlo donde no ayuda. A menudo he encontrado esto para obtener un gran rendimiento sin tener que microanalizar el código.

Muy difícil dar una respuesta genérica a esta pregunta. It really depends on your problem domain and technical implementation. A general technique that is fairly language neutral: Identify code hotspots that cannot be eliminated, and hand-optimize assembler code.

Last few % is a very CPU and application dependent thing….

  • cache architectures differ, some chips have on-chip RAM you can map directly, ARM’s (sometimes) have a vector unit, SH4’s a useful matrix opcode. Is there a GPU – maybe a shader is the way to go. TMS320 ‘s are very sensitive to branches within loops (so separate loops and move conditions outside if possible).

The list goes on…. But these sorts of things really are the last resort…

Build for x86, and run Valgrind /Cachegrind against the code for proper performance profiling. Or Texas Instruments’ CCStudio has a sweet profiler. Then you’ll really know where to focus…

Did you know that a CAT6 cable is capable of 10x better shielding off extrenal inteferences than a default Cat5e UTP cable?

For any non-offline projects, while having best software and best hardware, if your throughoutput is weak, then that thin line is going to squeeze data and give you delays, albeit in milliseconds… but if you are talking about the last drops, that’s a some drops gained, 24/7 for any packge sent or received.

I’ve spent some time working on optimising client/server business systems operating over low-bandwidth and long-latency networks (eg satellite, remote, offshore), and been able to achieve some dtwigtic performance improvements with a fairly repeatable process.

  • Measure : Start by understanding the network’s underlying capacity and topology. Talking to the relevant networking people in the business, and make use of basic tools such as ping and traceroute to establish (at a minimum) the network latency from each client location, during typical operational periods. Next, take accurate time measurements of specific end user functions that display the problematic symptoms. Record all of these measurements, along with their locations, dates and times. Consider building end-user “network performance testing” functionality into your client application, allowing your power users to participate in the process of improvement; empowering them like this can have a huge psychological impact when you’re dealing with users frustrated by a poorly performing system.

  • Analyze : Using any and all logging methods available to establish exactly what data is being transmitted and received during the execution of the affected operations. Ideally, your application can capture data transmitted and received by both the client and the server. If these include timestamps as well, even better. If sufficient logging isn’t available (eg closed system, or inability to deploy modifications into a production environment), use a network sniffer and make sure you really understand what’s going on at the network level.

  • Cache : Look for cases where static or infrequently changed data is being transmitted repetitively and consider an appropriate caching strategy. Typical examples include “pick list” values or other “reference entities”, which can be surprisingly large in some business applications. In many cases, users can accept that they must restart or refresh the application to update infrequently updated data, especially if it can shave significant time from the display of commonly used user interface elements. Make sure you understand the real behaviour of the caching elements already deployed – many common caching methods (eg HTTP ETag) still require a network round-trip to ensure consistency, and where network latency is expensive, you may be able to avoid it altogether with a different caching approach.

  • Parallelise : Look for sequential transactions that don’t logically need to be issued strictly sequentially, and rework the system to issue them in parallel. I dealt with one case where an end-to-end request had an inherent network delay of ~2s, which was not a problem for a single transaction, but when 6 sequential 2s round trips were required before the user regained control of the client application, it became a huge source of frustration. Discovering that these transactions were in fact independent allowed them to be executed in parallel, reducing the end-user delay to very close to the cost of a single round trip.

  • Combine : Where sequential requests must be executed sequentially, look for opportunities to combine them into a single more comprehensive request. Typical examples include creation of new entities, followed by requests to relate those entities to other existing entities.

  • Compress : Look for opportunities to leverage compression of the payload, either by replacing a textual form with a binary one, or using actual compression technology. Many modern (ie within a decade) technology stacks support this almost transparently, so make sure it’s configured. I have often been surprised by the significant impact of compression where it seemed clear that the problem was fundamentally latency rather than bandwidth, discovering after the fact that it allowed the transaction to fit within a single packet or otherwise avoid packet loss and therefore have an outsize impact on performance.

  • Repeat : Go back to the beginning and re-measure your operations (at the same locations and times) with the improvements in place, record and report your results. As with all optimisation, some problems may have been solved exposing others that now dominate.

In the steps above, I focus on the application related optimisation process, but of course you must ensure the underlying network itself is configured in the most efficient manner to support your application too. Engage the networking specialists in the business and determine if they’re able to apply capacity improvements, QoS, network compression, or other techniques to address the problem. Usually, they will not understand your application’s needs, so it’s important that you’re equipped (after the Analyse step) to discuss it with them, and also to make the business case for any costs you’re going to be asking them to incur. I’ve encountered cases where erroneous network configuration caused the applications data to be transmitted over a slow satellite link rather than an overland link, simply because it was using a TCP port that was not “well known” by the networking specialists; obviously rectifying a problem like this can have a dtwigtic impact on performance, with no software code or configuration changes necessary at all.

Not nearly as in depth or complex as previous answers, but here goes: (these are more beginner/intermediate level)

  • obvious: dry
  • run loops backwards so you’re always comparing to 0 rather than a variable
  • use bitwise operators whenever you can
  • break repetitive code into modules/functions
  • cache objects
  • local variables have slight performance advantage
  • limit string manipulation as much as possible

Imposible de decir. It depends on what the code looks like. If we can assume that the code already exists, then we can simply look at it and figure out from that, how to optimize it.

Better cache locality, loop unrolling, Try to eliminate long dependency chains, to get better instruction-level parallelism. Prefer conditional moves over branches when possible. Exploit SIMD instructions when possible.

Understand what your code is doing, and understand the hardware it’s running on. Then it becomes fairly simple to determine what you need to do to improve performance of your code. That’s really the only truly general piece of advice I can think of.

Well, that, and “Show the code on SO and ask for optimization advice for that specific piece of code”.

If better hardware is an option then definitely go for that. De otra manera

  • Check you are using the best compiler and linker options.
  • If hotspot routine in different library to frequent caller, consider moving or cloning it to the callers module. Eliminates some of the call overhead and may improve cache hits (cf how AIX links strcpy() statically into separately linked shared objects). This could of course decrease cache hits also, which is why one measure.
  • See if there is any possibility of using a specialized version of the hotspot routine. Downside is more than one version to maintain.
  • Look at the assembler. If you think it could be better, consider why the compiler did not figure this out, and how you could help the compiler.
  • Consider: are you really using the best algorithm? Is it the best algorithm for your input size?

The google way is one option “Cache it.. Whenever possible don’t touch the disk”

Here are some quick and dirty optimization techniques I use. I consider this to be a ‘first pass’ optimization.

Learn where the time is spent Find out exactly what is taking the time. Is it file IO? Is it CPU time? Is it the network? Is it the Database? It’s useless to optimize for IO if that’s not the bottleneck.

Know Your Environment Knowing where to optimize typically depends on the development environment. In VB6, for example, passing by reference is slower than passing by value, but in C and C++, by reference is vastly faster. In C, it is reasonable to try something and do something different if a return code indicates a failure, while in Dot Net, catching exceptions are much slower than checking for a valid condition before attempting.

Indexes Build indexes on frequently queried database fields. You can almost always trade space for speed.

Avoid lookups Inside of the loop to be optimized, I avoid having to do any lookups. Find the offset and/or index outside of the loop and reuse the data inside.

Minimize IO try to design in a manner that reduces the number of times you have to read or write especially over a networked connection

Reduce Abstractions The more layers of abstraction the code has to work through, the slower it is. Inside the critical loop, reduce abstractions (eg reveal lower-level methods that avoid extra code)

Spawn Threads for projects with a user interface, spawning a new thread to preform slower tasks makes the application feel more responsive, although isn’t.

Pre-process You can generally trade space for speed. If there are calculations or other intense operations, see if you can precompute some of the information before you’re in the critical loop.

Sometimes changing the layout of your data can help. In C, you might switch from an array or structures to a structure of arrays, or vice versa.

Tweak the OS and framework.

It may sound an overkill but think about it like this: Operating Systems and Frameworks are designed to do many things. Your application only does very specific things. If you could get the OS do to exactly what your application needs and have your application understand how the the framework (php,.net,java) works, you could get much better out of your hardware.

Facebook, for example, changed some kernel level thingys in Linux, changed how memcached works (for example they wrote a memcached proxy, and used udp instead of tcp ).

Another example for this is Window2008. Win2K8 has a version were you can install just the basic OS needed to run X applicaions (eg Web-Apps, Server Apps). This reduces much of the overhead that the OS have on running processes and gives you better performance.

Of course, you should always throw in more hardware as the first step…

pass by reference instead of by value

Reduce variable sizes (in embedded systems)

If your variable size is larger than the word size on a specific architecture, it can have a significant effect on both code size and speed. For example, if you have a 16 bit system, and use a long int variable very often, and later realize that it can never get outside the range (−32.768 … 32.767) consider reducing it to short int.

From my personal experience, if a program is ready or almost ready, but we realize it takes up about 110% or 120% of the target hardware’s program memory, a quick normalization of variables usually solves the problem more often than not.

By this time, optimizing the algorithms or parts of the code itself can become frustratingly futile:

  • reorganize the whole structure and the program no longer works as intended, or at least you introduce a lot of bugs.
  • do some clever tricks: usually you spend a lot of time optimizing something, and discover no or very small decrease in code size, as the compiler would have optimized it anyway.

Many people make the mistake of having variables which exactly store the numerical value of a unit they use the variable for: for example, their variable time stores the exact number of milliseconds, even if only time steps of say 50 ms are relevant. Maybe if your variable represented 50 ms for each increment of one, you would be able to fit into a variable smaller or equal to the word size. On an 8 bit system, for example, even a simple addition of two 32-bit variables generates a fair amount of code, especially if you are low on registers, while 8 bit additions are both small and fast.