Python höx: lykkjur og cache

Python er um margt fínt forritunarmál. Það er mjög byrjendavænt mál og einfalt að skrifa og keyra kóða í því. Helsti vankanturinn við Python er samt auðvitað hvað það er hægvirkt. Þegar kóðinn þarf ekki að reikna mjög mikið þá er munurinn á millisekúndu og míkrósekúndu ekki mjög mikilvægur, sérstaklega ekki ef það að skrifa kóðann í Python sparar forritaranum dag eða meira af vinnu miðað við að skrifa hann í t.d. C++. En nú eru margir að keyra frekar þungan kóða í Python, sérstaklega í vísindalegri tölvun. Þó að ákveðin óskilvirkni tengd því að túlka kóðann í stað þess að þýða hann sé óumflýjanleg, þá er ýmislegt hægt að gera til að láta Python forritið sitt keyra sem hraðast.

Mig langar að skrifa niður og deila ýmsum Python höxum sem ég hef lært í gegnum tíðina. Í þessum hluta fer ég yfir nokkur ráð til að gera Python kóða hraðari. Í framtíðinni skrifa ég kannski um fleiri slík höx.

Lykkjur: summan af náttúrlegu tölunum upp að ákveðinni tölu

For á móti while

Hver er munurinn á þessum kóðabútum?

summa = 0
for i in range(100001):
    summa = summa + i

#######################

summa = 0
i = 0
while i < 100001:
    summa = summa + i
    i = i + 1

Rökfræðilega virðast þessir bútar vera alveg eins, en munurinn liggur í innri virkni Python. Python, nánar tiltekið CPython sem er staðalútgáfan af Python, byggist á undirliggjandi skipanasafni sem er skrifað í C. Built-in fyrirbæri í Python eru því almennt mun skilvirkari en hvað sem maður gæti gert í Python. Með því að nota for lykkju hér í staðinn fyrir while lágmarkar maður þannig hversu mikið af kóðanum keyrir í Python interpreternum í staðinn fyrir í þýddum og skilvirkum C rútínum. while lykkjan framkvæmir þrjár python aðgerðir í hverri ítrun, en for lykkjan aðeins eina. Í stuttu máli þá er skilvirkasta leiðin til að lykkja í Python að lykkja ekki í Python heldur í C.

Að hámarka notkun á innbyggðum föllum

Það er hægt að lágmarka enn meira hve margar python aðgerðir eru framkvæmdar með því að endurskrifa þetta sem

summa = sum(range(100000))

Bæði er þetta knappara, og núna fara samlagningarnar líka fram í C í staðinn fyrir Python.

NumPy

Á þeim nótum að nota sem minnst Python í Python forritunum okkar er sjálfsagt að skoða NumPy. NumPy er í rauninni bindingar fyrir skilvirk C skipanasöfn, þannig að almennt getur maður hraðað mikið á reikningum með því að nota NumPy sem mest. Með numpy gætum við til dæmis gert

import numpy as np

summa = np.sum(np.arange(100001))

Numba og PyPy

Annað tól sem við getum nýtt okkur til að hraða á Python er að fjarlægja sem mest af túlkuninni og nota Just in Time (JIT) þýðingu. Með Python eru tveir kostir til þess, annarsvegar Numba pakkinn og hinsvegar önnur Python útgáfa sem kallast PyPy.

Kostirnir við Numba framyfir PyPy eru að hann er einfaldlega pakki sem maður installar með pip, maður getur notað hann í venjulegum Python kóða og hann er með slatta af stillingum sem geta gefið manni enn meiri skilvirkni með einföldum hætti. Vankantar Numba eru hinsvegar að það er aðeins hægt að nota hann til að JIT-a ákveðna hluti, eins og föll og klasa, þannig að til að fá sem mest úr því þarf maður hugsanlega að endurskrifa kóðann sinn. Síðan keyrir Numba frekar hægt fyrst þegar það JIT-ar fall, þó það keyri síðan ansi hratt eftir á.

Kostirnir við PyPy eru síðan að það virkar fyrir allan Python kóða manns, þannig að maður þarf ekki að endurskrifa neitt sem fall. Af því að PyPy er sjálft byggt á JIT þá er fyrsta þýðingin hraðskreiðari en með Numba. Hinsvegar eru vankantarnir við PyPy að maður þarf að setja upp heila nýja útgáfu af Python og ýmsir pakkar sem virka með CPython virka ekki með PyPy, eins og functools. Þó að PyPy keyri fyrstu þýðinguna frekar hratt og þurfi síðan ekki að þýða fall aftur sem það er búið að þýða, þá er PyPy þýðandinn ekki jafn sniðugur og Numba þýðandinn, eins og við munum sjá seinna.

from numba import njit

@njit # Fyrir PyPy skrifar maður það sama nema án Numba og njit
def summa(n):
    summa = 0
    for i in range(n+1):
        summa = summa + i
    return summa

summa(100000)

Cython

Enn annað hax sem maður getur gert með Python er Cython. Cython er nokkurskonar kerfi sem er hægt að nota til að þýða Python kóða yfir í C kóða, og fá þannig vonandi það besta úr báðum heimum, hraða C og einfaldleika Python. Fyrir þetta dæmi myndum við skrifa .pyx skrá, segjum sumcython.pyx með eftirfarandi innihaldi

# Það er ekki nauðsynlegt að segja hvaða tegundir breyturnar eru
# en það hraðar á lokaniðurstöðunni.
# Ef við gerðum cdef á fallið þá gætum við ekki notað það í Python.
# cpdef gefur okkur hraðaaukningu miðað við def en leyfir okkur ennþá að nota það í Python.
cpdef long int summa(long int n):
    cdef long int total = 0
    for i in range(100001):
        summa = summa + i
    return total

Síðan skrifar maður setup.py skrá með innihaldinu

from setuptools import setup
from Cython.Build import cythonize

setup(
    name='bleh',
    ext_modules=cythonize('sumcython.pyx'),
    zip_safe=False,
)

Síðan keyrir maður python setup.py build_ext --inplace til að búa til module sem heitir sumcython. Maður getur svo importað fallið í Python kóða

from sumcython import summa

summa(100000)

En svo hefur Cython auðvitað sína vankanta. Til dæmis virkar það ekki með decoratorum eins og eru í functools og það er flókið að samþætta það með öðrum pökkum eins og Django. Þar að auki er þetta auðvitað dálítið maus ef maður er bara að gera eitthvað svona einfalt, og eins og við munum sjá er cython þýðandinn ekki jafn sniðugur og Numba þýðandinn.

Að hugsa aðeins

Þetta tiltekna dæmi minnir mann líka á að hafa augun opin fyrir því hvort maður sé að gera það sem maður er að reyna að gera asnalega. Nefnilega er til einföld formúla fyrir þessari summu sem hvaða 10. bekkingur sem er ætti að þekkja:

summa = 100000*(100000 + 1)/2

Hér erum við búin að breyta hundrað þúsund summum og einni lykkju í eina summu, eina margföldun og eina deilingu.

Að inline-a

Hingað til hefur þetta nánast allt verið „inline“ kóði. Það er að segja, fyrir utan fallið sem við viljum að Numba þýði, þá var enginn af þessum kóða settur í sérstakt fall. Nú eru margar aðstæður þar sem maður myndi vilja setja hluta af kóðanum sínum í fall, sér í lagi ef maður er að skrifa nokkurnveginn sama kóðan oftar en tvisvar með aðeins smávægilegum breytingum.

Það getur bæði gert það auðveldara að lesa og skilja kóðann, sem gerir það auðveldara að viðhalda honum fram í tímann og gerir manni auðveldara fyrir að greina vandamál í kóðanum. En það er smá vandamál við að gera kóðabút að falli, það tekur nefnilega tíma að kalla á fallið. Í þýddum málum eins og C, C++, Rust og svo framvegis, þá yfirleitt „inlinear“ þýðandinn sem flest föll sem maður notar og sleppir þar af leiðandi fallköllunum í lokaforritinu. Í Python hinsvegar kallar interpreterinn á fallið, og það getur tekið dálítinn tíma.

Sem dæmi þá gætum við gert summuformúluna okkar að falli:

def sum_up_to_n(n):
    return n*(n+1)/2

Að kalla á þetta fall tekur sirka stærðargráðu lengri tíma heldur en að reikna beint í kóðanum. Hinsvegar, ef þú ert að gera sama hlutinn aftur og aftur í kóðanum þínum þá er sjálfsagt mál að aðskilja það í fall til að þér verði ekki illt í augunum við að lesa kóðann þinn.

Mismunandi ítranlegar gagnagerðir

Nú höfum við hingað til bara verið að vinna með range til þess að ítra yfir. En það er ekki eina gagnagerðin í python sem er hægt að ítra yfir. Til dæmis er hægt að ítra yfir lista, n-undir, mengi og orðabækur.

En hver er hraðasta gagnagerðin til að ítra yfir? Í stuttu máli er ómælanlega mjótt milla muna á n-undum og listum. Orðabækur eru síðan dálítið hægari en listar og mengi enn hægari en það. Nánar um það í samantektinni og meðfylgjandi python skrá

Samantekt

Ég útbjó Python skrá sem þú getur keyrt til að bera saman hraðann á þessum mismunandi aðferðum. Skiljanlega nennirðu kannski ekki að fara í gegnum Cython ferlið, þannig að sá hluti er kommentaður út. Hinsvegar er NumPy nánast ómissandi ef maður notar Python í einhverjum reikningum, og Numba krefst ekki næstum því jafn mikils stúss og Cython, þannig að báðir þeir hlutar eru ókommentaðir í skránni.

Ef þú keyrir skránna muntu sjá að for lykkjan keyrir sirka 40% hraðar en while lykkjan. Að nota innbyggð föll sem mest keyrir rúmlega tvöfalt hraðar en lykkjurnar, en NumPy kóðinn keyrir síðan tæplega tvöfalt hraðar en jafnvel það.

Numba kóðinn virðist við fyrstu keyrslu vonlaus, en svo þegar það er búið að þýða fallið kemur í ljós að hann keyrist á örfáum míkrósekúndum. Numba er nefnilega byggt á Clang, sem fattaði hvað þetta var asnaleg aðferð sem við vorum að nota og spýtti út falli sem notar þessa vel þekktu formúlu.

Loks er það að pæla aðeins í dæminu og koma með sniðugri lausn klár sigurvegari, jafnvel fimmfalt hraðara en Numba kóðinn. Python fallið sem notar sömu formúlu keyrir síðan eiginlega nákvæmlega jafn hratt og Numba kóðinn. Það sýnir hvað það tekur langan tíma að kalla á fall miðað við að gera reikninginn „inline.“

Ef þú prófar síðan PyPy þá sérðu að ef þú býrð til fall fyrir reikninginn tekur styttri tíma að nota það í fyrstu keyrslu en ef maður notar Numba. Hinsvegar er seinni keyrslan bara álíka hröð og Cython. Þýðandinn í PyPy er semsagt ekki alveg jafn klár og Numba þýðandinn.

Að lokum sést að listar og n-undir eru hraðasta gagnagerðin til að ítra yfir. Í mismunandi keyrslum getur munað talsverðu á því hversu mikið hægari orðabækur og mengi eru, en þær eru svipað hægar og eru sirka frá 5 og upp í 20% hægari en listar og n-undir.

Cache: Fibonacci runan

Hugsum okkur einfalt fall sem finnur n-tu Fibonacci töluna

def fib(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

Það er frekar stór galli við þetta fall, það nefnilega keyrir í O(2ⁿ) tíma. Í hvert skipti sem það er ekki komið niður í grunntilfelli kallar það á sjálft sig tvisvar í viðbót þangað til að það kemst niður í grunntilfellið, og síðan þarf það aftur að rekja sig niður í grunntilfellið fyrir hverja síka grein sem það bjó til.

Berum það saman við hvernig maður myndi skrifa niður Fibonacci tölur í höndunum. Þú byrjar á að skrifa niður 1 og 1. Síðan til að finna næstu töluna leggurðu þær tvær síðustu saman til að fá tvo, síðan gerirðu það aftur til að fá þrjá, síðan aftur og færð fimm, o.s.frv. þangað til að þú ert búinn að rekja þig upp að tölunni sem þú vilt komast að. Munurinn er að við skrifum Fibonacci tölurnar niður á blað eftir því sem við reiknum þær, þannig að þegar okkur vantar síðustu tvær Fibonacci tölurnar þurfum við ekki að reikna þær aftur upp á nýtt eins og forritið gerir, við lesum þær bara af blaðinu. Þetta er dæmi um cache, geymsla sem inniheldur for-útreiknuð gildi fyrir fallið sem er bara flett upp í staðinn fyrir að reikna þau.

En hvernig búum við til cache fyrir fallið okkar? Það er nefnilega einfalt mál í Python með inbyggðu skipanasafni sem kallast functools. Functools býður upp á ýmsa cache decoratora, þannig að með því einfaldlega að skrifa

from functools import cache

@cache
def cfib(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    return cfib(n - 1) + cfib(n - 2)

Þá er maður búinn að búa til cachaða útgáfu af fallinu, þannig að ef maður biður það um fallgildið fyrir inntak sem er búið að reikna þá tekur það bara niðurstöðuna beint úr cachinu.

Hvað hefur cachið í för með sér fyrir þetta fall? Ef við köllum til dæmis á cfib(40) mun fallið fyrst rekja sig niður að grunntilfelli fyrir eina grein, en þá fyllist cachið af þekktum fallgildum í leiðinni, þannig að fyrir hvert kall á cfib eftir það getur það bara flett upp niðurstöðunni. Þannig að núna virkar fallið í línulegum tíma á móti því að nota aðeins meira minni. Þetta er eitt dæmi um algenga málamiðlun í forritun: að láta forrit keyra hraðar á móti því að nota meira minni, eða að nota minna minni á móti því að forritið keyri hægar.

En hversu mikið minni notar það? Eftir nítugustu Fibonacci töluna verða þær of stórar fyrir 64 bita heiltölur, þannig að cachið verður sennilega ekki mikið stærra en 2 kiB í praktískri notkun (cachið þarf bæði að geyma inntökin og fallgildin og svo hefur gagnagerðin sjálf ákveðið overhead). Til samanburðar geturðu prófað að keyra fib(40) og cfib(40). Þú þarft ekki einu sinni að setja upp neinn benchmark kóða til að sjá hversu mikið hraðar cfib keyrir. fib(40) mun taka tugi sekúnda á meðan cfib(40) klárast nánast samstundis.