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.
That annoying moment when @MATLAB runs out of memory in a computation:-( #NeedMoreMemory #Programming #DTUFotonik pic.twitter.com/pC5DQv5eM9
— Jakob R. de Lasson (@Jakobrdl) 16. december 2013Lad 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.
Work in progress on active photonic crystal waveguides. #PhD #DTUFotonik #Nanophotonics #Research pic.twitter.com/BIbGOO4Jyj
— Jakob R. de Lasson (@Jakobrdl) 21. januar 2014For 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"!
