I første del av denne artikkelserien gikk vi gjennom minneproblemer og hvordan å håndtere det å gå tom for tråder eller sockets. I denne delen vil vi forklare med eksempler, hvordan CPU- og I/O-begrensinger kan påvirke systemet og hvordan du kan løse dem. Men først må vi nesten si noe om «Big-O-notation», siden dette har en viktig plass når det er snakk om ytelse og kjøretid for algoritmer.

Det er mange måter å se på ytelse

En av måtene man som regel sammenligner algoritmer på i akademia, er «Big-O-notation». Der gir man et estimat for worst-case-utviklingen av kjøretiden til en algoritme som funksjon av problemstørrelsen. Det dette betyr med enklere ord, er at man sier noe om kjøretidsutviklingen til en algoritme, etter som den får mer å gjøre. Dette er et veldig kjekt verktøy når det kommer til ekstremt store datamengder.

UTFORDRINGEN MED DENNE MÅTEN Å SE PÅ KJØRETID, ER AT DEN FORT BLIR LITT NAIV.

Et eksempel er sortering av en liste med en enkel algoritme som heter «BubbleSort». Her har man to looper der man evaluerer og bytter plass på et og et element i rekken til alle elementer er på rett plass. Nedenfor ser du tre måter å implementere denne typen algoritme på, der de har forskjellig effektivitet. Den første har kjøretid O(n2) og de to neste har O(n*n/2) siden man bare trenger å evaluere de elementene som ikke allerede er ferdig sortert. N er som regel variabelen for antall elementer i problemet og O() gir antall operasjoner som må utføres som er avhengig av problemstørrelsen. Siden konstanter ikke har nok å si når det kommer til store datamengder vil man fjerne dem og si at alle tre algoritmer er O(n2) siden dette er lettere å sammenligne.
def bubbleSort1(values):
numElements = len(values)
for i in range(numElements-1):
for j in range(0, numElements-1):
if values[j] > values[j+1]:
values[j], values[j+1] = values[j+1], values[j]

def bubbleSort2(values):
numElements = len(values)
for i in range(numElements-1):
for j in range(0, numElements-i-1):
if values[j] > values[j+1]:
values[j], values[j+1] = values[j+1], values[j]

def BubbleSort3(values):
numElements = len(values)
 swapped = False
for i in range(numElements-1):
for j in range(0, numElements-i-1):
if values[j] > values[j+1]:
values[j], values[j+1] = values[j+1], values[j]
 swapped = True
 if swapped == False:
break

I dette eksempelet er det ganske greit å se hva kjøretiden er, men større og mer komplekse algoritmer kan fort trenge forenklinger, der man tar vekk konstanter, siden det er for vanskelig å estimere hvor lang tid hver del kommer til å ta med nøyaktige tall.

Utfordringen med denne måten å se på kjøretid, er at den fort blir litt naiv. Dette fordi den som regel forenkler bort parallellisering, I/O, eller andre faktorer som gjør at man får en mer kompleks graf man skal representere.

DET AT PROGRAMMER KLARER Å UTNYTTE HØY PROSENT AV CPU NÅR DET FØRST ER I GANG, ER OFTE ET GODT TEGN.

Denne typen forenklinger gjør at man fort kan bli lurt til å velge feil algoritme, hvis man for eksempel har mye CPU tilgjengelig og problemstørrelsen er overkommelig. Dersom man koder opp mot et grafikkort, der man som regel har tilgang til veldig mange kjerner, vil det være mye viktigere at felleskapet av CPU-kjerner jobber på maks ytelse, enn at en og en kjerne blir ferdig så tidlige som mulig med sin del av problemet. Det er derfor viktig å forstå ditt spesifikke problem, datastørrelse og maskinvare så godt som mulig, slik at du kan gjøre et informert valg på hvilke flaskehalser som treffer deg.

Gå “tom” for CPU

I de fleste tilfeller er ikke CPU den begrensende faktoren. Av og til benytter man 100% av en av kjernene, men så lenge man kjører på moderne pc-er eller servere, vil ikke dette være et normalt problem. Som regel er det andre elementer av programmet som er begrensende for kjøretiden, men dersom man for eksempel har begynt å parallellisere, eller kjører på en svakere enhet som en telefon eller en IOT-device, kan man likevel komme bort i dette problemet.

Det at programmer klarer å utnytte høy prosent av CPU når det først er i gang, er ofte et godt tegn. Når man ser på ytelse, er det også viktig å evaluere om serveren er dedikert til deg, eller om du deler den med andre og om du trenger noe CPU allokert til å kjøre andre bakgrunnsprosesser, som for eksempel logging og monitorering.

Konkrete tiltak man ofte kan gjøre for å få ned CPU-bruk er å:

1. Finne en mer effektiv algoritme

2. Passe på at registerverdiene ikke må byttes for ofte

3. Sørge for at verdier kan leses sekvensielt i minnet

4. Begrense laging, klone eller kopiere for mange objekter i kritisk del av koden

1. Finne en mer effektiv algoritme

Selv de enkleste ting kan gjøres smartere dersom man tenker en del på det. Siden man vet mye om dataen som kommer inn, kan man ofte gjøre en del forenklinger for å gjøre programmet utrolig mye raskere. Et godt eksempel på bruk av mer effektive algoritmer, er sortering av større datamengder. Her er det vanlig å bruke hybridalgoritmer, som da først sorterer med en algoritme, for så å bytte om til en mer spesialisert algoritme mot slutten. Eksempel på dette er «Introsort» som brukes til sortering i C++ og .Net. Den bruker først quicksort, for så å bytte til heapsort og avslutter med insertionsort.

Quicksort velger et tall i listen og sammenligner alle tall med dette. Alle tall som er høyere legges på høyre side av tallet og alle som er lavere legges til venstre. Så sendes venstre og høyre side inn til en ny rekursiv runde av algoritmen for videre sortering.

Heapsort lages ved at man bygger en maks-heap. Dette gjøres ved at du iterativt kaller en rekursiv metode som løfter tall som er høyere enn sine foreldre oppover i treet. Når du er ferdig med en iterasjon begynner du å plukke fra hverandre treet ved å fjerne roten og sortere treet på ny.

Insertionsort er slik de fleste sorterer kort når man skal spille. Man begynner fra en side og evaluerer et og et kort. Hvert kort settes på den første plassen der de er lik verdi eller høyere enn et eksisterende kort.

SÅ TIPSET HER ER Å ENDRE SÅ FÅ VERDIER SOM MULIG PER ITERASJON I ALGORITMEN, SLIK AT DE VIKTIGSTE VERDIENE HELE TIDEN LIGGER RASKT TILGJENGELIG.

Ved å kombinere disse tre algoritmene ungår man i stor grad hver av deres svakheter. Quicksort er rask, men har en svakhet for dårlig splitting av listene. Derfor bytter man over til heapsort dersom man begynner å kalle seg selv rekursivt for mange ganger i Quicksort. Når man kommer til få antall elementer er Insertionsort best og tar derfor innspurten. For mer info se gjerne:

https://www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/

2. Kontroll på registerverdiene

Registerverdier trenger man som regel ikke bry seg så mye om før man skal hente ut siste prosenten av ytelse. Her er du avhengig av å vite litt om minimum krav til maskinvare programmet skal kjøre på. Register er den raskeste lagringen du har i en maskin og ligger så nær utregningen som mulig. Men dette betyr også at du har begrenset antall verdier som kan lagres her. For eksempel har en Intel i7 8086 prosessor 16X64 kB lagring i register for 64 bit. Dette er ikke mye, men det er veldig raskt. Så tipset her er å endre så få verdier som mulig per iterasjon i algoritmen, slik at de viktigste verdiene hele tiden ligger raskt tilgjengelig.

3. Tilpasse systemet for sekvensiell lesing

Sekvensiell lesing er lettere å gjennomføre. Se for deg at du skal hente inn verdier fra sensorer og lagre dem. En naturlig måte å lagre dette på ville vært å lagre alle de nyeste verdiene fra alle sensorer samlet i en batch. Dersom du som regel skal lese dataen på denne måten, vil dette være smart, men dersom du som regel er ute etter å se på trender på en sensor eller et lite område med sensorer, så kommer du trolig til å få et stort problem. Da ingen av disse verdiene ligger på rekke, må man lese opp veldig mange verdier og søke mye, før man får dataen man vil.

CPU-er også bygget slik at de er ekstra gode på å lese ting som kommer etter hverandre . Det finnes til og med operasjoner som kan lese to og to int32 av gangen for å utnytte en 64 bit-arkitektur optimalt. Det er derfor viktig å lagre data på en så effektiv måte som mulig, i den delen av programmet som er flaskehals. Av og til kan det også være en flaskehals ved skriving og det kan da være en løsning å skrive data på en «naiv» og rask måte, for så å ha en bakgrunnsjobb som rydder dataen over på en mer effektiv måte.

Alle disse punktene kan fort gjøre koden komplisert, men redningen er som regel å finne et bibliotek eller en spesifikk metode, som allerede har implementert dette for deg (helst i c eller c++). Heldigvis er det mange som har lagt ned utallige timer med arbeid for å lage utrolige effektive algoritmer for å kjøre join-operasjoner, optimalisert søk og mye annet. Du trenger ikke finne opp hjulet på nytt her.

4. For mange objekter i kritisk del av koden

Når man lærer seg et nytt og kult programmeringspattern, er det lett at man benytter det unødvendig mye i begynnelsen. Slik er det med objektorientert programmering også.

DET SOM KAN VÆRE LURT, ER Å IMPLEMENTERE DET LESBART FØRST OG HA I BAKHODET AT MAN KAN GJØRE EN FORENKLING AV DE VIKTIGSTE TALLENE I EN UTREGNING OM TIL MATRISER I STEDET FOR OBJEKTER.

Det er mange som ender med å gjøre alt om til objekter i uendelige hierarkier av arv. Denne feilen har jeg har selv gjort, og en av de uventede effektene av dette var en kraftig knekk i ytelsen i den delen av koden som måtte gå raskest.

Det å balansere dette kan være vanskelig, da man balanserer på en knivsegg, der man fort enten kan lage uleselig kode eller få for dårlig ytelse. Det som kan være lurt, er å implementere det lesbart først og ha i bakhodet at man kan gjøre en forenkling av de viktigste tallene i en utregning om til matriser i stedet for objekter.

Eksempel:

Python: Ved å gå over til å bruke innebygde metoder for matriseopperasjoner og søk i biblioteket «Pandas», gikk vi fra timer til sekunder i en av våre systemer, samtidig som lasten på CPU gikk ned. Dette krevde veldig lite kode og gjorde også at vi hadde dataen på et format som muliggjorde mange andre operasjoner.

ET TIPS HER ER Å PARALLELLISERE MER, ELLER Å KJØRE SÅ MYE ASYNKRONT SOM MULIG, DERSOM DU IKKE TRENGER SVARET MED EN GANG.

Begrenset av IO

Veldig ofte trenger algoritmer å laste noe data i en eller annen form. Om det er fra en database, fra disk, en strøm eller til grafikkort, vil dette medføre en kostnad i både kjøretid, CPU og minne. Av disse er det som regel kjøretiden som øker raskest og fører til problemer. Et tips her er å parallellisere mer, eller å kjøre så mye asynkront som mulig, dersom du ikke trenger svaret med en gang.

Et annet tiltak for å redusere kjøretid, er å spørre om mer av den samme dataen og bruke den som «cache». Dersom du velger å gå for denne løsningen, er det viktig at du har et bevisst forhold til om dataen endres ofte og hvordan algoritmen din vil oppføre seg når dette lageret må tømmes på grunn av oppdateringer av enten kode eller dataen selv.

Når det kommer til å få opp hastigheten på lesing, er det veldig ofte noen andre som også har slitt med dette problemet før deg og derfor har laget et rammeverk med «insert range», «delete range» og/eller «upsert». Dette er ofte metoder som fort kan oversees, men som kan øke ytelsen ved for eksempel et databasekall, med 100-gangen.

En feil som ofte går igjen når det kommer til databaser, er uthenting av for mye data. Programmet bør som regel kjøre så mye filtrering/gruppering/aggregering som mulig i SQL, eller i andre datanære språk, før det føres over til din maskin. Det er dette databaser er laget for og er utrolig gode på. Dette er ikke bare lurt med tanke på kjøretid, men kan også være en god optimalisering, dersom du skal servere data over til noen som sitter på 4G eller lignende.

For å få IO til å gå så raskt som det bør, er det viktig at man setter seg inn i en del ting:

• Index strategier

• Database cache

• Partisjonering

• Sharding

• Read only replicas

• Som regel er Inner join mye bedre enn outer join

• Sett kolonner til å være “not null” så ofte som mulig

• For mange indexer/unique contraint/database triggers kan drepe skrivehastigheten

Disse databaseoptimaliseringene er ikke i scope for denne bloggen, men skriv gjerne under dersom du kunne ønske deg et nytt blogginnlegg om dette.

Eksempel:

C#: Vi brukte entity framework og add i en av våre programmer, før vi endret til å bruke AddRange i stedet. Dette førte til at vi sparte minutter på lagring av store kjøringer.

Oppsummering

Dette var en rask gjennomgang av to av utfordringene vi ofte ser knyttet til ytelse. I neste artikkel, som er tredje og siste del i denne artikkelserien, kan du lese mer om begrensninger i sekvensiell del av programmer og hvordan vi har jobbet med ytelse i praksis ute hos kunder.
Dersom dere har noen kommentarer, spørsmål eller trenger å snakke med noen om ytelse, er det bare å skrible ned noe å sende til Hei@alv.no eller legge inn i kommentarfeltet under.