Få de daglige nyheder fra Version2 og Ingeniøren. Læs mere om nyhedsbrevene her.

close
Ved at tilmelde dig accepterer du vores Brugerbetingelser, og du accepterer, at Teknologiens Mediehus og IDA-gruppen lejlighedsvis kan kontakte dig om arrangementer, analyser, nyheder, job og tilbud m.m. via telefon og e-mail. I nyhedsbreve, e-mails fra Teknologiens Mediehus kan der forefindes markedsføring fra samarbejdspartnere.
forskningsingeniøren bloghoved

Lavthængende frugter og præmatur kodeoptimering

Før jul stødte jeg ind i ikke at have nok hukommelse i min computer til at gennemføre en beregning, og for at imødegå dette hukommelsessvigt lagde jeg en plan for, hvilke tiltag som kunne gøre mine beregninger mindre hukommelseskrævende og hurtigere. Disse tog jeg i begyndelsen af det nye år fat på at implementere, og det har givet nogle markante forbedringer af min kode, som jeg i dette blogindlæg vil beskrive i håbet om, at andre kan bruge idéerne til forbedringer i egen kode.

Lad mig starte med en væsentlig pointe, som formentlig er gældende for mange andres kode også: Der er mange lavthængende frugter at plukke. Jeg har programmeret i Matlab i en del år og har lavet flere større kodepakker til at gennemføre avancerede simuleringer. Men jeg er ikke computerprogrammør og er således ikke uddannet til at skrive "korrekt" kode, hvor softwarearkitektur, kodetestning, debugging mv. er tænkt meget systematisk ind i koden, allerede før den første linje kode er skrevet. Dette leder nemt til kode, som man uden en stor indsats kan forbedre og optimere - eller med andre ord til lavthængende frugter.

Med oplevelserne fra det første år af mit ph.d. projekt er jeg blevet mere bevidst om at tænke på strukturen af koden, således at denne især kan skaleres til de store simuleringer, vi er interesseret i at kunne gennemføre på vores computer cluster med rimelige beregningstider. Processen med at forbedre hukommelseskravene og hastigheden af min kode har været en lærerig oplevelse, som jeg forventer vil være brugbar, når jeg snart går videre fra de indtil nu mindre krævende todimensionelle beregninger til de mere udfordrende tredimensionelle beregninger.

Profiling: Hvor trykker skoen mest?

Før man går i gang med at optimere sin kode, er det værd at gøre sig klart, hvilke dele af koden der kræver mest hukommelse og som tager længst tid. Hertil er det centralt at køre sine beregninger på et repræsentativt stort problem, hvor de væsentligste flaskehalse vil stå klart ud. I mit tilfælde består dette f.eks. i at regne på en stor fotonisk krystal, hvor jeg inkluderer mange rækker af huller (se billedet nedenfor), og hvor jeg bruger mange led i de Fourier rækker, min løsningsteknik er bygget op omkring; dette leder til mange og store matricer, og de kritiske elementer i min kode står dermed klarest frem.

For et sådant repræsentativt stort problem kan man profile sin kode. Dette giver adgang til en profiler rapport, som i stor detalje beskriver, hvor lang tid hver del af koden tager at køre, og som således udgør et oplyst startpunkt for, hvor man skal optimere sin kode.

Præ-allokering er godt, men...

Som det nok er de fleste med blot en smule programmeringserfaring bekendt, er det en god idé at præ-allokere datastrukturer frem for at lade disse vokse i størrelse, efterhånden som data fyldes ind i disse.

Jeg benytter i min egen kode flittigt præ-allokering, men dette ledte i min implementering til hukommelsesproblemerne beskrevet ovenfor. Konkret beregner jeg løsninger i hver lateral række af huler (se igen billedet ovenfor), og eftersom disse ofte er identiske, beregner jeg kun løsningerne for én af rækkerne - og gemmer data fra denne første række i datastrukturerne for de efterfølgende rækker. Dette leder i udgangspunktet til, at Matlab kun gemmer én kopi af disse data, men når datastrukturerne før dette er præ-allokeret med nuller, anvendes hukommelse for hver række. Hvilket, når der anvendes mange rækker, leder til meget data i hukommelsen.

Løsningen var ganske simpelt kun at præ-allokere datastrukturer for de unikke rækker af huller i mit konkrete problem - og så tilgå disse data ud fra pasende indekstabeller, som angiver, hvor de relevante data er gemt. I det generelle tilfælde, hvor der ikke er en gentagelse i strukturen, vil dette selvsagt ikke hjælpe, men det er i alle tilfælde værd at overveje, om man behøver at gemme al data, hvis hukommelse er en udfordring.

Parallelisering af pinligt paralleliserbare løkker

I Matlab kan man ved at erstatte for-løkker med parfor-løkker parallelisere løkker og udnytte eventuelt flere kerner på den computer, beregningerne gennemføres på, til at udføre beregninger parallelt frem for sekventielt. Dette er kun muligt, såfremt beregningerne i de enkelte skridt af løkken er uafhængige.

Er dette tilfældet, er der tale om et såkaldt pinligt parallelt problem, som man nemt og med fordel kan anvende en parfor-løkke på - hvilket i det simpleste tilfælde blot drejer sig om at skrive parfor i stedet for for!

I min egen kode udnytter jeg nu parfor-løkker flere steder, hvilket har givet en forbedret beregningstid. Jeg oplevede dog også, at det et enkelt sted ikke kunne betale sig at løse med parfor frem for med for, idet beregningstiden øgedes. Der er en smule overhead forbundet med at sende dele af beregningen ud til forskellige kerner, og hvis denne overstiger gevinsten ved de parallele beregninger, er der ikke noget at vinde. Hvis man laver en passende stor beregning, vil fordelen ved parfor altid på et tidspunkt manifestere sig, men det er værd at profile de forskellige metoder og gøre sig klart, om den i visse tilfælde lidt mere komplekse parfor-kode betaler sig i form af hastighedsforbedringer.

Parfor-løkker er i øvrigt også ideelle til at lave parameter scanninger, idet beregningerne ved hver værdi af parameteren typisk er uafhængige. Dette har jeg implementeret, hvilket også har givet hastighedsforbedringer.

Reducer eller genanvend "dyre" beregninger

Visse beregninger i koden tager, som profiler rapporten kan afsløre, længere tid end andre, og det er som nævnt værd at have særligt fokus på disse. Specielt er det værd at overveje, om antallet af "dyre" beregninger kan reduceres, eller om dele af disse kan genanvendes.

I min kode er en tidskrævende del at løse matrixligninger, svarende til at konstruere (ikke eksplicit!) den inverse af en række matricer. Det viste sig, at disse matrixinverse kunne genbruges, og dette gav en hastighedsforbedring. Jeg kunne også omskrive ligningerne og dermed reducere antallet af matrixinverse yderligere, men prisen var flere matrixmultiplikationer og kode, som ikke var hurtigere; profiler rapporten var igen central for at forstå, hvordan jeg bedst optimerede koden.

Undgå unødvendige for-løkker

Det er barnelærdom, men det skader ikke at høre det igen: For-løkker tager tid og skal derfor så vidt muligt undgås. Specielt i Matlab, som er optimeret til at lave vektoriserede beregninger, er dette centralt.

Jeg havde nogle enkelte steder for-løkker, som kunne undværes, og særligt den ene af disse - i forbindelse med Gram-Schmidt ortonormalisering - gav en væsentlig hastighedsforbedring.

Lavthængende frugter og præmatur kodeoptimering

Meget af ovenstående har kun krævet mindre ændringer i min kode, og som nævnt i begyndelsen har der således været en del lavthængende frugter at plukke. Profiler rapporterne var centrale til at optimere koden de rette steder, og hvor der kun var minimale forbedringer at hente, foretrak jeg at beholde den mere læselige og intuitive kode, jeg oprindeligt havde skrevet.

For, som Donald Knuth udtrykte det, "premature optimization is the root of all evil"!

Emner : Software
Jakob Rosenkrantz de Lasson er civilingeniør og ph.d. i nanofotonik fra DTU. Jakob arbejder som Product Lead og forskningsingeniør hos virksomheden TICRA i København og blogger om forskning, fotonik og rumteknologi. Jakobs blog har tidligere heddet DTU Indefra (2012-2016) og DTU Studenten (2012)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Tak for interessant indlæg. Jeg har selv haft stor glæde af profileren i MatLab. Bare af nysgerrighed, hvad var effekten af din optimering (mem forbrug, beregningstid)?

-Steen

  • 0
  • 0

Tak for interessant indlæg. Jeg har selv haft stor glæde af profileren i MatLab. Bare af nysgerrighed, hvad var effekten af din optimering (mem forbrug, beregningstid)?

Selv tak.

Mht. memory så ved jeg ikke rigtig, hvad forbruget var før optimeringen; jf. det første billede i mit indlæg, stoppede en repræsentativt stor beregning, før det hele var færdig, og det er derfor svært at estimere.

Ændringerne med kun at opbevare unikke data, uden at præ-allokere datastrukturerne for alle lag, har dog været meget central: Jeg kan nu skalere min struktur ved f.eks. at inkludere flere rækker af huller, uden at dette har en indvirkning på hukommelsen - mens det for hastighed har en lille betydning.

Efter memory optimeringen kørte jeg en beregning som den, der ikke før jul kunne køre, og denne tog ca. 750 sekunder (12:30 min). Da jeg var færdig med at optimere koden mht. hastighed tog den samme beregning ca. 150 sekunder (2:30 min). Hvis jeg tilføjer flere led i Fourier rækkerne, bliver denne forskel endnu mere udtalt, og dette vil være tilfældet, når jeg går videre til tredimensionelle simuleringer.

Hvad har du selv haft af konkrete oplevelser med profiling og kodeoptimering?

  • 0
  • 0

For-løkker tager tid og skal derfor så vidt muligt undgås.

Det er vel en lidt farlig generalisering - i de fleste programmeringssprog er en for-løkke (og tilsvarende løkker som while, foreach, osv.) den hurtigste måde at foretage en operation på N elementer. Man skal naturligvis undgå algoritmer med kompleksitet O(N) hvis det er muligt, fx ved at erstatte lineær søgning med tabelopslag eller binær søgning, men det er lidt en anden problemstilling.

  • 1
  • 0

Det er vel en lidt farlig generalisering - i de fleste programmeringssprog er en for-løkke (og tilsvarende løkker som while, foreach, osv.) den hurtigste måde at foretage en operation på N elementer. Man skal naturligvis undgå algoritmer med kompleksitet O(N) hvis det er muligt, fx ved at erstatte lineær søgning med tabelopslag eller binær søgning, men det er lidt en anden problemstilling.

Sandt, det er nok lidt for skarpt formuleret. Men særligt i Matlab, og særligt når man lige lærer at bruge dette sprog, er det nemt at sætte nogle for-løkker op, som gør det samme, som en enkelt matrixmultiplikation kan klare. Og her er for-løkkerne en dårlig idé: 1) De er markant langsommere, og 2) de giver ikke den samme forståelse for matrixalgebra, som matrixmultiplikationen gør.

Jeg er selv startet på denne måde, og jeg har også været hjælpelærer i indledende Matlab-kurser og har set, at de fleste starter sådan - mens jeg i dag med stor fordel undgår så mange for-løkker som muligt.

  • 0
  • 0

Hej Jakob,

Jeg bruger på mange måder Matlab på samme måde som dig - jeg skriver en masse kode, men er ikke programmør. Og selvfølgelig er jeg også interesseret i, at den tager meget lidt tid at eksekvere. Jeg kender derfor også mange af de tricks du skriver om. Det seneste trick jeg har lært i forbindelse med programmering i Matlab er brugen af MATLAB Coder. Her laves en .m-fil om til c-kode, som stadig kan bruges igennem Matlab via en mex-fil. Det har i nogle tilfælde gjort min kode 6 gange hurtigere! Især i tilfælde, hvor det ikke er muligt at undgå for-løkker er det en god ide. Den eneste bagside er, at ikke alle matlab-kommandoer er understøttet (se http://www.mathworks.se/help/simulink/ug/f...).

  • 1
  • 0

Det seneste trick jeg har lært i forbindelse med programmering i Matlab er brugen af MATLAB Coder. Her laves en .m-fil om til c-kode, som stadig kan bruges igennem Matlab via en mex-fil. Det har i nogle tilfælde gjort min kode 6 gange hurtigere! Især i tilfælde, hvor det ikke er muligt at undgå for-løkker er det en god ide. Den eneste bagside er, at ikke alle matlab-kommandoer er understøttet (se http://www.mathworks.se/help/simulink/ug/f...).

Tak for heads up - det vil jeg kigge nærmere på:-)

  • 0
  • 0

Det er meget spændende at følge med i dit projekt. Det første jeg lige kom til at tænke på efter at have læst indlægget, er matrix-algebra og for-løkkerne, som også Jonas har bidt mærke i.

Du har jo sikkert gjort det, men der er rigtig meget at hente ved at bruge matrix-faktoriseringer i forbindelse med især løsning af matrix-ligninger. Afhængig af matrisernes struktur, er forskellige faktoriseringer nyttige. Og så er der selvfølgelig brug af sparsematriser, hvis der er mange nuller i dem, hvilket virkelig kan gøre en forskel i hukommelsesforbrug. Det er mine erfaringer gennem projekter på bl.a studier på DTU.

Profiling-featuren i Matlab har jeg aldrig brugt, men det er måske en god ide. Jeg har klaret mig med at udpege de passager i koden der kører mest, og så optimere der først. Som regel kan jeg godt vurdere i hovedet, nogenlunde hvor mange procent af tiden der går på de forskellige kodeblokke og så fokusere på de vigtigste først. Ellers tester jeg køretiden af de forskellige strukturer med 'tic' og 'toc' funktionerne. Og det er jo vigtigt, at man starter med at optimere på en funktion der kører f.eks. 50% af tiden fremfor en der kun kører 5% af tiden.

Jeg har altid forstået det sådan, at man netop skal bruge for-løkker til at løse iterations-opgaver, fordi de er optimeret hardwaremæssigt ved at gemme løkkens parametre i registre fremfor i cache eller memory. Et opslag i cache er rigtig meget hurtigere end et opslag i ram, men et opslag i et register er endnu hurtigere. Jeg er dog heller ikke softwareingeniør. Men jeg er ikke sikker på jeg har forstået hvad du mener med, at brug af for-løkker bør minimeres.

  • 0
  • 0

Okay, jeg havde ikke læst de andre indlæg vedrørende for-løkker. Brug af vektorisering i Matlab fremfor for-løkker. Ja det giver vist god mening. Ikke mindst den fantastisk kompakte kode. Er det meget hurtigere end for-løkker? Jeg ved i hvertfald godt, at matrixmultiplikationer i Matlab er særligt exceptionelt hurtige.

  • 0
  • 0

Du har jo sikkert gjort det, men der er rigtig meget at hente ved at bruge matrix-faktoriseringer i forbindelse med især løsning af matrix-ligninger. Afhængig af matrisernes struktur, er forskellige faktoriseringer nyttige. Og så er der selvfølgelig brug af sparsematriser, hvis der er mange nuller i dem, hvilket virkelig kan gøre en forskel i hukommelsesforbrug. Det er mine erfaringer gennem projekter på bl.a studier på DTU.

Jeg har ikke gjort dette eksplicit, men har haft kig på det. Matlabs indbyggede \-kommandoer og /-kommandoer, som jeg anvender mange steder, er baseret på en række forskellige faktoriseringer, og i den givne situation benytter Matlab den bedste faktorisering til at løse matrixligningerne - så indirekte anvender jeg matrixfaktoriseringer.

Profiling-featuren i Matlab har jeg aldrig brugt, men det er måske en god ide. Jeg har klaret mig med at udpege de passager i koden der kører mest, og så optimere der først. Som regel kan jeg godt vurdere i hovedet, nogenlunde hvor mange procent af tiden der går på de forskellige kodeblokke og så fokusere på de vigtigste først. Ellers tester jeg køretiden af de forskellige strukturer med tic og toc funktionerne. Og det er jo vigtigt, at man starter med at optimere på en funktion der kører f.eks. 50% af tiden fremfor en der kun kører 5\% af tiden.

Jeg har selv i mange sammenhænge anvendt den simplere procedure, du beskriver. Jeg kan dog varmt anbefale at bruge profiling i stedet; der er intet besværligt ved at bruge det, og det giver i min optik et langt bedre overblik og indblik i, hvordan koden kører.

Okay, jeg havde ikke læst de andre indlæg vedrørende for-løkker. Brug af vektorisering i Matlab fremfor for-løkker. Ja det giver vist god mening. Ikke mindst den fantastisk kompakte kode. Er det meget hurtigere end for-løkker? Jeg ved i hvertfald godt, at matrixmultiplikationer i Matlab er særligt exceptionelt hurtige.

Det er markant hurtigere, ja. Gram-Schmidt proceduren var oprindeligt i min kode implementeret med to for-løkker, men den inderste af disse kunne relativt nemt vektoriseres - hvilket i en konkret beregning sænkede beregningstiden fra ca. 750 sekunder til ca. 230 sekunder.

  • 1
  • 0

Enig vedr. vektorisering i stedet for for-loops i Matlab (eller for mit vedkommende Scilab). Det kører markant bedre, da det ikke fortolkes en-ad-gangen i en parser, men kører ud i underliggende biblioteker.

Da jeg ikke er så "hård" til vektorisering synes jeg det hjælper at skrive for-løkken først og derefter tænke over om det kan vektoriseres.

Fra 750 sek til 230 sek er en mærkbar forbedring, men egentlig kun en factor 3. Der kan ofte være tale om langt større forbedringer.

  • 0
  • 0

En mere drastisk tilgang kunne være at skifte programmeringssprog til for eksempel Julia (http://julialang.org/), der i mange tilfælde er hurtigere end MATLAB og lignende, og hvor for-loops ikke ødelægger hastigheden - tværtimod er det i visse tilfælde hurtigere at bruge en løkke end at vektorisere [1]. Til gengæld er sproget relativt nyt og mangler for eksempel en debugger, men der er et fornuftigt community bag og sproget i sig selv er ret veludviklet.

  • 0
  • 0

Da jeg ikke er så "hård" til vektorisering synes jeg det hjælper at skrive for-løkken først og derefter tænke over om det kan vektoriseres.

Sådan arbejder jeg også sommetider - men øvelse gør mester, og jeg kan mærke, at jeg har nemmere og nemmere ved at skrive koden vektoriseret fra begyndelsen.

Fra 750 sek til 230 sek er en mærkbar forbedring, men egentlig kun en factor 3. Der kan ofte være tale om langt større forbedringer.

Sandt, den samlede gevinst af at erstatte for-løkken med vektoriseret kode var i det konkrete tilfælde en faktor tre for kørslen af hele koden. Profiler rapporten kunne dog afsløre, at den specifikke del af koden gik fra mere end 500 sekunder til ca. 50 sekunder - dvs. ca. en faktor 10 i dette tilfælde. Dette bliver større, når jeg går fra to- til tredimensionelle simuleringer, så alt i alt er jeg udmærket tilfreds med gevinsten ved denne meget simple ændring :-)

  • 0
  • 0

En mere drastisk tilgang kunne være at skifte programmeringssprog til for eksempel Julia (http://julialang.org/), der i mange tilfælde er hurtigere end MATLAB og lignende, og hvor for-loops ikke ødelægger hastigheden - tværtimod er det i visse tilfælde hurtigere at bruge en løkke end at vektorisere [1]. Til gengæld er sproget relativt nyt og mangler for eksempel en debugger, men der er et fornuftigt community bag og sproget i sig selv er ret veludviklet.

Tak for informationen.

Jeg har selv leget med tanken om at skifte til Python, men jeg bliver i Matlab og benytter de ressourcer, som er tilgængelige her. Og så bliver Python udviklet i diverse sideprojekter i stedet :-)

  • 0
  • 0

Tak for informationen.

Jeg har selv leget med tanken om at skifte til Python, men jeg bliver i Matlab og benytter de ressourcer, som er tilgængelige her. Og så bliver Python udviklet i diverse sideprojekter i stedet :-)

Hej Jakob

Hvad med Blaze - og Anaconda? - så kan du "let" orkestrere et kluster af computere - evt. med GPUere:

A Python Compiler for Big Data:
http://continuum.io/blog/blaze
Citat: "...
Unlike NumPy, Blaze is designed to handle out-of-core computations on large datasets that exceed the system memory capacity, as well as on distributed and streaming data. Blaze is able to operate on datasets transparently as if they behaved like in-memory NumPy arrays.
...
Once a graph is evaluated, Blaze attempts to gather all available type and metadata available from the user input to inform better computation selection and scheduling.
..."

Anaconda.
Completely free enterprise-ready Python distribution for large-scale data processing, predictive analytics, and scientific computing:
https://store.continuum.io/cshop/anaconda/
Citat: "...
Cross platform on Linux, Windows, Mac
...
All Products are Free for Academic Use
...
we offer free licenses of IOPro and Accelerate to individuals at degree-granting institutions. For research institutions we offer a 1-year free license of our premium products.
..."

  • 0
  • 0

Hvad med Blaze - og Anaconda? - så kan du "let" orkestrere et kluster af computere - evt. med GPUere:

Tak for forslaget. Jeg har allerede Anaconda installeret på min computer, og når jeg laver noget i Python, er det således med denne distribution.

Jeg er dog, som nævnt ovenfor, ikke på udkig efter et nyt miljø at lave mine beregninger i. Python har været en overvejelse, men jeg bliver i Matlab til de ting, jeg skal lave i min ph.d. - og benytter de optimeringer, jeg nævnte i indlægget, samt de muligheder, Matlab har indbygget.

  • 0
  • 0

Ja profiling i MATLAB kan virkelig være til stor hjælp :)

Hvis man vil løse et stort lineært system, så er, som Rasmus Skovmand skriver, dannelsen af en sparse matrix fuldstændig essentiel. Til brug i mit speciale med et 3D finite element program (K*u = f), hvor hvert element har 30 frihedsgrader, testede jeg for sjovs skyld programmet uden brug af sparse matrix som samlingsalgoritme af K, hvorved MATLAB løb tør for hukommelse (8gb) med ca. 6000 elementer ved u = K\f.

Samles K derimod som en sparse matrix, hvilket vil sige at kun elementer forskellige fra nul lagres er jeg ikke stødt på nogen hukommelsesbegrænsninger ved løsning af systemet (150000 elementer er det højeste jeg har gidet at prøve).

En anden fordel ved sparse matrices -- ihvertfald hvad angår FEM, hvor mange elementmatricer skal samles til ét global array -- er hastigheden af selve samlingsalgoritmen. Fordi K ikke indgår i en løkke, men først bliver samlet efter f.eks. en for-løkke, skal den ikke opdateres ved hvert eneste step. Dette gør naturligvis samlingen meget hurtigere. MATLABs indbyggede sparse funktion summerer automatisk elementer op, der har samme globalt kolonne- og rækkenummer.

  • 0
  • 0

Ja profiling i MATLAB kan virkelig være til stor hjælp :)

Hvis man vil løse et stort lineært system, så er, som Rasmus Skovmand skriver, dannelsen af en sparse matrix fuldstændig essentiel. Til brug i mit speciale med et 3D finite element program (K*u = f), hvor hvert element har 30 frihedsgrader, testede jeg for sjovs skyld programmet uden brug af sparse matrix som samlingsalgoritme af K, hvorved MATLAB løb tør for hukommelse (8gb) med ca. 6000 elementer ved u = K\f.

Samles K derimod som en sparse matrix, hvilket vil sige at kun elementer forskellige fra nul lagres er jeg ikke stødt på nogen hukommelsesbegrænsninger ved løsning af systemet (150000 elementer er det højeste jeg har gidet at prøve).

En anden fordel ved sparse matrices -- ihvertfald hvad angår FEM, hvor mange elementmatricer skal samles til ét global array -- er hastigheden af selve samlingsalgoritmen. Fordi K ikke indgår i en løkke, men først bliver samlet efter f.eks. en for-løkke, skal den ikke opdateres ved hvert eneste step. Dette gør naturligvis samlingen meget hurtigere. MATLABs indbyggede sparse funktion summerer automatisk elementer op, der har samme globalt kolonne- og rækkenummer.

Interessant, tak for detaljerne om dine erfaringer:-)

De matricer, jeg arbejder med, er i udgangspunktet ikke sparse. Men jeg har overvejet, om de i visse situationer er næsten-sparse, dvs. med mange meget små elementer - som man så evt. kunne sæt lig med nul for at arbejde videre med matricerne som sparse. I visse symmetriske systemer kunne dette potentielt være brugbart i mine beregninger.

  • 0
  • 0
Bidrag med din viden – log ind og deltag i debatten