Thumbnail pow() optimalisatie

Door: Thijs Zumbrink
05-01-2012 17:28

Machten berekenen zou heel snel moeten gaan voor integer exponenten. Immers, we kunnen recursief de macht opbreken in kleinere machten en daardoor resultaten hergebruiken, wat een logaritmische running time oplevert. Doordat in C++ de pow() functie overloaded is voor deze integer exponent moet de efficiente versie vanzelf gekozen worden, maar op de een of andere manier was mijn pow() toch de bron van veel traagte.

Valgrind

Om veel aspecten van je programma te analyseren kun je heel gemakkelijk Valgrind gebruiken. Dit is gericht op Linux programma's, ongeacht in welke taal ze geschreven zijn. Het programma emuleert een processor en draait je programma erop. Ondertussen analyseert het alles dat je programma met geheugen doet, zodat het heel gemakkelijk memory leaks, uninitialized values, dangling pointers etc. opspoort. Het vertelt je vervolgens precies waar het probleem is ontstaan en waar het is opgedoken. (Als je je programma compileert met debugging symbols zegt het precies op welke regel je moet kijken.)

Voor Valgrind zijn ook nog andere tools beschikbaar. Zo kun je cache gebruik bekijken, call graphs genereren, de heap profilen, concurrency bugs opsporen (ook diegenen die timing-afhankelijk: extreem moeilijk te debuggen), en nog veel meer!

Callgrind

Een van die tools is Callgrind. Hiermee maak je een call graph van je programma en kun je direct zien hoeveel executietijd gespendeerd wordt door welke functies en regels code. Op deze manier kun je heel makkelijk een intensief stuk code opzoeken om het te optimaliseren. Gebruikmakend van Callgrind (en visualisatietool KCacheGrind) vond ik twee instanties van pow() in een functie die 75% van de totale executietijd opslokte. De functie bevat naast pow() calls ook nog veel meer rekenwerk.

De fix

Deze pow() calls hadden integer exponenten en zouden dus voor weinig problemen moeten zorgen. Erger nog, de exponent was altijd constant, bij de ene aanroep 4 en bij de andere 5. Door dit om te schrijven naar een rijtje vermeningvuldigingen is de functie een stuk sneller geworden en neemt het nog maar 50% totale executietijd in beslag. Een verbetering van maarliefst 33% door twee regels code!

// In plaats van:
float xPow5 = pow(x, 5);

// Beter:
float xPow5 = x*x*x*x*x;

// Ik gebruik:
float xSq = x*x; // Heb ik ook nodig in een andere formule
float xPow5 = xSq * xSq * x;


Al met al zal het programma nog wel veel tijd in beslag nemen. Ik render frames van een video, waarbij voor elke pixel in elk frame de gehele omgeving gesampled moet worden om de invloed van omgevingslicht te bepalen. Dat omgevingslicht draagt op zijn beurt bij aan een stukje kleur op de render, wat gemodelleerd is met de Cook-Torrance shader (daar vindt het rekenwerk plaats). Voor een video van 10 seconden komt dit neer op 194 miljoen pow() aanroepen.

Reacties
Log in of registreer om reacties te plaatsen.