Optimización, profiling y complejidad

Un programa rápido no es el que acumula trucos: es el que dedica el tiempo donde de verdad se consume. Aquí aprendes a medir con std::chrono y a distinguir los tres cuellos de botella que explican casi todo en C++: cuántas operaciones pides, cómo recorres la memoria y qué consigue vectorizar el compilador.

¿Qué es optimizar un programa?

Optimizar es reducir el trabajo que el procesador hace para llegar al mismo resultado. No es añadir construcciones exóticas ni comentarios sobre lo rápido que va: es cambiar lo que se ejecuta millones de veces y comprobar con una medición que el cambio sirvió. Si no puedes medir la diferencia, no has optimizado: has modificado.

• Menos operaciones: cambiar un algoritmo cuadrático por uno lineal reduce el trabajo por un factor que crece con los datos.
• Mejor uso de la memoria: recorrer los datos en el orden en que están guardados evita esperar a la RAM.
• Más trabajo por instrucción: con instrucciones SIMD procesas cuatro o más double a la vez.
• Más núcleos: repartir el bucle entre hilos solo ayuda cuando las tres palancas anteriores ya están resueltas.

El reparto del tiempo no es uniforme: una fracción pequeña del código consume la mayor parte de la ejecución, y ahí una hora de trabajo produce un cambio visible. El resto no merece que lo toques.

¿Para qué sirve medir antes de optimizar?

Imagina un entrenamiento que tarda cuatro horas. El equipo sospecha del cálculo de la pérdida y propone reescribirlo con punteros. Un perfil muestra que el ochenta por ciento del tiempo está en una lectura de archivos repetida en cada época. La sospecha era razonable y falsa.

• Bucles calientes: los que se ejecutan millones de veces y suman casi todo el tiempo.
• Datos que no caben en caché: cuando el conjunto supera unos megabytes, el orden de acceso pesa más que la aritmética.
• Latencia frente a rendimiento: a veces no importa el total sino el tiempo hasta la primera respuesta.
• Decisiones de diseño: elegir entre std::vector y std::list se decide con números, no con intuición.

La ley de Amdahl pone un límite: si el veinte por ciento del tiempo es irreducible, ninguna optimización del ochenta restante bajará el total de ese veinte.

Cómo funciona por dentro: coste, caché y compilador

La notación Big-O describe cómo crece el número de operaciones cuando crece el tamaño de la entrada, ignorando constantes. Un algoritmo O(n) hace una operación por elemento; uno O(n²) hace una por cada pareja. La constante importa poco cuando n es grande, porque el exponente domina.

A mil millones de operaciones simples por segundo, 10¹² operaciones son unos diecisiete minutos y 10¹⁸ son más de treinta años. Esa es la razón por la que cambiar de exponente gana siempre a microoptimizar: pasar de O(n²) a O(n log n) con un millón de elementos convierte diecisiete minutos en veinte milisegundos.

El segundo cuello de botella es la memoria. El procesador no lee la RAM byte a byte: trae líneas de caché de 64 bytes, ocho double contiguos. Si tu bucle usa esos ocho valores seguidos, el coste se reparte entre ocho operaciones; si salta de fila en fila, paga el viaje completo por un solo valor.

Las latencias explican la diferencia: un acceso en L1 cuesta del orden de un nanosegundo; uno que falla hasta la RAM, del orden de cien. En ese tiempo el procesador podría ejecutar cientos de instrucciones.

El tercer factor es el compilador. Con -O2 desenrolla bucles, mantiene variables en registros y agrupa operaciones en instrucciones SIMD; con -O0 no hace casi nada de eso. Un benchmark sin optimizar mide un programa que nunca vas a distribuir.

Sintaxis: medir con std::chrono

std::chrono separa dos ideas: un instante (time_point) y una duración (duration). Tomas dos instantes con steady_clock::now() y restas: el resultado es una duración que puedes convertir a la unidad que quieras.

123456789101112131415161718

#include <chrono>
#include <cstdio>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> datos(10'000'000);
    std::iota(datos.begin(), datos.end(), 0.0);

    const auto inicio = std::chrono::steady_clock::now();
    double suma = 0.0;
    for (double valor : datos) suma += valor;
    const auto fin = std::chrono::steady_clock::now();

    const double ms = std::chrono::duration<double, std::milli>(fin - inicio).count();
    std::printf("suma = %.0f en %.2f ms\n", suma, ms);
    return 0;
}

• steady_clock es monótono: nunca retrocede aunque se ajuste la hora del sistema; system_clock sí puede saltar.
• duration<double, std::milli> convierte la diferencia a milisegundos; sin eso obtienes «ticks» del reloj.
• .count() devuelve el número; sin él, printf no sabe imprimir la duración.
• La suma se imprime al final: sin usar el resultado, el compilador puede borrar el bucle y medirás cero.

Ejemplo básico: sumar cincuenta millones de doubles

Dos versiones del mismo cálculo. La primera acumula en una sola variable; la segunda usa cuatro acumuladores independientes para que el procesador no espere a que termine una suma antes de empezar la siguiente.

12345678910111213141516171819202122232425262728293031323334353637383940

#include <chrono>
#include <cstdio>
#include <vector>

double suma_serial(const std::vector<double>& v) {
    double s = 0.0;
    for (double x : v) s += x;  // una dependencia encadenada
    return s;
}

double suma_cuatro(const std::vector<double>& v) {
    double a = 0.0, b = 0.0, c = 0.0, d = 0.0;
    const std::size_t n = v.size();
    std::size_t i = 0;
    for (; i + 4 <= n; i += 4) {
        a += v[i];
        b += v[i + 1];
        c += v[i + 2];
        d += v[i + 3];
    }
    for (; i < n; ++i) a += v[i];
    return a + b + c + d;
}

int main() {
    std::vector<double> v(50'000'000, 1.0);

    const auto t0 = std::chrono::steady_clock::now();
    const double r1 = suma_serial(v);
    const auto t1 = std::chrono::steady_clock::now();
    const double r2 = suma_cuatro(v);
    const auto t2 = std::chrono::steady_clock::now();

    auto ms = [](auto x, auto y) {
        return std::chrono::duration<double, std::milli>(y - x).count();
    };
    std::printf("serial %.2f ms -> %.0f\n", ms(t0, t1), r1);
    std::printf("cuatro %.2f ms -> %.0f\n", ms(t1, t2), r2);
    return 0;
}

En un Apple M1 Max con clang y -O2, la versión serial tarda unos 47 ms y la de cuatro acumuladores unos 12, tomando el mejor de cinco intentos: cuatro veces menos con las mismas sumas. El motivo es la dependencia: en s += x cada suma necesita la anterior. Con cuatro cadenas independientes, la unidad de coma flotante trabaja en paralelo sin usar un hilo.

El mismo programa con -O0 tarda unos 211 ms. Ese factor de cuatro indica que el compilador deja de guardar cada variable en memoria y empieza a vectorizar.

Ejemplo intermedio: localidad de caché en una matriz

Una matriz de 2048 por 2048 double ocupa 32 MB, más de lo que cabe en la caché de un núcleo. Sumarla toda es el mismo número de operaciones en cualquier orden, pero no cuesta lo mismo.

1234567891011121314151617181920212223242526272829303132333435

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <vector>

int main() {
    constexpr int n = 2048;
    std::vector<double> m(static_cast<std::size_t>(n) * n, 1.0);

    double mejor_fila = 1e9, mejor_columna = 1e9;
    double suma_fila = 0.0, suma_columna = 0.0;

    for (int repeticion = 0; repeticion < 5; ++repeticion) {
        auto t0 = std::chrono::steady_clock::now();
        double s = 0.0;
        for (int r = 0; r < n; ++r)
            for (int c = 0; c < n; ++c) s += m[static_cast<std::size_t>(r) * n + c];
        auto t1 = std::chrono::steady_clock::now();
        suma_fila = s;
        mejor_fila = std::min(mejor_fila, std::chrono::duration<double, std::milli>(t1 - t0).count());

        t0 = std::chrono::steady_clock::now();
        s = 0.0;
        for (int c = 0; c < n; ++c)
            for (int r = 0; r < n; ++r) s += m[static_cast<std::size_t>(r) * n + c];
        t1 = std::chrono::steady_clock::now();
        suma_columna = s;
        mejor_columna = std::min(mejor_columna, std::chrono::duration<double, std::milli>(t1 - t0).count());
    }

    std::printf("por fila    = %.0f  (%.2f ms)\n", suma_fila, mejor_fila);
    std::printf("por columna = %.0f  (%.2f ms)\n", suma_columna, mejor_columna);
    std::printf("factor      = %.1fx\n", mejor_columna / mejor_fila);
    return 0;
}

Medido con -O2, la pasada por filas tarda unos 4 ms y la de columnas unos 13: tres veces más. Ambas suman 4194304. Por filas avanzas de forma contigua y aprovechas cada línea de caché; por columnas saltas 16 KB entre un elemento y el siguiente.

La conclusión es incómoda: el orden de los bucles es una decisión de rendimiento. En una matriz guardada por filas, deja que el índice de columna sea el que varía más rápido. Es gratis y suele ser la optimización más rentable.

Visualización: cómo crece el trabajo con los datos

Antes de cronometrar nada conviene saber cuántas operaciones vas a pedir. La traza siguiente cuenta el trabajo de una multiplicación de matrices ingenua, que hace una multiplicación por cada terna de índices.

—

Fíjate en el patrón: cada vez que duplicas el tamaño, el trabajo se multiplica por ocho. Un dataset que pasa de mil a diez mil filas no tarda diez veces más, tarda mil. Ningún speedup de diez núcleos compensa ese salto: primero cambia el algoritmo.

Caso práctico: perfilado con perf e Instruments

Un cronómetro dice cuánto tarda el programa; un perfilador, en qué función. perf viene con Linux e Instruments con macOS: muestrean la pila de llamadas y agregan los resultados sin instrumentar el código.

12345678910

# Linux: cuántas instrucciones, fallos de caché y ramas mal predichas
perf stat -e cycles,instructions,cache-misses,branch-misses ./programa

# Linux: perfil con pilas de llamadas y luego informe interactivo
perf record -g ./programa
perf report

# macOS: grabar un perfil de tiempo y abrirlo en Instruments
xcrun xctrace record --template 'Time Profiler' --launch ./programa --output perfil.trace
open perfil.trace

• Tiempo propio (self): el consumido dentro de la función, sin contar las que llama.
• Fallos de caché: si son altos en un bucle contiguo, sospecha de un acceso con salto.
• Ramas mal predichas: aparecen en condiciones difíciles de predecir dentro del bucle.

Un perfil bien leído convierte una discusión en una lista ordenada. Si la función más costosa es la que esperabas, ya sabes dónde trabajar; si no lo es, acabas de ahorrarte una optimización inútil.

Errores comunes al medir

1234

const auto t0 = std::chrono::system_clock::now();
calcular(datos);
const auto t1 = std::chrono::system_clock::now();
std::cout << (t1 - t0).count() << " ticks\n";

1234567

double mejor = 1e9;
for (int rep = 0; rep < 5; ++rep) {
    const auto t0 = std::chrono::steady_clock::now();
    consumir(calcular(datos));
    const auto t1 = std::chrono::steady_clock::now();
    mejor = std::min(mejor, std::chrono::duration<double, std::milli>(t1 - t0).count());
}

• Medir con -O0: cronometras un programa que no existe en producción. Usa -O2, las mismas opciones con las que entregas.
• Descartar el resultado: si la función devuelve algo que no se imprime ni se guarda, el compilador puede eliminarla.
• Incluir entrada y salida: std::cout dentro del bucle medido domina el tiempo. Separa el cálculo de la impresión.
• Una sola repetición: la primera pasada paga el arranque en frío. Haz cinco y quédate con la mejor.
• Comparar máquinas distintas: un portátil con el gobernador de frecuencia activo no da los mismos números que un servidor.

Buenas prácticas de optimización

• Escribe la versión clara y compruébala con datos pequeños; optimiza solo lo que el perfil señale.
• Elige el algoritmo antes que el microdetalle: O(n log n) feo gana a O(n²) elegante.
• Recorre los datos en el orden en que están guardados; en matrices por filas, el índice de columna varía más rápido.
• Compila con -O2 y, si el bucle es numérico, prueba -march=native para permitir instrucciones del procesador.
• Prefiere std::vector a contenedores con nodos dispersos cuando domina el recorrido secuencial.
• Mide el antes y el después con el mismo binario y anota el número.
• No sacrifiques claridad por un cinco por ciento: el código se lee muchas más veces de las que se ejecuta.

Ejercicios

Tres prácticas cortas: medir tres formas de lo mismo, arreglar un recorrido que desperdicia caché y completar un cronómetro.

const auto inicio = std::chrono::::now();
trabajo_pesado(datos);
const auto fin = std::chrono::steady_clock::now();

const double ms = std::chrono::duration<double, std::milli>(fin - ).();
std::printf("%.2f ms\n", );

Soluciones explicadas

En el primer ejercicio ninguna versión gana. Con -O2 el compilador reduce las tres a un bucle equivalente y el tiempo lo fija el ancho de banda, no la sintaxis. Medido con -O0 habrías aprendido algo falso sobre range-for.

En el segundo, el vector auxiliar cambia el patrón de acceso: en lugar de pedir un double y saltar, lees una fila completa seguida. Ese patrón se llama bloqueo y es la base de las bibliotecas de álgebra lineal: si un cálculo no cabe en caché, se parte en trozos que sí quepan.

Resumen

• Optimizar es reducir trabajo y comprobarlo con una medición; sin número antes y después no hay optimización.
• Big-O describe el crecimiento: pasar de O(n²) a O(n log n) vence a cualquier microoptimización.
• Cada línea de caché trae ocho double contiguos: aprovéchalos.
• Recorrer una matriz por filas puede ser tres veces más rápido que por columnas con las mismas operaciones.
• std::chrono::steady_clock, varias repeticiones y el mejor tiempo: la forma mínima de medir bien.
• Compila con -O2 al medir: -O0 mide un programa que nunca vas a entregar.
• perf e Instruments dicen en qué función se va el tiempo; el cronómetro dice cuánto.

Evaluación

12345678

import time
import numpy as np

x = np.ones(50_000_000)
t0 = time.perf_counter()
s = x.sum()
t1 = time.perf_counter()
print(f"{s:.0f} en {1000 * (t1 - t0):.1f} ms")

12345

std::vector<double> x(50'000'000, 1.0);
const auto t0 = std::chrono::steady_clock::now();
double s = 0.0;
for (double v : x) s += v;
const auto t1 = std::chrono::steady_clock::now();