Cómo aprender trucos C para computación de alto rendimiento.

Lo más importante para entender es cómo funciona la memoria. Para las computadoras modernas, aquí es donde el rendimiento se gana o se pierde. Para muchos problemas, los patrones de acceso a la memoria tienen un impacto más significativo en el rendimiento que la complejidad algorítmica. Usted querrá comenzar a pensar en sus programas en términos de datos, cómo se presenta en la memoria y cómo su código accede a ellos.

Recomendaría leer el documento ‘Lo que todo programador debe saber sobre la memoria’: página en akkadia.org

Una de las reglas básicas más simples es recordar que el hardware ama los arreglos y está altamente optimizado para la iteración sobre los arreglos. Una optimización simple para muchos problemas es simplemente dejar de usar estructuras de datos sofisticadas y usar arreglos simples (o std :: vectoress en C ++). Esto puede tomar algún tiempo para acostumbrarse.

(Además, si tiene antecedentes en Programación Orientada a Objetos, tendrá que comenzar a pensar de una manera diferente. Piense primero en la disposición de los datos y luego en cómo operará su código en ellos. Deje de pensar en incrustar pequeñas cantidades de datos en objetos que Está encapsulado con métodos cercanos a él.)

Hay diferentes trucos específicos de arquitectura que se pueden hacer, pero honestamente no perdería mucho tiempo con estos. Además, muchas de las optimizaciones de mano que la gente solía hacer en C ahora las realizan compiladores sin la necesidad de un ajuste humano. Es la imagen más grande en la que debe pensar, porque a los compiladores les resulta difícil optimizar esto. Mantener el acceso a la memoria simple y lineal ayudará al rendimiento en casi todas las arquitecturas.

Mencionó el empaquetado de estructuras, pero recuerde que esta es una optimización para reducir el espacio de memoria, no generalmente para aumentar el rendimiento en tiempo de ejecución. El compilador agrega relleno por defecto para mejorar el rendimiento. En algunos casos, simplemente puede cambiar el orden de los miembros de la estructura y obtener una huella de memoria más pequeña y el mismo rendimiento (ganar-ganar).

Hay una serie de libros sobre el tema. Algunos de ellos están fechados, pero los principios generales siguen vigentes.

Zen de la optimización del código por Michael Abrash
Inner Loops de Rick Booth
Computación de alto rendimiento por Charles Severance, Kevin Dowd

Ahora puedes pensar que puedes leer estos libros y llegar a algún tipo de conocimiento secreto prohibido, pero no es así como funciona. Cualquier técnica de rendimiento que aprenda debe medirse y ponerse en contexto para la arquitectura de máquina en particular con la que está trabajando.

No basta con conocer la técnica; Debe saber por qué funciona en su arquitectura y haber medido la mejora con respecto a su uso.

No hay un sustituto para tener conocimiento detallado de arquitectura de computadora. Los siguientes libros son buenos para esta comprensión.

Escriba el Gran Código: Volumen 1: Entendiendo la Máquina por Randall Hyde
Escriba Gran Código, Volumen 2: Pensamiento de bajo nivel, Escritura de alto nivel
Arquitectura de computadora, Quinta edición: Un enfoque cuantitativo por John L. Hennessy, David A. Patterson

No estoy seguro de que la estructura de embalaje sea una buena idea. Cualquier cosa que no esté alineada con los límites de 8 bytes, o tal vez incluso los límites de las líneas de caché, será más lenta de manipular. Guardar un par de bits no es importante.

Punto principal: para la computación de alto rendimiento, necesita comprender qué es costoso para una máquina y qué es irrelevante. Aquí hay un libro bastante bueno:

Escriba un gran código: Volumen 1: Entendiendo la máquina: Randall Hyde: 0689145700381: Amazon.com: Libros

No creo que haya un solo lugar con todos los trucos de C. Simplemente pase el tiempo suficiente programando en C y comunicándose con la comunidad de C, y aprenderá trucos con bastante frecuencia.
En cuanto a mí mismo, aprendí la mayoría de ellos estudiando las preguntas de la entrevista C y realizando un desarrollo de software integrado con Linux (el kernel y los controladores de Linux están llenos de ellos).
Pero si necesita algo, comience con google para las preguntas de la entrevista C. Por lo general, piden trucos interesantes.

El libro de Henry S. Warren, Hacker’s Delight, viene a la mente.

No tengo un enlace en este momento, pero puede buscar la localidad de caché , lo que tiene un efecto dramático en el rendimiento.