Tuesday, August 14, 2012

F#: speed up Monte Carlo Simulation by reducing creation of a new list

In the previous post, I learnt that creation of a new list could be much more costly than that of a new array. As such, I try to identify where in my original "List" version I can reduce creation of a new list.

Here is the original European_Option_Price function in the code:

let European_Option_Price (payout:float->float) S0 r vol T =
    let S_T x = S0 * exp((r - 0.5*(vol**2.0))*T + vol*sqrt(T)*x)
    randomNormals |> List.map S_T |> List.map payout |> List.average 
                  |> (*) (exp(-r*T))

I modify the third line by using an anonymous function to wrap up the two function calls to S_T and payout:

let European_Option_Price (payout:float->float) S0 r vol T =
    let S_T x = S0 * exp((r - 0.5*(vol**2.0))*T + vol*sqrt(T)*x)
    randomNormals |> List.map (fun x -> S_T x |> payout) |> List.average 
                  |> (*) (exp(-r*T))

The performance results are as follows:

version
option price
CPU time (ms)
absolute time (ms)
List (original)
10.118465
5,335
5,467
List (modified)
10.118465
3,993
4,035

Obviously, the improvement is significant (>25%), although it's not as big as that of "Find and Replace". Nevertheless, if you like to stick with List in Monte Carlo simulation, perhaps you can consider creating less lists in your F# functions.

By adding the anonymous function, we actually introduce some overhead because now we call S_T and payout indirectly and hence have more states to maintain on the call stack. If you like to avoid the overhead, you could choose to move the payout call to the end of the S_T function rather than using an anonymous function.

let European_Option_Price (payout:float->float) S0 r vol T =
    let S_T x = S0 * exp((r - 0.5*(vol**2.0))*T + vol*sqrt(T)*x) |> payout
    randomNormals |> List.map S_T |> List.average
                  |> (*) (exp(-r*T))


You might see a bit improvment by saving the overhead incurred by the use of an anonymous function. However, I also tried that, but the improvement seems to be immaterial in this case so I don't bother to adopt it at this moment.


No comments:

Post a Comment