Sunday, 17 August 2008

Pebble v1 Call Graph

Following up on my recent post about a C++ implementation of the Mersenne Twister pseudo-random number generator (PRNG), I decided to find out just how much the performance of the PRNG actually affects a Monte Carlo system such as Pebble. Clearly, the random number generation is a critical part of the procedure, but as I'm about to show, it is definitely not the slowest part of Pebble, by a long way.

The valgrind tool allows a programmer to check their programs for many things, including memory leaks (the original goal of the valgrind project). One of the neat things it does is function call profiling and graphing. The idea is simple, you run a program inside valgrind using the callgrind option, and it tracks every function call made within the program. This lets you figure out how many times a function is being called, and how much of the program execution time is spent within a given function, allowing you to easily profile the code and determine functions or classes which are good candidates for optimisation.

Here is the call graph for Pebble v1, which uses a C++ implementation of the Mersenne Twister which I wrote last summer, rather than the new one I have recently posted about.


(Click for larger version)


The random number generation, performed by Pebble::Math::Random::MersenneTwister::getDouble and getLong, account for a mere 3.33% of the time spent in the event generator function Pebble::EventGenerator::generate. In contrast, finding minima of the probability distribution functions (using Pebble::Math::Utility::Minimiser::getMinimum) accounts for 31.29%, and integrating the PDFs for normalisation purposes (using Pebble::Math::Calculus::RombergIntegrator::integrate) accounts for 50.82% of the time spent generating events.

It is clear from this that, if I want to improve on the speed of generation in "Pebble v2", I need to focus my efforts on efficient minimia-finding and numerical integration functions.

There is also 7.47% of the time taken to generate events spent adding particles to an Event object, using the Pebble::Event::addParticle function. A lot of this time is accounted for by the memory allocation, and as I mentioned in my previous post, eliminating such object-oriented extravagances, while maintaining a sensible object-oriented design for the important parts of the program, should help to boost the speed of any new version.

No comments:

Post a Comment