Lidsky řečeno
Stěhuješ byt a chceš to mít rychleji. Můžeš trénovat rychlejší zavazování tkaniček. Nebo si všimneš, že většinu dne čekáš na výtah, a začneš nosit krabice po dvou. Program je stejný: skoro vždycky brzdí jedno konkrétní místo a skoro nikdy to není to, které bys tipoval. Proto se nejdřív měří.
Nejdřív změř, potom měň
Odhad je u výkonu špatný rádce. Postup, který funguje:
- Řekni si, co znamená „dost rychlé“. Bez cíle nevíš, kdy skončit.
- Změř program na realistických datech.
- Najdi nejpomalejší místo.
- Oprav jednu věc.
- Změř znovu. Když se nic nezlepšilo, změnu vrať.
Nejjednodušší měřidlo jsou stopky kolem kusu kódu. Správné hodiny jsou time.perf_counter(): mají vysoké rozlišení a nikdy necouvnou. Nepoužívej na to time.time(), ta se může změnit i uprostřed měření, když systém seřídí hodiny.
import time
from contextlib import contextmanager
@contextmanager
def stopky(nazev):
zacatek = time.perf_counter()
try:
yield
finally:
trvani = time.perf_counter() - zacatek
print(f"{nazev}: {trvani * 1000:.2f} ms")
with stopky("součet čtverců"):
vysledek = sum(i * i for i in range(200_000))
print(vysledek)
Spusť to několikrát. Čísla se pokaždé trochu liší, protože počítač dělá i jiné věci. Python tady navíc běží v prohlížeči, takže absolutní časy budou jiné než u tebe na počítači. Porovnávej proto poměry, ne samotná čísla.
Kolik může oprava přinést, říká Amdahlův zákon:
zrychlení celku = 1 / ((1 - p) + p / s)
p = jaký podíl času zabírá část, kterou zrychluješ
s = kolikrát ji zrychlíšKdyž část zabírá 10 % času a zrychlíš ji desetkrát, celý program je rychlejší jen asi 1,1krát. Když zabírá 80 % a zrychlíš ji pouze dvakrát, získáš asi 1,67krát. Malé zlepšení velké části poráží velké zlepšení části malé.
Funkce zabírá 5 % běhu programu. Podaří se ti ji zrychlit stokrát. Co se stane s celkem?
Zbylých 95 % času zůstalo beze změny. Dosazením vyjde 1 / (0.95 + 0.05 / 100), tedy asi 1,05krát.
timeit: férové srovnání dvou zápisů
Na krátké kousky kódu jsou stopky moc hrubé. Modul timeit spustí kód mnohokrát a změří součet. Část setup se provede předem a do času se nepočítá. repeat celé měření zopakuje a ty vezmeš nejmenší hodnotu: pomalejší běhy zdržel někdo jiný, nejrychlejší je nejblíž skutečné ceně kódu.
import timeit
setup = "seznam = list(range(20_000)); mnozina = set(seznam)"
v_seznamu = min(timeit.repeat("-1 in seznam", setup, repeat=3, number=100))
v_mnozine = min(timeit.repeat("-1 in mnozina", setup, repeat=3, number=100))
print("množina je rychlejší:", v_mnozine < v_seznamu)
print("aspoň stokrát:", v_seznamu > v_mnozine * 100)
množina je rychlejší: True aspoň stokrát: True
Hledání v seznamu prochází prvek po prvku, množina jde díky hashi rovnou na místo. Rozdíl roste s velikostí dat, jak ukázala lekce o složitosti.
Z příkazové řádky je to ještě kratší:
python -m timeit -s "data = list(range(1000))" "sum(data)"cProfile: kam čas opravdu teče
Profiler sleduje běžící program a zapisuje, které funkce se volaly, kolikrát a jak dlouho trvaly. Nemusíš hádat. Modul cProfile je součástí Pythonu.
Tady je funkce, která ze seznamu slov vybírá unikátní. Nejdřív se podíváme na počty volání, ty jsou při každém běhu stejné.
import cProfile
import pstats
def normalizuj(slovo):
return slovo.strip().lower()
def je_nove(slovo, videna):
return slovo not in videna
def unikatni(slova):
videna = []
for slovo in slova:
ciste = normalizuj(slovo)
if je_nove(ciste, videna):
videna.append(ciste)
return videna
slova = [f" Slovo{i % 500} " for i in range(5_000)]
with cProfile.Profile() as profil:
vysledek = unikatni(slova)
print("unikátních:", len(vysledek))
moje_funkce = {"unikatni", "normalizuj", "je_nove"}
radky = []
for (soubor, cislo_radku, jmeno), udaje in pstats.Stats(profil).stats.items():
if jmeno in moje_funkce:
radky.append((jmeno, udaje[1])) # udaje[1] = all calls
for jmeno, volani in sorted(radky):
print(f"{jmeno}: {volani}×")
unikátních: 500 je_nove: 5000× normalizuj: 5000× unikatni: 1×
A teď časy. Tabulku si vypiš sám, čísla se budou při každém spuštění mírně lišit.
import cProfile
import pstats
def normalizuj(slovo):
return slovo.strip().lower()
def je_nove(slovo, videna):
return slovo not in videna
def unikatni(slova):
videna = []
for slovo in slova:
ciste = normalizuj(slovo)
if je_nove(ciste, videna):
videna.append(ciste)
return videna
slova = [f" Slovo{i % 500} " for i in range(5_000)]
with cProfile.Profile() as profil:
unikatni(slova)
pstats.Stats(profil).strip_dirs().sort_stats("tottime").print_stats(5)
Sloupce čti takhle:
| Sloupec | Význam |
|---|---|
ncalls | kolikrát se funkce volala |
tottime | čas strávený přímo v této funkci, bez volaných funkcí |
cumtime | čas včetně všeho, co funkce volala |
percall | průměr na jedno volání |
Vysoký tottime ukazuje, kde se pálí čas. Vysoký cumtime při nízkém tottime značí funkci, která jen řídí ostatní. Tady má vést je_nove: operátor in prochází seznam a jeho práce se počítá přímo do ní. Oprava je jednoduchá, videna má být množina.
Celý skript profiluješ bez zásahu do kódu:
python -m cProfile -s tottime skript.py
python -m cProfile -o profil.prof skript.py
python -m pstats profil.profKolikrát se to volá?
Napiš pocet_volani(funkce, jmeno). Spustí funkce() pod cProfile a vrátí, kolikrát se během běhu zavolala funkce se jménem jmeno. Když se nevolala vůbec, vrátí 0.
import cProfile
import pstats
def pocet_volani(funkce, jmeno):
# doplň: profiluj funkce() a najdi v pstats.Stats(...).stats správný záznam
return 0
def krok():
return 1
def program():
return sum(krok() for _ in range(7))
print(pocet_volani(program, "krok"))
tracemalloc: kam teče paměť
Pomalost není jediný problém. Program, který zabere všechnu paměť, spadne. Modul tracemalloc sleduje alokace Pythonu a umí říct, kolik paměti bylo v nejhorší chvíli obsazeno.
import tracemalloc
def spicka(funkce):
tracemalloc.start()
vysledek = funkce()
_, vrchol = tracemalloc.get_traced_memory()
tracemalloc.stop()
return vysledek, vrchol
def pres_seznam():
return sum([i * 2 for i in range(50_000)])
def pres_generator():
return sum(i * 2 for i in range(50_000))
soucet_a, pamet_a = spicka(pres_seznam)
soucet_b, pamet_b = spicka(pres_generator)
print("stejný výsledek:", soucet_a == soucet_b)
print("generátor potřebuje aspoň stokrát méně:", pamet_b * 100 < pamet_a)
stejný výsledek: True generátor potřebuje aspoň stokrát méně: True
Únik paměti najdeš porovnáním dvou snímků. Tady si funkce „pro jistotu“ schovává každý výsledek.
import tracemalloc
schovane = []
def obsluz(pozadavek):
vysledek = pozadavek.upper() + "!"
schovane.append(vysledek)
return len(vysledek)
tracemalloc.start()
pred = tracemalloc.take_snapshot()
for i in range(20_000):
obsluz(f"požadavek číslo {i}")
po = tracemalloc.take_snapshot()
tracemalloc.stop()
nejvetsi = po.compare_to(pred, "lineno")[0]
print("nejvíc paměti přibylo na řádku:", nejvetsi.traceback[0].lineno)
print("nových objektů aspoň 20 000:", nejvetsi.count_diff >= 20_000)
nejvíc paměti přibylo na řádku: 6 nových objektů aspoň 20 000: True
Výpis ukazuje řádek 6, kde řetězec vznikl, a ne řádek 7, který ho drží naživu. To je potřeba mít na paměti: tracemalloc říká, odkud paměť přišla. Kdo ji nepouští, to musíš dohledat sám.
Co znamená vysoký cumtime a skoro nulový tottime u funkce main?
cumtime zahrnuje volané funkce, tottime ne. Hledej níž ve stromu volání tu funkci, která má vysoký tottime.
Opravy, které se vyplatí
Až víš, kde to brzdí, zkoušej opravy v tomhle pořadí. Čím výš v seznamu, tím větší bývá efekt.
- Nedělej tu práci vůbec. Filtruj dřív, načítej jen potřebné sloupce.
- Lepší algoritmus a struktura. Množina místo seznamu, slovník místo vnořeného cyklu.
- Nedělej totéž dvakrát. Cache a předpočítané hodnoty.
- Hotový kód v C. Vestavěné funkce,
str.join, NumPy místo cyklu v Pythonu. - Víc jader nebo souběh. Procesy na výpočty,
asynciona čekání.
Mikrooptimalizace typu „přesuň proměnnou před cyklus“ patří až za tohle všechno.
Z kvadratické na lineární
Funkce spolecne(a, b) vrací prvky z a, které jsou i v b, ve stejném pořadí a včetně opakování. Funguje správně, ale na velkých datech je pomalá. Přepiš ji tak, aby výsledek zůstal stejný a prvky se porovnávaly jen zlomkově často. Kontrola počítá skutečná porovnání.
def spolecne(a, b):
return [prvek for prvek in a if prvek in b]
print(spolecne([1, 2, 2, 3], [2, 3, 4]))
Cache si pamatuje výsledky pro už viděné vstupy. V Pythonu je hotová jako dekorátor functools.lru_cache. Parametr maxsize určuje, kolik výsledků se drží. Když je cache plná, vypadne ten, který se nejdéle nepoužil.
from functools import lru_cache
dotazy = 0
@lru_cache(maxsize=2)
def kurz(mena):
global dotazy
dotazy += 1 # imagine a slow network call here
return {"EUR": 25, "USD": 23, "GBP": 29}[mena]
for mena in ["EUR", "EUR", "USD", "EUR", "GBP", "USD"]:
kurz(mena)
print("skutečných dotazů:", dotazy)
print(kurz.cache_info())
skutečných dotazů: 4 CacheInfo(hits=2, misses=4, maxsize=2, currsize=2)
Šest volání, čtyři skutečné dotazy. Poslední USD se ptá znovu, protože ho z plné cache vytlačil GBP.
Exploze volání
Funkce cesty počítá cesty mřížkou. Volá sama sebe a stejné dotazy řeší znovu a znovu. Přidej cache tak, aby vysledek zůstal stejný a tělo funkce se provedlo nejvýš 150krát. Proměnná volani to počítá, nech ji v těle funkce.
volani = 0
def cesty(radky, sloupce):
global volani
volani += 1
if radky == 0 or sloupce == 0:
return 1
return cesty(radky - 1, sloupce) + cesty(radky, sloupce - 1)
vysledek = cesty(10, 10)
print(vysledek, volani)
Pod kapotou · čím se měří a co měření zkresluje
Hodiny. perf_counter měří uplynulý čas včetně spánku, process_time jen čas procesoru tohoto procesu. Velký rozdíl mezi nimi znamená, že program čeká, a pak ho rychlejší kód nezachrání. timeit během měření vypíná garbage collector, což u kódu vytvářejícího hodně objektů výsledek zlepší. Zapneš ho přes setup="import gc; gc.enable()". Pro seriózní benchmarky je tu pyperf, který řeší kalibraci a rozptyl.
Profilery. cProfile je deterministický: zachytí každé volání, takže malé funkce zpomaluje víc než velké a poměry umí zkreslit. Od 3.12 stojí na sys.monitoring (PEP 669). V procesu smí běžet jen jeden, druhý skončí ValueError. V produkci se hodí vzorkovací profiler, třeba py-spy, který se připojí k běžícímu procesu zvenčí bez úpravy kódu. Na Linuxu umí 3.12 přes -X perf ukázat Python funkce i v nástroji perf.
Zkratky. python -X importtime skript.py ukáže, co zdržuje start. python -X tracemalloc=10 skript.py zapne sledování alokací s deseti rámci. Od 3.12 jsou list, dict a set comprehensions vložené přímo do funkce (PEP 709), takže v profilu nemají vlastní řádek. Generátorové výrazy ho mají dál.
Past v timeit. Kompilátor spočítá konstantní výraz předem, takže timeit("60 * 60 * 24") měří jen načtení hotové hodnoty. Neplatí to ale vždy: výsledky, které by byly moc velké, skládat odmítne, a 2 ** 100 se proto počítá až za běhu. Poznáš to podle konstant v kódu:
for vyraz in ("60 * 60 * 24", "2 ** 100"):
kod = compile(vyraz, "<ukazka>", "eval")
print(vyraz, "->", kod.co_consts)
60 * 60 * 24 -> (86400,) 2 ** 100 -> (2, 100)
Pod kapotou · adaptivní interpret a spojování řetězců
Od 3.11 se bytecode za běhu specializuje podle typů, které skutečně vidí (PEP 659). Obecné BINARY_OP se po zahřátí změní na variantu pro celá čísla. Proto krátké benchmarky bez zahřátí lžou a část starých rad o ruční optimalizaci už neplatí.
import dis
def secti(a, b):
return a + b
def scitani(funkce):
return [i.opname for i in dis.get_instructions(funkce, adaptive=True)
if i.opname.startswith("BINARY_OP")]
print("na začátku:", scitani(secti))
for _ in range(1000):
secti(1, 2)
print("po zahřátí:", scitani(secti))
na začátku: ['BINARY_OP'] po zahřátí: ['BINARY_OP_ADD_INT']
Učebnicové „+= na řetězcích je kvadratické“ platí jen napůl. CPython umí řetězec rozšířit na místě, pokud na něj nikdo jiný neukazuje a je v lokální proměnné. Stačí druhá reference a každý krok kopíruje celý text. Na tuhle optimalizaci se proto nespoléhej, PEP 8 to říká výslovně. Použij "".join(...).
import time
def skladej(pocet, drz_kopii):
text = ""
kopie = None
for _ in range(pocet):
text += "x"
if drz_kopii:
kopie = text
return len(text)
def cas(drz_kopii):
nejlepsi = float("inf")
for _ in range(3):
zacatek = time.perf_counter()
skladej(40_000, drz_kopii)
nejlepsi = min(nejlepsi, time.perf_counter() - zacatek)
return nejlepsi
print("druhá reference zpomaluje:", cas(True) > cas(False))
druhá reference zpomaluje: True
Pozor i na garbage collector: při hromadném vytváření objektů se cyklický sběr spouští často (výchozí práh první generace je 700 kontejnerů přibylých od posledního sběru). Při načítání velkých struktur pomůže dočasné gc.disable(). Servery s předforkovanými workery využívají gc.freeze().