SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Y0da
Topic Author
Posts: 387
Joined: August 7th, 2007, 4:48 pm

Slow for-loops in Matlab

June 19th, 2008, 4:32 pm

Let's say I want to price a knock-out barrier optionusing Matlab with Monte Carlo.How do people address the issue of for-loops beingridiculously slow in Matlab?I know one can just make the random paths in the verystart and put them into a big matrix. But this isn'tvery helpful if one needs many (say 10 million)simulations, because of memory shortage.What approaches do people use to write usableMonte Carlo code in Matlab?
 
User avatar
aiQUANT
Posts: 91
Joined: June 4th, 2008, 6:20 pm

Slow for-loops in Matlab

June 19th, 2008, 5:28 pm

Check this out. I normally vectorize where possible. If still a problem I'd code in C and write a mex interface to call from matlab.
Last edited by aiQUANT on June 18th, 2008, 10:00 pm, edited 1 time in total.
 
User avatar
msperlin
Posts: 608
Joined: July 10th, 2006, 6:21 pm

Slow for-loops in Matlab

June 19th, 2008, 9:40 pm

QuoteOriginally posted by: aiQUANTCheck this out. I normally vectorize where possible. If still a problem I'd code in C and write a mex interface to call from matlab.Yep, matlab was just not build for big loops. I've seen the mex interface give out 5X - 10X improvement in speed over looped matlab code, so, as aiQuant already pointed out, this could be something to try out.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

Slow for-loops in Matlab

June 20th, 2008, 1:16 am

You might try a for loop on memory-efficient chunks of data (e.g., process 10,000 paths in a matrix, repeat 1,000 times). That will maximize use of Matlab's low-level array handling.
 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 20th, 2008, 10:46 am

QuoteHow do people address the issue of for-loops being ridiculously slow in Matlab?1 Use C++ (just kidding)2 loop optimisation techniques, esp loop unrolling (here3 Multicore (superlinear speedup...)QuoteI know one can just make the random paths in the verystart and put them into a big matrix. But this isn'tvery helpful if one needs many (say 10 million)simulations, because of memory shortage.Nope. Might be better to generate 1d arrays for each draw.
Last edited by Cuchulainn on June 19th, 2008, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 20th, 2008, 10:51 am

QuoteOriginally posted by: Traden4AlphaYou might try a for loop on memory-efficient chunks of data (e.g., process 10,000 paths in a matrix, repeat 1,000 times). That will maximize use of Matlab's low-level array handling.Would this be loop tiling
 
User avatar
tristram
Posts: 10
Joined: March 13th, 2008, 3:33 pm

Slow for-loops in Matlab

June 20th, 2008, 2:00 pm

QuoteOriginally posted by: Y0da Let's say I want to price a knock-out barrier option using Matlab with Monte Carlo.How do people address the issue of for-loops beingridiculously slow in Matlab?They are not so slow as they used to be a few years ago. The JIT compiler has helped a lot.QuoteI know one can just make the random paths in the verystart and put them into a big matrix. But this isn'tvery helpful if one needs many (say 10 million)simulations, because of memory shortage.How many time periods are you looking at?I expect you will need to loop through the time periods, but within each period you can probably have MATLAB work on a vector of 10 million simulations at a time. This part should be pretty fastc.f. something in C. the point here is that you will perhaps loop through 8760 hours or 365 days, but you shouldn't normally have to ask MATLAB to loop through the 10 million simulations. Do all of them in one go.10 million seems to me like a lot of simulations. Do you really have that much faith in your input data that you need to run such a large sample size?Your choices are:1. Buy more memory, and run 64 bit MATLAB2. Break you computations down into (say) 10 chunks of 1 million3. Post some example code and see if anyone can suggest improvements.4. Use the MATLAB profiler to identify the bottlenecksI suggest you take these in reverse order, although memory is cheap. I used to say that the best things about MATLAB were that it had superb graphics capabilities, it was available on every platform, and that for bigger problems you just needed to run it on a bigger computer.For several years now the number of well supported platforms seems to have been declining, and graphics hasn't been quite so good since Java came along, but I am pleased to see the return of 64 bit support.Next on my list is support for Solaris on x86/x64...
 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 20th, 2008, 4:30 pm

Quote1. Buy more memory, and run 64 bit MATLAB2. Break you computations down into (say) 10 chunks of 1 million3. Post some example code and see if anyone can suggest improvements.4. Use the MATLAB profiler to identify the bottlenecksI suggest you take these in reverse order, although memory is cheap.This is an expensive option! Memory is cheap, not developers 5. Use loop optimisation techniques. And code inspection.
 
User avatar
Y0da
Topic Author
Posts: 387
Joined: August 7th, 2007, 4:48 pm

Slow for-loops in Matlab

June 20th, 2008, 4:46 pm

Heh I think I will just go with Cuchulainn's joke advice of using C++!Seems like the best advice!
 
User avatar
Y0da
Topic Author
Posts: 387
Joined: August 7th, 2007, 4:48 pm

Slow for-loops in Matlab

June 20th, 2008, 4:48 pm

QuoteOriginally posted by: tristramThey are not so slow as they used to be a few years ago. The JIT compiler has helped a lot.Hmm I'm still finding it too slow compared to C#.By slow I mean VERY slow. I'm not familiar withany JIT compiler though as I have not compiledanything.
 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 20th, 2008, 4:51 pm

QuoteOriginally posted by: Y0daHeh I think I will just go with Cuchulainn's joke advice of using C++!Seems like the best advice!Big problems need a big language
 
User avatar
tristram
Posts: 10
Joined: March 13th, 2008, 3:33 pm

Slow for-loops in Matlab

June 23rd, 2008, 7:25 am

QuoteOriginally posted by: CuchulainnQuoteThis is an expensive option! Memory is cheap, not developers 5. Use loop optimisation techniques. And code inspection.Memory is cheaper all the time, but that does not excuse us from reviewing the codewe write. The MATLAB profiler is an excellent tool which is trivial to use. >> profile on>> [a,b] = myfun(c,d,e);>> profile reportIt generates a function by function, line by line report of all the code used, detailing total time spent, number of calls, and the occasional piece of advice. If you have never used it before then you really should give it a try. Use it to inspect your code, and to optimise your loops.
 
User avatar
tristram
Posts: 10
Joined: March 13th, 2008, 3:33 pm

Slow for-loops in Matlab

June 23rd, 2008, 8:02 am

QuoteOriginally posted by: Y0daQuoteOriginally posted by: tristramThey are not so slow as they used to be a few years ago. The JIT compiler has helped a lot.Hmm I'm still finding it too slow compared to C#.By slow I mean VERY slow. I'm not familiar withany JIT compiler though as I have not compiledanything.The JIT compiler runs behind the scenes as part of the MATLAB interpreter. You don't need to compile any code yourself. In theory it recognises things such as nested loops and runs themmuch more efficiently than previous versions of MATLAB might have achieved. In practice, itis still best to vectorise your code whenever possible. When working with large arrays, it is alsoworth considering that MATLAB stores its data by row and then by column. Consider the following:x = rand(2000,2000);[m,n] = size(x);y = zeros(m,n);for i = 1:m for j = 1:n y(i,j) = 1 / x(i,j); endendThis is slow, as the inner loop requires accessing data from subsequent columns. The data are stored m locations apart in memory.a = zeros(m,n);for j = 1:n for i = 1:m y(i,j) = 1 / x(i,j); endendThis is faster, accessing data from subsequent rows, which will be stored in the next memory location.z = 1 ./ x;This is fastest of all. Wherever possible, operate on the whole matrix or vector at once.If you can't work on the whole matrix, work on a column at a time, rather than a row at a time.
 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 23rd, 2008, 11:47 am

Quotefor i = 1:mfor j = 1:ny(i,j) = 1 / x(i,j);endendThis is slow, as the inner loop requires accessing data from subsequent columns. The data are stored m locations apart in memory.a = zeros(m,n);for j = 1:nfor i = 1:my(i,j) = 1 / x(i,j);endendSo it seems that ML uses column-ordered access, like Fortran. C uses row-ordered. Kind of surprising since I suspect (??) Matlab is written in C.
Last edited by Cuchulainn on June 22nd, 2008, 10:00 pm, edited 1 time in total.
 
User avatar
msperlin
Posts: 608
Joined: July 10th, 2006, 6:21 pm

Slow for-loops in Matlab

June 23rd, 2008, 12:49 pm

This is a very good discussion. I used to think that it didn't make any difference whether you first loop the collumns or the rows.Just to bring some numbers to the discussion, this is the times I got in my matlab:___Results Time for 1 (row/col loop) -> 0.32302Time for 2 (col/row loop) -> 0.21222Time for 3 (matrix operation) -> 0.050236Time for 4 (row loop) -> 0.11249Time for 5 (col loop) -> 0.049939___It seems that using a col loop (iterating the columns) is the same as the vectorized matrix operation.Here's the code I used:___clear;N=2000;x = rand(N,N);[m,n] = size(x);y = zeros(m,n);% Test 1tic;for i = 1:m for j = 1:n y(i,j) = 1 / x(i,j); endendtime(1)=toc;% Test 2tic;for j = 1:n for i = 1:m y(i,j) = 1 / x(i,j); endendtime(2)=toc;% Test 3tic;y = 1 ./ x;time(3)=toc;% Test 4tic;for i = 1:m y(i, = 1./ x(i,;endtime(4)=toc;% Test 5tic;for j = 1:n y(:,j) = 1./x(:,j);endtime(5)=toc;fprintf(1,'\n\nResults \n\n');fprintf(1,['Time for 1 (row/col loop) -> ' num2str(time(1)) '\n']);fprintf(1,['Time for 2 (col/row loop) -> ' num2str(time(2)) '\n']);fprintf(1,['Time for 3 (matrix operation) -> ' num2str(time(3)) '\n']);fprintf(1,['Time for 4 (row loop) -> ' num2str(time(4)) '\n']);fprintf(1,['Time for 5 (col loop) -> ' num2str(time(5)) '\n']);
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On