Con el código afinado (05-01) y la memoria bajo control (05-02), queda el recurso que hasta ahora hemos ignorado: un procesador moderno tiene 4, 8 o 16 núcleos, y todo lo que hemos escrito en el curso usa exactamente uno. Esta lección enseña a repartir el trabajo — cuándo hacerlo, cómo hacerlo en Python y, sobre todo, cuándo no hacerlo. Porque paralelizar no es gratis: exige clasificar la tarea (¿espera o calcula?), sortear una peculiaridad famosa de Python llamada GIL, pagar costes ocultos de arranque y comunicación, y aceptar un techo matemático — la ley de Amdahl — que ninguna cantidad de núcleos puede levantar. Sobre RutaBus veremos los dos escenarios canónicos: consultar 50 APIs de tráfico municipal (esperar) y recalcular la matriz de tiempos de toda la red (calcular), cada uno con su herramienta correcta. La lección cierra, además, el módulo: al final recapitularemos el método completo del oficio de optimizar.
Contenido
- Concurrencia y paralelismo: no son lo mismo
- Clasificar antes de repartir: CPU-bound frente a I/O-bound
- El GIL de Python, explicado sin adornos
- Hilos para I/O-bound:
ThreadPoolExecutor - Procesos para CPU-bound:
ProcessPoolExecutor - Qué se paraleliza bien: problemas vergonzosamente paralelos
- La ley de Amdahl: el techo de la ganancia
- Costes ocultos y cuándo NO paralelizar
- Condiciones de carrera y
Lock - Cierre del módulo: el método completo
Concurrencia y paralelismo: no son lo mismo
Dos palabras que se confunden constantemente y nombran cosas distintas:
- Concurrencia: gestionar varias tareas a la vez, aunque no avancen simultáneamente. Un cocinero solo que atiende tres cazuelas — mientras una hierve, remueve otra — es concurrente: el progreso se entrelaza.
- Paralelismo: ejecutar varias tareas literalmente al mismo tiempo. Tres cocineros, tres cazuelas, tres fogones: el progreso es simultáneo.
| Concurrencia | Paralelismo | |
|---|---|---|
| Idea | Estructurar tareas que se solapan | Ejecutar cálculos a la vez |
| Requiere varios núcleos | No (basta uno) | Sí |
| Gana tiempo cuando... | las tareas esperan (red, disco) | las tareas calculan |
| En Python | threading, asyncio |
multiprocessing |
La distinción no es académica: es la que decide qué herramienta usar. La concurrencia aprovecha las esperas de unas tareas para avanzar otras (un solo núcleo basta, porque esperar no ocupa CPU); el paralelismo reparte cálculo entre núcleos. Y para saber cuál de las dos necesita tu problema, primero hay que clasificarlo.
Clasificar antes de repartir: CPU-bound frente a I/O-bound
Toda tarea lenta lo es por una de dos razones:
- CPU-bound (limitada por cálculo): el procesador trabaja al 100 % todo el tiempo. Más velocidad = más núcleos calculando.
- I/O-bound (limitada por entrada/salida): el procesador pasa casi todo el tiempo esperando — a la red, al disco, a una base de datos. Más velocidad = solapar las esperas.
Clasifiquemos tareas reales de RutaBus:
| Tarea | ¿Dónde se va el tiempo? | Tipo | Estrategia |
|---|---|---|---|
| Recalcular la matriz de tiempos (Dijkstra desde cada parada) | Cálculo puro sobre el grafo | CPU-bound | Procesos |
| Consultar las 50 APIs de tráfico de los municipios | Esperar respuestas HTTP (~1 s cada una) | I/O-bound | Hilos |
| Leer el fichero de fichajes de 2 GB | Esperar al disco | I/O-bound | (poco que ganar: un solo disco) |
| Generar los informes PDF del día | Cálculo (maquetar) | CPU-bound | Procesos |
| Avisar a 10.000 usuarios por push | Esperar a la pasarela de envío | I/O-bound | Hilos |
Un truco de diagnóstico: mira el monitor del sistema mientras corre la tarea. ¿Un núcleo clavado al 100 %? CPU-bound. ¿CPU aburrida y la tarea igual de lenta? I/O-bound. (Y sí: esto también es medir antes de actuar — el método de 05-01 no se toma vacaciones.)
El GIL de Python, explicado sin adornos
Aquí Python tiene una peculiaridad que hay que contar honestamente. CPython — el intérprete estándar — tiene un GIL (Global Interpreter Lock): un cerrojo global que garantiza que solo un hilo ejecuta bytecode Python a la vez. Aunque lances 8 hilos en una máquina de 8 núcleos, sus instrucciones Python se turnan sobre el cerrojo: jamás hay dos ejecutándose simultáneamente.
Consecuencias prácticas, sin adornos:
- Los hilos NO aceleran tareas CPU-bound en CPython. Ocho hilos calculando Dijkstras suman el mismo trabajo por un solo cerrojo, más el coste de turnarse: suele salir igual o más lento que en serie.
- Los hilos SÍ aceleran tareas I/O-bound. Cuando un hilo se queda esperando a la red o al disco, suelta el GIL y otro hilo avanza. Cincuenta hilos esperando cincuenta APIs se solapan de maravilla: esperar no requiere cerrojo.
- La salida para CPU-bound son los procesos. Cada proceso es un intérprete Python independiente, con su propia memoria y su propio GIL: ocho procesos sí usan ocho núcleos de verdad.
- Matices para el mapa completo: las bibliotecas en C (NumPy, mencionada en 05-02) a menudo sueltan el GIL durante sus cálculos, por lo que se saltan parcialmente la limitación; y CPython trabaja desde la versión 3.13 en un modo experimental sin GIL (free-threaded). Pero la regla que debes memorizar hoy es la de siempre en producción: hilos para esperar, procesos para calcular.
Hilos para I/O-bound: ThreadPoolExecutor
La interfaz recomendada para ambos mundos es concurrent.futures: mismos métodos (map, submit), solo cambia el ejecutor. Empecemos por las 50 APIs de tráfico:
import time
from concurrent.futures import ThreadPoolExecutor
def consultar_trafico(municipio):
"""Consulta el estado del tráfico de un municipio (~1 s de espera de red)."""
time.sleep(1.0) # simula la llamada HTTP; en real: requests.get(...)
return municipio, "fluido"
municipios = [f"Municipio-{i:02d}" for i in range(50)]
# EN SERIE: 50 llamadas × 1 s = ~50 s
inicio = time.perf_counter()
estados = dict(consultar_trafico(m) for m in municipios)
print(f"serie: {time.perf_counter() - inicio:.1f} s") # serie: 50.1 s
# CON HILOS: las 50 esperas se solapan
inicio = time.perf_counter()
with ThreadPoolExecutor(max_workers=10) as pool:
estados = dict(pool.map(consultar_trafico, municipios))
print(f"hilos: {time.perf_counter() - inicio:.1f} s") # hilos: 5.1 sQué está pasando, línea a línea:
ThreadPoolExecutor(max_workers=10)crea una piscina de 10 hilos reutilizables; elwithgarantiza que se espera a todos y se cierran al salir.pool.map(f, datos)es elmapde toda la vida, repartido: cada hilo toma un municipio, lanza la consulta y, mientras espera la respuesta (GIL liberado), otro hilo lanza la suya. Devuelve los resultados en el orden de entrada.- 50 tareas entre 10 hilos = 5 tandas de ~1 s ≈ 5 s. ¿Por qué no 50 hilos y tardar 1 s? Se puede, pero cada hilo consume recursos y las APIs reales limitan las peticiones simultáneas;
max_workerses un dial que se ajusta midiendo.
Para procesar respuestas según van llegando (en vez de esperar el orden), existe concurrent.futures.as_completed; te lo encontrarás en código real y funciona igual con ambos ejecutores.
Procesos para CPU-bound: ProcessPoolExecutor
Ahora la tarea de calcular: recalcular los tiempos mínimos de toda la red, zona a zona. Cambiar hilos por procesos es literalmente cambiar una palabra:
from concurrent.futures import ProcessPoolExecutor
def recalcular_zona(zona):
"""CPU pura: Dijkstra desde cada parada de la zona (04-05)."""
return zona["nombre"], {origen: dijkstra(zona["red"], origen)[0]
for origen in zona["red"]}
if __name__ == "__main__": # OBLIGATORIO con procesos (ver abajo)
zonas = cargar_zonas() # p. ej. 8 zonas de la red metropolitana
with ProcessPoolExecutor(max_workers=4) as pool:
matrices = dict(pool.map(recalcular_zona, zonas))Diferencias que importan respecto a los hilos:
- Cada worker es un proceso Python independiente: memoria propia, GIL propio, un núcleo de verdad para él. Cuatro procesos en cuatro núcleos ≈ 4x en cálculo puro (menos el peaje del apartado 8).
- El guardián
if __name__ == "__main__":no es decorativo: en Windows y macOS los procesos hijos reimportan tu módulo para arrancar, y sin el guardián cada hijo relanzaría la creación de la piscina — procesos engendrando procesos sin fin. - Los argumentos y resultados viajan serializados con
pickleentre procesos (no comparten memoria). Esto tiene dos consecuencias: las funciones y datos deben ser picklables (unalambdano lo es, una función de módulo sí), y mover datos grandes cuesta — lo cuantificamos en el apartado 8.
Qué se paraleliza bien: problemas vergonzosamente paralelos
No todo problema se deja repartir. El caso ideal tiene nombre propio: vergonzosamente paralelo (embarrassingly parallel) — el trabajo se divide en piezas que no necesitan nada unas de otras.
El ejemplo perfecto ya lo conocemos de 04-06: la matriz de tiempos todos-con-todos se puede construir ejecutando Dijkstra desde cada origen por separado. El Dijkstra desde Plaza Mayor no lee ni escribe nada del Dijkstra desde la Universidad: V tareas independientes, repartibles tal cual entre los núcleos:
from concurrent.futures import ProcessPoolExecutor
from functools import partial
def matriz_de_tiempos(red):
with ProcessPoolExecutor() as pool: # workers = nº de núcleos
distancias = pool.map(partial(dijkstra_desde, red), red.keys())
return dict(zip(red.keys(), distancias))(partial fija el argumento red para que map solo reparta los orígenes; dijkstra_desde(red, origen) devuelve el dict de distancias.) Con 8 núcleos y 20.000 orígenes, cerca de 8x. El contraste instructivo es Floyd-Warshall: su bucle externo en k es una dependencia secuencial — la iteración k necesita la matriz completa que dejó la k−1 (era la esencia del algoritmo en 04-06) — así que no se puede repartir por las buenas. Regla general para reconocer cada caso:
- ¿Cada pieza se calcula solo con la entrada común (la red) y sus propios datos? → vergonzosamente paralelo: simulaciones por escenario, informes por zona, un Dijkstra por origen.
- ¿Cada paso necesita el resultado del anterior? → cadena secuencial: iteraciones de Floyd-Warshall, un acumulador que depende del orden, la pila del backtracking de 03-04.
La mayoría de problemas reales están en medio: una parte repartible y una parte secuencial (leer los datos, juntar resultados). Cuánto limita esa parte secuencial tiene fórmula exacta.
La ley de Amdahl: el techo de la ganancia
Si una fracción p del tiempo de un programa es paralelizable (y la fracción 1−p es forzosamente secuencial), la aceleración máxima con n núcleos es:
S(n) = 1 / ((1 − p) + p/n)
La intuición: la parte paralela se divide entre n, pero la secuencial se paga entera, sí o sí. Números:
| p (fracción paralelizable) | n = 2 | n = 4 | n = 8 | n = 16 | n → ∞ (techo) |
|---|---|---|---|---|---|
| 50 % | 1.33x | 1.60x | 1.78x | 1.88x | 2x |
| 90 % | 1.82x | 3.08x | 4.71x | 6.40x | 10x |
| 95 % | 1.90x | 3.48x | 5.93x | 9.14x | 20x |
| 99 % | 1.98x | 3.88x | 7.48x | 13.9x | 100x |
Dos lecturas que duelen y conviene interiorizar:
- Con la mitad del programa secuencial, infinitos núcleos dan 2x. Ni uno más.
- Incluso con el 90 % paralelizable, 8 núcleos no dan 8x: dan 4.71x. El folleto del procesador vende núcleos; Amdahl reparte realidad.
Aplicado al job de la matriz de RutaBus: si cargar la red y escribir los resultados (secuencial) es el 10 % del tiempo total, el techo es 10x aunque el cluster tenga 64 núcleos. La consecuencia práctica enlaza con todo el módulo: reducir la parte secuencial (optimizándola con 05-01 y 05-02) sube el techo de p — a menudo rinde más que añadir núcleos.
Costes ocultos y cuándo NO paralelizar
Amdahl es el techo teórico; en la práctica se está aún más abajo, porque paralelizar cobra peajes:
- Arranque de procesos: crear un proceso Python cuesta decenas o cientos de milisegundos (importa módulos, inicializa el intérprete). Para una tarea de 2 segundos totales, la piscina puede costar más que el trabajo.
- Serialización (pickle): cada argumento y cada resultado se serializa, viaja y se deserializa. Enviar la red metropolitana completa (varios MB, 05-02) a cada uno de 20.000 trabajos la copia 20.000 veces. Mitigaciones: enviar referencias baratas (la zona, no el grafo entero; que cada worker cargue la red una vez), agrupar trabajos con
chunksizeenpool.map, y devolver resultados agregados en lugar de datos crudos. - Sincronización: si las tareas comparten algo (apartado 9), coordinar el acceso consume tiempo y, en el peor caso, re-secuencializa lo que se quería paralelizar.
De ahí la lista de cuándo NO paralelizar:
- Cuando el trabajo total es pequeño: el overhead supera la ganancia. Se comprueba midiendo, no estimando.
- Cuando aún no se ha optimizado en serie: paralelizar la versión con el
insobre lista de 05-01 es multiplicar trabajo inútil por 8 núcleos. El orden del módulo es el orden del método: algoritmo → código → memoria → y solo entonces, paralelizar. - Cuando la parte secuencial domina (Amdahl): con p = 50 %, complicar el código para un techo de 2x rara vez compensa.
- Cuando mover los datos cuesta más que calcularlos: tareas diminutas sobre datos enormes son el peor cliente de
pickle.
Condiciones de carrera y Lock
El precio en corrección del paralelismo se llama condición de carrera: dos hilos tocando el mismo dato a la vez, con resultado dependiente del azar del entrelazado. El ejemplo mínimo — un contador global de fichajes procesados:
import threading
contador = 0
def procesar_lote(lote):
global contador
for _ in lote:
contador += 1 # ¡NO es atómico!: leer, sumar, escribir (3 pasos)
hilos = [threading.Thread(target=procesar_lote, args=([0] * 100_000,)) for _ in range(4)]
for h in hilos: h.start()
for h in hilos: h.join()
print(contador) # esperado 400000; obtenido p. ej. 273481 — y cada vez uno distintocontador += 1 son tres operaciones (leer el valor, sumarle 1, escribirlo). Si dos hilos leen "1000" a la vez, ambos escriben "1001": una suma se pierde. El GIL no protege de esto — garantiza un hilo por instrucción de bytecode, pero puede cambiar de hilo entre las tres operaciones. La solución es un Lock (cerrojo) que convierte la secuencia en exclusiva:
cerrojo = threading.Lock()
def procesar_lote(lote):
global contador
for _ in lote:
with cerrojo: # solo un hilo dentro a la vez
contador += 1 # ahora sí: 400000, siempreDos observaciones y cerramos, porque los sistemas distribuidos quedan fuera de este curso:
- El
Lockre-secuencializa la sección que protege: si casi todo el trabajo pasa por el cerrojo, adiós paralelismo (Amdahl, otra vez). Mejor diseño: que cada hilo acumule en su contador local y se sumen al final. - La mejor condición de carrera es la que no puede existir: por eso los ejemplos de esta lección reparten trabajo sin estado compartido (cada tarea recibe sus datos, devuelve su resultado, y
mapjunta). Los procesos, al no compartir memoria, hacen de esa disciplina la opción por defecto.
Cierre del módulo: el método completo
Con esta lección se completa el oficio que prometía el final del Módulo 4. El método, en orden — y el orden es el método:
| Paso | Pregunta | Herramientas | Lección |
|---|---|---|---|
| 1. Medir | ¿Dónde se va el tiempo/la memoria? | perf_counter, timeit, cProfile, tracemalloc |
05-01, 05-02 |
| 2. Algoritmo | ¿Es la estrategia y la estructura correcta? | Módulos 2–4 (análisis, diseño, clásicos) | M2–M4 |
| 3. Código | ¿La implementación desperdicia trabajo? | jerarquía: hoisting, lru_cache, idiomático |
05-01 |
| 4. Memoria | ¿Materializa o retiene de más? | generadores, lotes, __slots__, representación |
05-02 |
| 5. Paralelizar | ¿Queda cálculo repartible que lo justifique? | concurrent.futures; Amdahl como techo |
05-03 |
Cada paso multiplica los siguientes: paralelizar (paso 5) un algoritmo equivocado (paso 2) reparte el error entre 8 núcleos; y optimizar la parte secuencial (pasos 3–4) es lo que sube el techo de Amdahl del paso 5. Y todo empieza y termina midiendo: la medición inicial dice dónde actuar y la final demuestra que sirvió.
Errores Comunes y Consejos
- Usar hilos para acelerar cálculo en CPython. El error clásico del GIL: 8 hilos calculando rinden como 1 (o peor). Hilos para esperar, procesos para calcular.
- Olvidar
if __name__ == "__main__":con procesos. En Windows produce errores de arranque o una cascada de procesos. Va siempre, sin excepciones. - Pasar datos enormes o no picklables a los workers. Una
lambdacomo función de trabajo falla; un grafo de 100 MB como argumento por tarea convierte la CPU ganada en serialización perdida. Funciones de módulo y argumentos ligeros. - Paralelizar antes de optimizar en serie. Multiplicar por 4 un código 100 veces más lento de lo necesario es quedarse 25 veces por debajo de la versión en serie bien escrita. Pasos 1–4 primero.
- Proteger de más o de menos. Sin
Lock, resultados corruptos e intermitentes (los peores bugs de reproducir); con unLockalrededor de todo, un programa secuencial disfrazado de paralelo. La salida buena suele ser rediseñar para no compartir estado. - Consejo: cronometra siempre las tres versiones — serie, hilos, procesos — con datos realistas, como hicimos con las APIs de tráfico. La tabla de tres números decide sola, y a veces la ganadora es la versión en serie.
Ejercicios
Ejercicio 1. Clasifica estas tareas de RutaBus como CPU-bound o I/O-bound y asigna a cada una la herramienta adecuada (ThreadPoolExecutor, ProcessPoolExecutor, o "en serie, no compensa"), justificando en una línea: (a) geocodificar 2.000 direcciones llamando a un servicio web externo; (b) comprimir los 365 ficheros de fichajes del año (compresión = cálculo intenso); (c) validar 500 fichajes contra un set en memoria; (d) ejecutar la simulación de demanda con 12 escenarios de parámetros independientes.
Ejercicio 2. El recálculo nocturno de RutaBus tarda 200 s: 20 s de carga y escritura (secuencial) y 180 s de Dijkstras independientes (paralelizable). (a) Calcula p y la aceleración con 4 y con 16 núcleos según Amdahl, y el techo con infinitos. (b) Un compañero reduce la carga de 20 s a 5 s aplicando 05-02 (lectura por generador). Recalcula el techo. ¿Qué enseña esto sobre el orden del método?
Ejercicio 3. Este código paralelo con hilos registra las paradas saturadas detectadas por 4 analizadores concurrentes, y a veces pierde avisos. Explica la condición de carrera exacta y da dos soluciones distintas: una con Lock y otra sin estado compartido (rediseño con ThreadPoolExecutor.map).
avisos = []
def analizar(zona):
for parada in zona:
if parada["ocupacion"] > 0.9:
avisos.append(f"Saturada: {parada['nombre']}")Soluciones
Solución 1. (a) I/O-bound → ThreadPoolExecutor: 2.000 esperas de red que se solapan; el GIL se libera durante cada llamada. (b) CPU-bound → ProcessPoolExecutor: comprimir es cálculo puro y los 365 ficheros son independientes (vergonzosamente paralelo). (c) En serie: 500 consultas O(1) a un set son microsegundos; cualquier piscina cuesta más que el trabajo (overhead > ganancia). (d) CPU-bound → ProcessPoolExecutor: 12 simulaciones independientes, ideal para map; con más de 12 núcleos, el límite pasa a ser el número de escenarios.
Solución 2. (a) p = 180/200 = 0,90. S(4) = 1/(0,1 + 0,9/4) = 3,08x (65 s); S(16) = 1/(0,1 + 0,9/16) = 6,4x (31 s); techo S(∞) = 1/0,1 = 10x (20 s: la parte secuencial entera). (b) Con 5 s secuenciales: p = 180/185 ≈ 0,973 → techo 1/(5/185) = 37x, y S(16) sube a ~11,6x. Moraleja: optimizar la parte secuencial con las técnicas de 05-01/05-02 elevó el techo de 10x a 37x — más de lo que jamás daría añadir núcleos con el techo antiguo. Los pasos 3–4 del método van antes que el 5 también por matemáticas, no solo por prudencia.
Solución 3. La carrera está en avisos.append(...) desde 4 hilos: aunque cada append individual es atómico en CPython, el patrón general de acumular en estructuras compartidas desde varios hilos es frágil (basta cambiar a avisos += [...], o a un contador, para perder actualizaciones: leer-modificar-escribir entrelazado). Solución 1, cerrojo:
avisos, cerrojo = [], threading.Lock()
def analizar(zona):
for parada in zona:
if parada["ocupacion"] > 0.9:
with cerrojo:
avisos.append(f"Saturada: {parada['nombre']}")Solución 2, sin estado compartido (preferible): cada tarea devuelve sus avisos y el hilo principal los junta — no hay nada que proteger porque no hay nada compartido:
def analizar(zona):
return [f"Saturada: {p['nombre']}" for p in zona if p["ocupacion"] > 0.9]
with ThreadPoolExecutor(max_workers=4) as pool:
avisos = [a for lote in pool.map(analizar, zonas) for a in lote]Es el patrón de toda la lección: repartir entrada, devolver resultados, agregar al final.
Conclusión
Este módulo ha recorrido el oficio completo de convertir un buen algoritmo en un programa rápido: medir antes de tocar nada (05-01), exprimir el código por niveles de impacto, domar la memoria cuando es ella la que escasea (05-02), y por último — solo por último — repartir el cálculo entre núcleos, con los hilos para las esperas, los procesos para el cálculo, la ley de Amdahl como techo y los costes de serialización y sincronización como letra pequeña. El método queda destilado en cinco pasos que conviene recitar en orden: medir → algoritmo → código → memoria → paralelizar. Con esto, el curso ha completado su arsenal: sabemos analizar (M1–M2), diseñar (M3), reconocer los clásicos (M4) y optimizar (M5). Lo que no se ha completado todavía es la soltura, y esa no se lee: se entrena. El Módulo 6 es exactamente eso — baterías de ejercicios de complejidad, de diseño y de optimización, y unos proyectos finales que juntan todas las piezas sobre RutaBus —, porque la diferencia entre conocer estas herramientas y pensar con ellas se cierra practicando, y ahí es donde vamos ahora.
Curso de Análisis y Diseño de Algoritmos
Módulo 1: Introducción a los Algoritmos
Módulo 2: Análisis de Algoritmos
- Análisis de Complejidad Temporal
- Análisis de Complejidad Espacial
- Casos de Complejidad: Mejor, Peor y Promedio
Módulo 3: Estrategias de Diseño de Algoritmos
Módulo 4: Algoritmos Clásicos
- Búsqueda Binaria
- Ordenamiento por Inserción
- Ordenamiento por Mezcla (Merge Sort)
- Ordenamiento Rápido (Quick Sort)
- Algoritmo de Dijkstra
- Algoritmo de Floyd-Warshall
