Pi, Monte Carlo, and SVG fun with some requestAnimationFrame() thrown in

To dive into some performance research and testing, I needed a example that ran some JS loop action and created lots of nodes for your friend the DOM. Why not use a simple Pi approximation with a graphical representation? Enter Monte Carlo and ets find some Pi!

What is this Monte Carlo Method? AKA Monte Carlo Experiments comprise a set of methods using random sampling to arrive at a result. This method is good to use if its physically impossible say to try all combinations or in other case when the problem can not be worded in a closed form. The process is named after the casino. Seems the author’s uncle gambled at the Monte Carlo in NV quite a bit. Yes, Mathematics does have humor!

How to apply the Monte Carlo method to approximate Pi? Throw darts! Consider a dartboard inscribed in a square and consider the top right quadrant only. Assume its a unit circle and unit square as well. Randomly through n darts. By random, I mean random, no aiming! Find the ratio p of m/n where m is the number of darts landing inside the circle. This ratio approximates the area of the quarter circle.

Area = pi * r ^ 2, eh? Since its a unit circle, Area = pi. Throw in a 1/4 and thus we have an approximation!

Now for some code! My first stab at it is here dartPi.html and looks like this:

Monte Carlo One

Nice and red quarter circle there for ya. The Spinner graphic, also in SVG, is there as a performance indicator of sorts. If it stops spinning, your browser is blocked up. Go ahead and enter say a 1000 to test it out. Notice a slight pause in the spinner? Crank it up to 10000 and mash start. Yeah, nasty, eh? Oh by the way, it does not work so well on a iPhone, reader beware.

Enter requestAnimationFrame()! After some thought I realized that as I was throwing random darts, I was drawing them straight away. JS is fast. Create DOM nodes still pretty fast. Inserting DOM nodes with the browser taking over on each insert to try and render and paint these nodes, not so fast. In fact slow. requestAnimationFrame() Can help out here. What the heck is this cat? It tells the browser, hey dude, I want to animate something, go and do your repaint fun and call this call back when you are ready for me. This brings us to dartPi2.html

Take a look at how the approxPi( ) method was changed up. Instead of a simple for-loop, we now use requestAnimationFrame() to do our loop bidding. Go ahead and test this one out with 10000 darts! Note how the spinner keeps on spinning. Now this works smooth as silk, albeit slow, but has the added benefit of actually animating the darts individually. We could likely fiddle with things, say animate 10 or so darts per frame and still look good. Browsers and machines vary so greatly though, this is hazardous, so better to use some dynamic subset cardinality and determine when best to call requestAnimationFrame() to pass work on to the next frame. A green threading if you will.

The penultimate example dartPi3.html separates out some of the work a bit further to realize that the simple loop to generate the random dart positions is indeed fast and not noticeably blocking until the numbers are really high. The animations are removed as well. This of course exposes just how expensive it is to create the SVGDOM elements and insert them into the big old DOM tree.

Now we turn our sites onto a different approach in example four dartPi4.html As we saw previously, creating SVGDOM elements AND inserting them to the DOM iteratively is well, quite expensive. Would WebWorkers help perhaps? Lets see, the computational work is simply creating a simple array of cartesian data, nothing terribly taxing really at relatively low sample size, say < 500k or so. No much to gain with WebWorkers unless we go beyond those numbers, entirely possible if we want. What about the SVGDOM element creation? WebWorkers have no access to the DOM! oops. This leads us to knowing we can't use them for DOM manipulation either, all that is on the main mother thread. We are left with just tuning what we have and tweaking it. Can we perhaps not create all the SVGDOM elements? Why sure! In example four I have done just that. Instead of creating the elements by hand, I instead just create one big fat string, a SVG document in fact, but not a DOM element as of yet. Then I just play the old el.innerHTML = myString game. Bamm! This sped things up quite a bit, only one re-render and re-paint phase to handle. But alas, at some point, say around 10k samples, you can start to see the pause. If you break out the console UI in your browser you should see the line I’m inserting into the DOM. This is logged just before setting the innerHTML property. You can get a idea just how long the re-rendering is taking.

So, we’ve played around a bit enjoying ourselves and learned a couple things, issues with performance of this or that and some cheap ways to address them. These ways are certainly not the solution to all life’s problems, there’s a towel for that, but they are useful in some use cases.

Happy trails!


This entry was posted in Blog, CSS3, HTML5, JavaScript, Techy, Universal Mind. Bookmark the permalink.