Tercera bateria: optimització. Aquí exercitem el Mòdul 5 complet —mesurar primer (05-01), memòria (05-02) i paral·lelització (05-03)— fent servir l'anàlisi del Mòdul 2 com a eina de diagnòstic. El material de treball és codi de RutaBus lent però realista: el tipus de codi que de debò apareix en producció, no exemples de laboratori.

Com treballar aquesta lliçó: abans de mirar cada solució, escriu el teu propi diagnòstic seguint el mètode destil·lat al final del Mòdul 5 — mesurar → algorisme → codi → memòria → paral·lelitzar — i només després compara. Si tens Python a mà, mesura de debò amb timeit versions abans/després amb dades sintètiques: comprovar que la teva estimació de guany es compleix (o no) és la meitat de l'aprenentatge.

1. Llegir un perfil: decidir on atacar primer.
2. L'informe de puntualitat lent: la jerarquia completa aplicada.
3. Memòria: el job nocturn que s'ofega.
4. Paral·lelitzo o no?: classificar CPU/E-S i aplicar Amdahl amb números.
5. Quan NO optimitzar.

Dificultat: bàsica

El procés tancament_diari() de RutaBus triga 21,5 segons. Abans de tocar codi, algú va fer el que tocava (05-01): passar-li cProfile. Sortida resumida:

Preguntes: (a) quina funció ataques primer i per què?; (b) és la que més vegades es crida?; (c) 180.000 crides amb percall gairebé nul però tottime enorme: això suggereix una optimització de nivell algorisme o de nivell micro en la jerarquia de 05-01?; (d) si deixessis cerca_tarifa en temps menyspreable, quin seria l'speedup màxim del tancament?

(a) cerca_tarifa: acumula 17,8 dels 21,5 segons (el 83 %). La columna que mana és tottime (temps propi de la funció), com vam veure a 05-01. Optimitzar qualsevol altra cosa primer és treballar sobre el 17 % restant.

(b) Trampa evitada: arrodoneix_import es crida les mateixes 180.000 vegades i només acumula 0,9 s. El nombre de crides no és el criteri; el temps total sí.

(c) Nivell algorisme. Cada crida individual és barata (percall ≈ 0,0001 s) però es fa 180.000 vegades amb un cost que, a jutjar pel total, creix amb les dades: el patró típic és una cerca lineal repetida (una tarifa cercada amb in/bucle sobre una llista per cada fitxatge → O(n·m), com vam analitzar a 02-01). La solució de nivell algorisme és canviar l'estructura: un dict de tarifes converteix cada cerca en O(1). Microoptimitzar l'interior de cerca_tarifa (nivell micro) deixaria intacte l'O(n·m).

(d) Temps restant ≈ 21,5 − 17,8 = 3,7 s → speedup màxim ≈ 21,5 / 3,7 ≈ ×5,8. És la mateixa aritmètica de la llei d'Amdahl (05-03) aplicada a optimització seqüencial: la part que no toques acota el guany total.

Error típic: obrir el codi i "optimitzar el que sembla lent" sense perfil. El perfil aquí desmenteix dues intuïcions raonables: ni l'ordenació (2,1 s, a la vista i amb nom sospitós!) ni la funció més cridada eren el problema.

Dificultat: mitjana

Aquest informe triga minuts amb els volums actuals (n ≈ 200.000 arribades, m ≈ 500 parades crítiques, i ~30 % de les arribades passen en parades crítiques):

Tasques: (a) deriva la complexitat actual amb l'anàlisi de 02-01, identificant el cost de (1), (2) i (3); (b) aplica la jerarquia de 05-01: què canvies, en quin ordre i a quin nivell és cada canvi; (c) reescriu la funció; (d) estima el guany amb els números donats.

Pista: un dels tres problemes és ordres de magnitud pitjor que els altres dos. Troba'l primer: és el que decideix per on començar.

(a) Diagnòstic.

• (1) parada in parades_critiques sobre llista: O(m) per iteració → O(n·m) total = 200.000 × 500 = 10⁸ comparacions.
• (2) max(...) recorre les n arribades dins del bucle, i és invariant: calcula el mateix a cada passada. S'executa a cada encert (~0,3·n = 60.000 vegades) × O(n) → 1,2 × 10¹⁰ operacions. Aquest és el monstre.
• (3) Concatenació de cadenes: cada += copia l'informe sencer (02-01). Amb k ≈ 60.000 línies, cost Θ(k²) en caràcters copiats: ~10⁹–10¹⁰ segons la longitud de línia.

(b) Pla segons la jerarquia (05-01: primer el que més rendeix):

1. Algorisme — treure l'invariant: pitjor es calcula una vegada, fora del bucle. Elimina el terme 10¹⁰.
2. Algorisme/estructura — llista → set: set(parades_critiques) una vegada (O(m)) i cada consulta passa a O(1). Elimina el 10⁸.
3. Codi — acumular i join: construir una llista de línies i unir-les al final, Θ(longitud total) en lloc de Θ(k²).

(c) Reescriptura:

(d) Guany. Abans: dominat per (2), ~10¹⁰ operacions elementals — desenes de segons o minuts en CPython. Després: Θ(n + m) ≈ 4 × 10⁵ operacions — desenes de mil·lisegons. Guany estimat: 3–4 ordres de magnitud. I el pas final obligatori del mètode: confirmar-ho mesurant amb timeit sobre dades sintètiques de la mateixa mida (05-01) — les estimacions es comproven, no es declaren.

Errors típics: (1) començar pel join perquè "la concatenació de strings és el que és famós" — aquí era el tercer problema en magnitud; la jerarquia existeix per ordenar els atacs; (2) no reconèixer (2) com a invariant perquè "és dins d'un if"; (3) convertir a set dins del bucle (if parada in set(parades_critiques)), que torna a ser O(m) per iteració amb cost extra de construcció — pitjor que la llista original.

Dificultat: mitjana

Aquest job processa el fitxer de fitxatges del dia (diversos GB) i mor amb MemoryError al servidor de 8 GB:

Preguntes: (a) quantes estructures proporcionals al fitxer conviuen en memòria en el pitjor moment?; (b) reescriu-lo perquè la memòria auxiliar sigui O(k) amb k = 10, fent servir el que hem vist a 05-02 i el top-k de 04-04; (c) amb quina eina confirmaries la millora?; (d) en quina situació no n'hi hauria prou amb generadors i caldria processar per lots?

(a) En el moment del sorted conviuen: linies (totes les cadenes), fitxatges (tots els objectes), valids (referències a gairebé tots ells) i la llista nova que sorted construeix. Entre 3 i 4 estructures O(n) simultànies — amb un fitxer de diversos GB, el MemoryError està garantit. Nota de 02-02: valids guarda referències, no còpies dels objectes, però linies i fitxatges sí que són contingut nou cadascuna.

(b) El fitxer es pot recórrer mandrosament (un fitxer obert ja és un iterador línia a línia) i el top-10 no necessita ordenar res: és un problema de k més grans, i per a k petit en streaming l'eina és un heap (04-05 ens va donar heapq; 04-04 ens va donar l'alternativa quickselect, que aquí no serveix perquè exigeix tenir la llista sencera en memòria):

Memòria auxiliar: O(k) — el generador produeix els fitxatges d'un en un (05-02) i nlargest només reté els 10 millors vistos. Temps: Θ(n log k) davant del Θ(n log n) d'ordenar-ho tot; amb k = 10, a la pràctica lineal.

(c) tracemalloc (05-02): mesurar el pic de memòria de totes dues versions amb un fitxer de prova. La versió original fa pic en gigabytes; la nova, en kilobytes. (Per al temps, timeit; per saber on es gasta, cProfile — cada eina respon una pregunta diferent.)

(d) Quan el càlcul necessita agrupar un estat que també creix sense límit — per exemple, "import total per bitllet únic" amb centenars de milions de bitllets diferents: el dict acumulador acabaria sent el nou problema. Aquí entren els lots de 05-02: processar per trams (per hora, per línia), bolcar resultats parcials i combinar després — que és exactament l'ordenació externa que vam esbossar a 04-03.

Errors típics: (1) "arreglar-ho" canviant readlines() per list(f) — la mateixa materialització amb una altra sintaxi; (2) construir el generador i després fer-li sorted(valids, ...): sorted materialitza l'iterable complet i la millora s'evapora en silenci; (3) convertir el generador en llista "un moment, per depurar" i oblidar-lo allà.

Dificultat: alta

Dos jobs de RutaBus són candidats a paral·lelització:

• Job A: consulta l'API municipal de trànsit per a 60 zones; cada crida triga ~0,5 s, gairebé tot espera de xarxa, i les respostes es processen en microsegons.
• Job B: recalcula Dijkstra des de cadascuna de les 300 parades de la xarxa (CPU pura; els orígens són independents entre si). Mesurat: el 90 % del temps són els Dijkstra; el 10 % restant (carregar el graf i bolcar resultats) és seqüencial.

Preguntes: (a) classifica cada job (CPU-bound / I-O-bound) i tria fils o processos, justificant-ho amb el GIL (05-03); (b) quin executor de concurrent.futures faries servir en cada cas?; (c) per al Job B, calcula amb la llei d'Amdahl l'speedup amb 4 i amb 8 processos, i el límit teòric amb infinits; (d) la màquina té 8 nuclis: val la pena configurar 16 processos?

(a) Job A: I/O-bound — el temps se'n va esperant la xarxa, no computant. Durant una espera d'E/S el fil allibera el GIL, així que els fils funcionen perfectament (i són més barats que processos). Job B: CPU-bound — el GIL impedeix que dos fils executin bytecode Python alhora, així que els fils no aportarien res; calen processos, cadascun amb el seu intèrpret i el seu GIL. I és el cas ideal: com vam veure a 05-03, Dijkstra per origen és vergonyosament paral·lel — zero dependències ni comunicació entre tasques.

(b) Job A → ThreadPoolExecutor (p. ex. max_workers=20; en ser espera de xarxa, més workers que nuclis és raonable). Job B → ProcessPoolExecutor amb max_workers ≈ nombre de nuclis:

(c) Amdahl (05-03) amb fracció paral·lelitzable p = 0,9: S(N) = 1 / ((1 − p) + p/N).

Amb 8 processos no obtens ×8: obtens ×4,7, perquè el 10 % seqüencial no s'accelera i pesa cada cop més en proporció.

(d) No. Dues raons que se sumen: (i) Amdahl dona S(16) = 1/(0,1 + 0,05625) ≈ ×6,4 teòric — passar de 8 a 16 processos afegiria com a molt un ×1,36 més; (ii) aquest teòric ni tan sols s'assoleix: amb 8 nuclis físics, 16 processos CPU-bound competeixen pels mateixos nuclis i afegeixen sobrecost de canvis de context i memòria (cada procés duplica el graf). Més workers que nuclis només té sentit quan hi ha espera (Job A), no quan hi ha còmput.

Error típic: paral·lelitzar com a primer recurs. La jerarquia del Mòdul 5 posa paral·lelitzar al final per alguna cosa: si dins de dijkstra_des_de hi hagués una llista on toca un heap, arreglar això donaria més que els 8 nuclis junts — i les dues millores es multipliquen si fas primer la barata.

Dificultat: mitjana

Dues situacions reals a l'equip de RutaBus:

• Cas 1: informe_mensual.py s'executa una vegada al mes, triga 4 segons i són 80 línies llegibles. Un company proposa dedicar 2 dies a reescriure'l amb multiprocessing, lru_cache i __slots__ per deixar-lo en 0,5 s.
• Cas 2: l'endpoint cerca_connexio de l'app respon en 900 ms i rep 50.000 peticions al dia. Els usuaris es queixen de lentitud. Ningú no l'ha perfilat.

Preguntes: (a) quin dels dos mereix esforç d'optimització? Quantifica-ho; (b) què faries primer en el cas que sí que ho mereix?; (c) quins riscos concrets té optimitzar el Cas 1?

(a) El Cas 2, sense discussió. Quantifiquem-los tots dos:

• Cas 1: estalvi de 3,5 s/mes = 42 segons l'any, a canvi de 2 dies d'enginyeria. Encara que el sou fos gratis, no recuperes la inversió ni en un segle.
• Cas 2: 50.000 × 0,9 s = 45.000 s = 12,5 hores diàries d'espera agregada d'usuaris, en el camí crític de l'experiència de l'app. Cada 100 ms que rasquis són ~1,4 hores diàries retornades als usuaris.

(b) Mesurar-lo (05-01): cProfile sobre l'endpoint amb peticions representatives, abans de tocar cap línia. "Ningú no l'ha perfilat" vol dir que ningú no sap si els 900 ms són la consulta de rutes (un Dijkstra sobre una representació maldestra del graf? una cerca lineal de parades?), la base de dades o la serialització. Optimitzar sense perfil és apostar; amb 12,5 hores/dia en joc, s'aposta poc i es mesura molt. Després, la jerarquia: algorisme → codi → memòria → paral·lelitzar.

(c) Riscos del Cas 1: (i) bugs nous en un procés que funcionava — tot canvi té probabilitat d'error, i aquí sense cap benefici que ho compensi; (ii) mantenibilitat: 80 línies llegibles es converteixen en multiprocessing amb estat compartit, que el company següent trigarà hores a entendre (i recordem de 05-03 que compartir estat entre processos exigeix Lock i serialització: complexitat real); (iii) cost d'oportunitat: aquests 2 dies no es dediquen al Cas 2, que sí que sagna. La regla del Mòdul 5 era exactament aquesta: el codi optimitzat es paga en llegibilitat i risc, així que s'optimitza el que és al camí crític i es deixa en pau el que no.

Matís final per no convertir la regla en dogma: si l'informe mensual passés a executar-se cada 5 minuts, o el seu fitxer d'entrada es multipliqués per 100, l'anàlisi canvia — les decisions d'optimització caduquen amb les dades, per això es recolzen en números mesurats i no en opinions.

Error típic: optimitzar per satisfacció tècnica ("sé fer-ho més ràpid") en lloc de per impacte. La pregunta professional no és "pot anar més ràpid?" — gairebé tot pot — sinó "quant val que vagi més ràpid i quant costa aconseguir-ho?".

Has aplicat el mètode complet del Mòdul 5 sobre codi aliè i realista: llegir un perfil i triar l'objectiu per tottime i no per intuïció; atacar un informe lent en l'ordre correcte (invariant fora del bucle, llista → set, join) estimant guanys d'ordres de magnitud; convertir un job golut de memòria en un flux O(k) amb generadors i heap; decidir fils o processos amb el GIL i posar números a l'speedup amb Amdahl; i —l'habilitat més rendible de totes— reconèixer quan la millor optimització és no optimitzar.

Ja tens els tres músculs entrenats per separat: anàlisi (06-01), disseny (06-02) i optimització (06-03). A l'última lliçó del curs els farem servir tots alhora: tres projectes finals que construeixen, de principi a fi, peces completes de RutaBus.