que - programas en c++ ejemplos avanzados pdf

¿Qué técnicas de codificación usa para optimizar los programas C?

Question

Hace algunos años, estaba en un panel que estaba entrevistando candidatos para un puesto de programador de C incrustado relativamente mayor.

Una de las preguntas estándar que hice fue sobre técnicas de optimización. Me sorprendió bastante que algunos de los candidatos no tuvieran respuestas.

Entonces, con el objetivo de armar una lista para la posteridad, ¿qué técnicas y construcciones usas normalmente para optimizar los programas de C?

Se aceptan las respuestas a la optimización para la velocidad y el tamaño.

Answer 1

1. Medida de rendimiento.
2. Use puntos de referencia realistas y no triviales. Recuerde que "todo es rápido para N pequeña" .
3. Use un generador de perfiles para encontrar puntos de acceso.
4. Reduzca el número de asignaciones dinámicas de memoria, accesos a disco, accesos a bases de datos, accesos de red y transiciones de usuario / kernel, ya que a menudo tienden a ser puntos de acceso.
5. Medida de rendimiento.

Además, debes medir el rendimiento.

Answer 2

¡La optimización temprana es la raíz de todo mal! ;)

Answer 3

A veces, Google es la mejor herramienta de optimización de algoritmos. Cuando tengo un problema complejo, un poco de búsqueda revela que algunos tipos con PhD han encontrado un mapeo entre esto y un problema bien conocido y ya han hecho la mayor parte del trabajo.

Answer 4

Como mis aplicaciones generalmente no requieren mucho tiempo de CPU por diseño, me concentro en el tamaño de mis binarios en el disco y en la memoria. Lo que hago principalmente es buscar arreglos de tamaño estático y reemplazarlos con memoria asignada dinámicamente donde vale la pena el esfuerzo adicional de liberar la memoria más tarde. Para reducir el tamaño del binario, busco matrices grandes que se inicializan en tiempo de compilación y coloco la inicialización en tiempo de ejecución.

char buf[1024] = { 0, };
/* becomes: */
char buf[1024];
memset(buf, 0, sizeof(buf));

Esto eliminará los 1024 cero bytes de la sección binarios .DATA y en su lugar creará el búfer en la pila en tiempo de ejecución y lo rellenará con ceros.

EDITAR: Ah sí, y me gusta guardar cosas en el caché. No es específico de C, pero dependiendo de lo que está almacenando en caché, puede darle un gran impulso en el rendimiento.

PD: Por favor, háganos saber cuándo su lista está terminada, tengo mucha curiosidad. ;)

Answer 5

Como todos los demás han dicho: perfil, perfil.

En cuanto a las técnicas reales, una que no creo que se haya mencionado aún:

Separación de datos calientes y fríos : permanecer dentro de la memoria caché de la CPU es increíblemente importante. Una forma de ayudar a hacer esto es dividiendo sus estructuras de datos en secciones de acceso frecuente ("caliente") y raramente accesibles ("frío").

Un ejemplo: supongamos que tiene una estructura para un cliente que se ve así:

struct Customer
{
    int ID;
    int AccountNumber;
    char Name[128];
    char Address[256];
};

Customer customers[1000];

Ahora, supongamos que desea acceder al ID y Número de cuenta mucho, pero no tanto al nombre y la dirección. Lo que harías es dividirlo en dos:

struct CustomerAccount
{
    int ID;
    int AccountNumber;
    CustomerData *pData;
};

struct CustomerData
{
    char Name[128];
    char Address[256];
};

CustomerAccount customers[1000];

De esta manera, cuando recorre su matriz de "clientes", cada entrada tiene solo 12 bytes y puede incluir muchas más entradas en la memoria caché. Esto puede ser una gran ganancia si puede aplicarlo a situaciones como el bucle interno de un motor de renderizado.

Answer 6

Difícil de resumir ...

• Estructuras de datos:

  • La división de una estructura de datos dependiendo del caso de uso es extremadamente importante. Es común ver una estructura que contiene datos a los que se accede en función de un control de flujo. Esta situación puede disminuir significativamente el uso de la memoria caché.
  • Para tener en cuenta el tamaño de la línea de caché y las reglas de captación previa.
  • Para reordenar los miembros de la estructura para obtener un acceso secuencial a ellos desde su código

• Algoritmos:

  • Tómese tiempo para pensar sobre su problema y encontrar el algoritmo correcto.
  • Conozca las limitaciones del algoritmo que elija (una clasificación de raíz / clasificación rápida para 10 elementos para clasificar podría no ser la mejor opción).

• Nivel bajo:

  • En cuanto a los últimos procesadores, no se recomienda desenrollar un bucle que tenga un cuerpo pequeño. El procesador proporciona su propio mecanismo de detección para esto y cortocircuitará toda la sección de su tubería.
  • Confíe en el prefetcher de HW. Por supuesto, si sus estructuras de datos están bien diseñadas;)
  • Tenga cuidado con su línea de caché L2.
  • Trate de reducir tanto como sea posible el conjunto de trabajo local de su aplicación, ya que los procesadores se inclinan por cachés más pequeños (C2D disfrutó de 3 MB por núcleo máximo, donde iCore7 proporcionará un máximo de 256 KB por núcleo + 8 MB compartidos con todos los núcleos por cuatro núcleos mueren).

El más importante de todos: medir temprano, medir a menudo y nunca hace suposiciones, basar su pensamiento y optimizaciones en los datos recuperados por un generador de perfiles (utilice PTU ).

Otra sugerencia: el rendimiento es clave para el éxito de una aplicación y debe considerarse en el momento del diseño, y usted debe tener objetivos claros de rendimiento.

Esto está lejos de ser exhaustivo, pero debería proporcionar una base interesante.

Answer 7

En estos días, las cosas más importantes en la optimización son:

• respetando el caché: intente acceder a la memoria en patrones simples y no desenrolle los loops solo por diversión. Use arrays en lugar de estructuras de datos con muchos punteros persiguiendo y probablemente sea más rápido para pequeñas cantidades de datos. Y no hagas nada demasiado grande.
• evitando la latencia: trate de evitar divisiones y cosas que son lentas si otros cálculos dependen de ellos de inmediato. Los accesos a la memoria que dependen de otros accesos a la memoria (es decir, a [b [c]]) son malos.
• Evitar la imprevisibilidad: una gran cantidad de situaciones con condiciones impredecibles, o condiciones que introducen más latencia, realmente lo arruinarán. Hay muchos trucos matemáticos sin sucursales que son útiles aquí, pero aumentan la latencia y solo son útiles si realmente los necesitas. De lo contrario, solo escriba código simple y no tenga condiciones de bucle loco.

No se moleste con las optimizaciones que implican copiar y pegar código (como desenrollar bucles) o reordenar bucles a mano. El compilador normalmente hace un mejor trabajo que tú al hacer esto, pero la mayoría de ellos no son lo suficientemente inteligentes como para deshacerlo.

Answer 8

En la mayoría de los sistemas integrados que trabajé no había herramientas de creación de perfiles, por lo que es bueno decir que usan el generador de perfiles pero no son muy prácticos.

La primera regla en la optimización de la velocidad es encontrar su ruta crítica .
Por lo general, encontrarás que este camino no es tan largo ni tan complejo. Es difícil decir de manera genérica cómo optimizar esto depende de lo que estás haciendo y lo que está en tu poder hacer. Por ejemplo, normalmente quiere evitar memcpy en ruta crítica, por lo que siempre debe usar DMA u optimizar, pero ¿qué ocurre si hw no tiene DMA? compruebe si la implementación de memcpy es la mejor, si no la reescriba.
No utilice ninguna asignación dinámica en embedded pero si lo hace por algún motivo, no lo haga en la ruta crítica.
Organice las prioridades de sus hilos correctamente, lo que es correcto es una pregunta real y es claramente específico del sistema.
Usamos herramientas muy simples para analizar los cuellos de botella, macro simple que almacena la marca de tiempo y el índice. Pocos (2-3) recorridos en el 90% de los casos encontrarán dónde pasa su tiempo.
Y el último es una revisión de código muy importante. En la mayoría de los casos evitamos el problema de rendimiento durante la revisión del código de manera muy efectiva :)

Answer 9

En ocasiones, debe decidir si desea más espacio o más velocidad, lo que generará optimizaciones casi opuestas. Por ejemplo, para aprovechar al máximo su espacio, pack estructuras, por ejemplo #pragma pack (1) y usa campos de bits en las estructuras. Para mayor velocidad, empaca para alinearte con las preferencias de los procesadores y evitar los campos de bits.

Otro truco es elegir los algoritmos de redimensionamiento correctos para el crecimiento de matrices a través de realloc, o mejor aún, escribir su propio administrador de montón basado en su aplicación particular. No asuma que el que viene con el compilador es la mejor solución posible para cada aplicación.

Answer 10

Evita usar el montón. Use los obstáculos o el asignador de grupo para objetos de tamaño idéntico. Ponga cosas pequeñas con corta vida en la pila. alloca todavía existe.

Answer 11

Funciones en línea! Inspirado por los fanáticos del perfilado, describí una aplicación mía y encontré una pequeña función que hace algunos cambios de bits en marcos de MP3. Hace aproximadamente el 90% de todas las llamadas a funciones en mi aplicación, así que lo hice en línea y voila - el programa ahora usa la mitad del tiempo de CPU que antes.

Answer 12

Grandes listas. Solo agregaré un consejo que no vi en las listas anteriores, que en algunos casos puede generar una gran optimización a un costo mínimo.

• enlazador de derivación

  si tiene alguna aplicación dividida en dos archivos, diga main.c y lib.c, en muchos casos puede simplemente agregar un /#include "lib.c" en su main.c Eso omitirá completamente el enlazador y permitirá mucho más optimización eficiente para el compilador.

Se puede lograr el mismo efecto optimizando las dependencias entre los archivos, pero el costo de los cambios suele ser mayor.

Answer 13

La recopilación de perfiles de ejecución de código te ofrece el 50% del camino hasta allí. El otro 50% se ocupa de analizar estos informes.

Además, si usa GCC o VisualC ++, puede usar la "optimización guiada por perfil", donde el compilador tomará información de las ejecuciones anteriores y reprogramará las instrucciones para hacer que la CPU sea más feliz.

Answer 14

Lo primero es lo primero: no optimices demasiado temprano. No es raro pasar tiempo optimizando cuidadosamente una porción de código solo para descubrir que no fue el cuello de botella lo que pensaste que iba a ser. O, para decirlo de otra manera: "Antes de hacerlo rápido, haz que funcione"

Investigue si existe alguna opción para optimizar el algoritmo antes de optimizar el código. Será más fácil encontrar una mejora en el rendimiento optimizando un algoritmo pobre que optimizando el código, solo entonces tirarlo cuando cambies el algoritmo de todos modos.

Y averigüe por qué necesita optimizar en primer lugar. ¿Qué estás intentando lograr? Si intenta, por ejemplo, mejorar el tiempo de respuesta a algún evento, resuelva si hay una oportunidad de cambiar el orden de ejecución para minimizar las áreas críticas en el tiempo. Por ejemplo, cuando intente mejorar la respuesta a alguna interrupción externa, ¿puede hacer alguna preparación en el tiempo muerto entre eventos?

Una vez que haya decidido que necesita optimizar el código, ¿qué valor optimiza? Use un perfilador. Enfoque su atención (primero) en las áreas que se usan con más frecuencia.

Entonces, ¿qué puedes hacer con esas áreas?

• minimizar la verificación de condición. El control de las condiciones (por ejemplo, las condiciones de terminación de los bucles) es el tiempo que no se gasta en el procesamiento real. La verificación de la condición se puede minimizar con técnicas como el desenrollado de bucles.
• En algunas circunstancias, la verificación de condición también se puede eliminar utilizando punteros de función. Por ejemplo, si está implementando una máquina de estado, puede encontrar que implementar los controladores para estados individuales como funciones pequeñas (con un prototipo uniforme) y almacenar el "siguiente estado" almacenando el puntero de función del siguiente controlador es más eficiente que usar un declaración de interruptor grande con el código del controlador implementado en las declaraciones de casos individuales. YMMV.
• minimizar llamadas de función. Las llamadas a funciones normalmente conllevan una carga de ahorro de contexto (por ejemplo, escribir variables locales contenidas en los registros en la pila, guardando el puntero de la pila), de modo que si no tiene que hacer una llamada, se ahorra tiempo. Una opción (si está optimizando la velocidad y no el espacio) es hacer uso de las funciones en línea.
• Si las llamadas a funciones son inevitables, minimice los datos que se pasan a las funciones. Por ejemplo, pasar punteros es probable que sea más eficiente que pasar estructuras.
• Al optimizar la velocidad, elija los tipos de datos que son el tamaño nativo de su plataforma. Por ejemplo, en un procesador de 32 bits, es probable que sea más eficiente manipular valores de 32 bits que valores de 8 o 16 bits. (nota al margen: vale la pena comprobar que el compilador está haciendo lo que crees que es. He tenido situaciones en las que he descubierto que mi compilador insistió en hacer una aritmética de 16 bits en valores de 8 bits con todas las conversiones ay desde ir con ellos)
• Encuentre datos que puedan calcularse previamente y calcule durante la inicialización o (mejor aún) en el momento de la compilación. Por ejemplo, al implementar un CRC, puede calcular sus valores de CRC sobre la marcha (utilizando el polinomio directamente), que es ideal para el tamaño (pero terrible para el rendimiento), o puede generar una tabla de todos los valores provisionales, que es un implementación mucho más rápida, en detrimento del tamaño.
• Localiza tus datos. Si está manipulando una burbuja de datos, a menudo su procesador puede acelerar las cosas al almacenar todo en caché. Y su compilador puede usar instrucciones más cortas que son adecuadas para datos más localizados (por ejemplo, instrucciones que usan compensaciones de 8 bits en lugar de 32 bits)
• En la misma línea, localiza tus funciones. Por las mismas razones.
• Resuelva las suposiciones que puede hacer sobre las operaciones que está realizando y encuentre formas de explotarlas. Por ejemplo, en una plataforma de 8 bits si la única operación que está haciendo en un valor de 32 bits es un incremento, puede encontrar que puede hacer mejor que el compilador al crear (o crear una macro) específicamente para este propósito, en lugar de usar una operación aritmética normal.
• Evite las instrucciones costosas; la división es un buen ejemplo.
• La palabra clave "registrar" puede ser tu amiga (aunque es de esperar que tu compilador tenga una muy buena idea sobre tu uso de registro). Si vas a usar "registrar", es probable que primero tengas que declarar las variables locales que deseas "registrar".
• Sea consistente con sus tipos de datos. Si está haciendo aritmética en una combinación de tipos de datos (por ejemplo, cortos e ints, dobles y flotantes), entonces el compilador está agregando conversiones de tipos implícitos para cada desajuste. Esto es un desperdicio de ciclos de CPU que pueden no ser necesarios.

La mayoría de las opciones enumeradas anteriormente se pueden usar como parte de la práctica normal sin ningún efecto negativo. Sin embargo, si realmente está tratando de obtener el mejor rendimiento: - Investigue dónde puede (con seguridad) deshabilitar la comprobación de errores. No es recomendable, pero te ahorrará espacio y ciclos. - Crea partes de tu código en assembler. Esto, por supuesto, significa que su código ya no es portátil, pero cuando eso no sea un problema, puede encontrar ahorros aquí. Sin embargo, tenga en cuenta que es posible perder tiempo moviendo datos dentro y fuera de los registros que tiene a su disposición (es decir, para satisfacer el uso de registro de su compilador). También tenga en cuenta que su compilador debería estar haciendo un buen trabajo por sí mismo. (por supuesto hay excepciones)

Answer 15

Mi técnica favorita es usar un buen generador de perfiles. Sin un buen perfil que le indique dónde se encuentra el cuello de botella, ningún truco o técnica lo ayudará.

Answer 16

Otra cosa que no fue mencionada:

• Conozca sus requisitos: no optimice para situaciones que no sean probables o que nunca sucedan, concéntrese en la mayor parte del dinero

Answer 17

Para la optimización de bajo nivel:

1. START_TIMER / STOP_TIMER macros de ffmpeg (exactitud a nivel de reloj para la medición de cualquier código).
2. Oprofile, por supuesto, para perfilar.
3. Enormes cantidades de ensamblado codificado a mano (solo haga un wc -l en el directorio x264 / common / x86, y luego recuerde que la mayoría del código está modelado).
4. Cuidada codificación en general; el código más corto es generalmente mejor.
5. Algoritmos inteligentes de bajo nivel, como el escritor de bitstream de 64 bits que escribí que usa solo un único if y ningún otro.
6. Combinación de escritura explícita .
7. Teniendo en cuenta los aspectos extraños e importantes de los procesadores, como el problema de división de caché de Intel .
8. Encontrar casos en los que uno puede realizar una finalización anticipada sin pérdida o casi sin pérdidas, donde el cheque de terminación anticipada cuesta mucho menos que la velocidad que se obtiene de él.
9. En realidad, ensamblado en línea para tareas que son mucho más adecuadas para la unidad SIMD x86, como cálculos de mediana (requiere verificación en tiempo de compilación para compatibilidad con MMX).

Answer 18

Recomiendo optimizar utilizando algoritmos más eficientes y no hacerlo como una idea de último momento, sino codificarlo de esa manera desde el principio. Deje que el compilador resuelva los detalles de las cosas pequeñas, ya que sabe más sobre el procesador de destino que usted.

Por un lado, rara vez uso bucles para buscar cosas, agrego elementos a una tabla hash y luego uso la tabla hash para buscar los resultados.

Por ejemplo, tiene una cadena para buscar y luego 50 valores posibles. Entonces, en lugar de hacer 50 strcmps, agregas las 50 cadenas a una tabla hash y le das a cada una un número único (solo tienes que hacer esto una vez). Luego busca la cadena objetivo en la tabla hash y tiene un interruptor grande con los 50 casos (o tiene punteros a funciones).

Al buscar cosas con conjuntos de datos comunes (como las reglas de CSS), utilizo el código rápido para realizar un seguimiento de las únicas posibles situaciones posibles y luego repetirlas para encontrar una coincidencia. Una vez que tengo una coincidencia, guardo los resultados en una tabla hash (como un caché) y luego uso los resultados de la caché si obtengo la misma entrada establecida más adelante.

Mis principales herramientas para un código más rápido son:

hashtable - para búsquedas rápidas y para obtener resultados de almacenamiento en caché

qsort - es el único tipo que uso

bsp: para buscar cosas según el área (representación del mapa, etc.)

Answer 19

Si alguien no tiene una respuesta a esa pregunta, podría ser que no saben mucho.

También podría ser que ellos saben mucho. Sé mucho (en mi humilde opinión :-), y si me hicieran esa pregunta, les estaría preguntando: ¿por qué creen que es importante?

El problema es que cualquier noción a priori sobre el rendimiento, si no están informadas por una situación específica, son conjeturas por definición.

Creo que es importante conocer las técnicas de codificación para el rendimiento, pero creo que es aún más importante saber no usarlas , hasta que el diagnóstico revele que hay un problema y de qué se trata.

Ahora voy a contradecirme y decir, si lo haces, aprenderás a reconocer los enfoques de diseño que generan problemas para evitarlos, y para un novato, eso suena como una optimización prematura.

Para darle un ejemplo concreto, esta es una aplicación C que fue optimizada .

Answer 20

Si es posible, compárelo con 0, no con números arbitrarios, especialmente en bucles, porque la comparación con 0 se implementa a menudo con comandos de ensamblador independientes y más rápidos.

Por ejemplo, si es posible, escriba

for (i=n; i!=0; --i) { ... }

en lugar de

for (i=0; i!=n; ++i) { ... }

Answer 21

conceptos básicos / general:

• No optimices cuando no tienes ningún problema.
• Conozca su plataforma / CPU ...
• ... saberlo a fondo
• conoce tu ABI
• Deje que el compilador haga la optimización, solo ayúdelo con el trabajo.

algunas cosas que realmente han ayudado:

Optar por tamaño / memoria:

• Usa bitfields para almacenar bools
• reutilizar arreglos globales grandes superponiendo con una unión (tenga cuidado)

Opte por la velocidad (tenga cuidado):

• usar tablas precalculadas cuando sea posible
• colocar funciones / datos críticos en la memoria rápida
• Utilice registros dedicados para los globales utilizados a menudo
• contar hasta cero, bandera cero es gratis

Answer 22

las técnicas más comunes que encontré son:

• desenrollar
• optimización de bucle para una mejor captación previa de caché (es decir, hacer operaciones N en ciclos M en lugar de operaciones singulares NxM)
• alineación de datos
• funciones en línea
• Fragmentos de asm hechos a mano

En cuanto a las recomendaciones generales, la mayoría de ellas ya sonaron:

• elige mejores algos
• usar profiler
• no optimice si no proporciona un aumento de rendimiento del 20-30%

Answer 23

• En primer lugar, use un algoritmo mejor / más rápido. No tiene sentido optimizar el código que es lento por diseño.
• Al optimizar la velocidad, cambie la memoria por velocidad: tablas de búsqueda de valores precalculados, árboles binarios, escriba una implementación personalizada más rápida de las llamadas al sistema ...
• Cuando se usa velocidad de memoria: use compresión en memoria