Concepto clave

En sistemas de baja latencia, la optimización de algoritmos y estructuras de datos no es solo una mejora marginal, sino un requisito fundamental para cumplir con SLAs (Service Level Agreements) críticos. La diferencia entre un algoritmo O(n²) y uno O(n log n) puede significar milisegundos versus microsegundos en procesamiento de datos financieros o telecomunicaciones.

Rust ofrece herramientas únicas para esta optimización: ownership y borrowing eliminan garbage collection, mientras que zero-cost abstractions permiten escribir código de alto nivel sin penalización de performance. La clave está en entender cómo el compilador traduce tus estructuras a código máquina eficiente.

En trading de alta frecuencia, 100 microsegundos de latencia pueden representar millones en pérdidas de oportunidad.

Cómo funciona en la práctica

Consideremos un sistema que procesa órdenes de mercado. Necesitamos mantener un libro de órdenes ordenado por precio y tiempo. Un enfoque ingenuo usaría Vec y sort(), pero en Rust podemos optimizar:

use std::collections::BTreeMap;

struct OrderBook {
    bids: BTreeMap<Price, Vec<Order>>,
    asks: BTreeMap<Price, Vec<Order>>,
}

impl OrderBook {
    fn add_order(&mut self, order: Order) {
        let price = order.price;
        let side = order.side;
        
        match side {
            Side::Bid => self.bids.entry(price).or_insert_with(Vec::new).push(order),
            Side::Ask => self.asks.entry(price).or_insert_with(Vec::new).push(order),
        }
    }
    
    fn get_best_bid(&self) -> Option<&Order> {
        self.bids.last_key_value().and_then(|(_, orders)| orders.last())
    }
}

BTreeMap mantiene las órdenes ordenadas por precio (O(log n) para inserciones), mientras que Vec en cada entrada maneja el orden por tiempo (O(1) para push). Esta estructura combinada es más eficiente que una única colección ordenada por múltiples criterios.

Caso de estudio

Un sistema de matching de órdenes para una bolsa procesa 100,000 órdenes/segundo con latencia máxima de 50μs. El equipo identificó un cuello de botella en la búsqueda de órdenes por ID.

Implementación inicial:

struct OrderStore {
    orders: Vec<Order>,
}

impl OrderStore {
    fn find_order(&self, id: OrderId) -> Option<&Order> {
        self.orders.iter().find(|order| order.id == id)  // O(n)
    }
}

Optimización:

use std::collections::HashMap;

struct OrderStore {
    orders: Vec<Order>,
    index: HashMap<OrderId, usize>,  // ID -> índice en Vec
}

impl OrderStore {
    fn find_order(&self, id: OrderId) -> Option<&Order> {
        self.index.get(&id).map(|&idx| &self.orders[idx])  // O(1) promedio
    }
    
    fn add_order(&mut self, order: Order) {
        let idx = self.orders.len();
        self.index.insert(order.id, idx);
        self.orders.push(order);
    }
}

Resultados:

Métrica	Antes	Después
Latencia p95	85μs	32μs
CPU usage	45%	28%
Memory overhead	8MB	12MB

El trade-off: +4MB de memoria por -53μs de latencia, aceptable en este contexto.

Errores comunes

Usar clone() innecesariamente: En bucles críticos, cada clone() añade overhead. Usa referencias (&) o reestructura el código para evitar copias.
Ignorar cache locality: Structs con Vec de structs pequeños son más eficientes que Vec de punteros a structs heap-allocated. Agrupa datos relacionados.
Abusar de dynamic dispatch: trait objects (Box<dyn Trait>) añaden indirección. Usa enums o generics cuando sea posible.
No medir antes de optimizar: Usa perf, flamegraph, o criterion para identificar cuellos de botella reales, no supuestos.
Optimizar para el caso general: En baja latencia, optimiza para el camino feliz (hot path). Usa unlikely()/likely() hints cuando sea relevante.

Checklist de dominio

¿Has analizado el algoritmo con notación Big-O para operaciones críticas?
¿Usas la estructura de datos más adecuada (Vec, HashMap, BTreeMap) para cada caso?
¿Minimizas allocations en bucles críticos?
¿Has considerado cache locality en el layout de tus structs?
¿Evitas dynamic dispatch en hot paths?
¿Has benchmarkeado con cargas realistas?
¿Documentas los trade-offs de performance/memoria?

Optimización de un sistema de cache en memoria

Implementa un sistema de cache LRU (Least Recently Used) optimizado para baja latencia que soporte 1,000,000 de operaciones/segundo.

Crea una struct LRUCache<K, V> con capacidad configurable
Implementa get(&mut self, key: &K) -> Option<&V> que devuelva el valor y actualice el orden de uso (O(1) promedio)
Implementa put(&mut self, key: K, value: V) -> Option<V> que inserte o actualice, eliminando el menos usado si se excede capacidad
Usa HashMap<K, NodeRef> y una lista doblemente enlazada para orden
Benchmarkea con criterion para 100k operaciones random
Optimiza: evita allocations en operaciones frecuentes, usa Option::take() para mover valores

Pistas

Considera usar RawTable de hashbrown para mejor control sobre el hashing
Implementa la lista enlazada con indices en un Vec para mejor cache locality
Usa unsafe cuidadosamente solo donde measurements muestren bottleneck

Evalua tu comprension

Completa el quiz interactivo de arriba para ganar XP.

Optimización de Algoritmos y Estructuras de Datos