SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 23rd, 2008, 2:12 pm

QuoteI used to think that it didn't make any difference whether you first loop the collumns or the rows.The differences will be even more pronounced if you use multi-threading. For some problems, I have found that loop *unrolling* can give 20% improvement, here in C++ (sorry, no Matlab):
Last edited by Cuchulainn on June 22nd, 2008, 10:00 pm, edited 1 time in total.
 
User avatar
AlistairMacArthur
Posts: 10
Joined: June 1st, 2003, 1:53 pm

Slow for-loops in Matlab

June 23rd, 2008, 3:48 pm

Is it not the case that Matlab uses BLAS libraries wherever possible? Its only possible to identify candidate matrix operations to submit to BLAS when using matrix notation ie 1./x. When using for loops it is *very* difficult (in the general case impossible) to recreate the original matrix operation so that we can submit to BLAS. Rule #1 in Matlab use matrix (or at worst vector) operations. For large matrices (as we are discussing here) the overriding problem is one of cache thrashing; The majority of optimisations done to BLAS implementations over the last couple of years focus on minimising this (eg Goto BLAS). This is why it still makes a difference in Matlab whether you access your matrix in row or column major format. I think in general you are always going skipping cache lines when your matrix is ~10mill. So, as has been mentioned, the trick is slice up your matrix into reasonable size chunks and keep running totals. As an aside, whenever we are simulating correlated underlyings we will have to perform matrix multiplication - this will always be your dominating complexity - don't bother optimising anything else (ie random number generation, brownian bridge) HTH
 
User avatar
aiQUANT
Posts: 91
Joined: June 4th, 2008, 6:20 pm

Slow for-loops in Matlab

June 23rd, 2008, 5:16 pm

Nice programming skills msperlin! Infact I first heard of that when I stumbled upon this article. There are some other ones on memory optimisation.
 
User avatar
msperlin
Posts: 608
Joined: July 10th, 2006, 6:21 pm

Slow for-loops in Matlab

June 23rd, 2008, 7:51 pm

QuoteOriginally posted by: aiQUANTNice programming skills msperlin! Infact I first heard of that when I stumbled upon this article. There are some other ones on memory optimisation.Well, thanks. But I'm still not sure whats so great about it ... That was a very good link by the way. Thanks.
Last edited by msperlin on June 22nd, 2008, 10:00 pm, edited 1 time in total.
 
User avatar
aiQUANT
Posts: 91
Joined: June 4th, 2008, 6:20 pm

Slow for-loops in Matlab

June 23rd, 2008, 7:54 pm

the smiley faces in your code!
 
User avatar
msperlin
Posts: 608
Joined: July 10th, 2006, 6:21 pm

Slow for-loops in Matlab

June 23rd, 2008, 8:05 pm

QuoteOriginally posted by: CuchulainnQuoteI used to think that it didn't make any difference whether you first loop the collumns or the rows.The differences will be even more pronounced if you use multi-threading. For some problems, I have found that loop *unrolling* can give 20% improvement, here in C++ (sorry, no Matlab):Cuchulainn, is there any intuition behind this gain in speed?
Last edited by msperlin 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, 8:07 pm

QuoteOriginally posted by: aiQUANTthe smiley faces in your code! Thats actually by accident. Every time the forum finds the string "" it puts a smiley instead of the actual characters..
 
User avatar
Cuchulainn
Posts: 62067
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Slow for-loops in Matlab

June 24th, 2008, 8:14 am

QuoteOriginally posted by: msperlinQuoteOriginally posted by: CuchulainnQuoteI used to think that it didn't make any difference whether you first loop the collumns or the rows.The differences will be even more pronounced if you use multi-threading. For some problems, I have found that loop *unrolling* can give 20% improvement, here in C++ (sorry, no Matlab):Cuchulainn, is there any intuition behind this gain in speed?mpsHere is a short motivation for the improvement.In this case (it is also known as loop unwinding) we execute the body of a loop multiple times. This is a technique to reduce the overhead of loop execution. It can help promote cache line utilization by improving data reuse. In general, loop overhead is high when each iteration has a small number of operations.
 
User avatar
msperlin
Posts: 608
Joined: July 10th, 2006, 6:21 pm

Slow for-loops in Matlab

June 24th, 2008, 8:22 am

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: msperlinQuoteOriginally posted by: CuchulainnQuoteI used to think that it didn't make any difference whether you first loop the collumns or the rows.The differences will be even more pronounced if you use multi-threading. For some problems, I have found that loop *unrolling* can give 20% improvement, here in C++ (sorry, no Matlab):Cuchulainn, is there any intuition behind this gain in speed?mpsHere is a short motivation for the improvement.In this case (it is also known as loop unwinding) we execute the body of a loop multiple times. This is a technique to reduce the overhead of loop execution. It can help promote cache line utilization by improving data reuse. In general, loop overhead is high when each iteration has a small number of operations. Ok. Thanks.
 
User avatar
AlistairMacArthur
Posts: 10
Joined: June 1st, 2003, 1:53 pm

Slow for-loops in Matlab

June 24th, 2008, 9:17 am

"In this case (it is also known as loop unwinding) we execute the body of a loop multiple times. This is a technique to reduce the overhead of loop execution. It can help promote cache line utilization by improving data reuse. In general, loop overhead is high when each iteration has a small number of operations."Loop unrolling also exposes potential parallelism that is otherwise hidden. This allows the scheduler - either in the compiler or in the processor's dynamic instruction issue - to be able to exploit instruction level parallelism (ie each instruction issued is doing close to its maximum possible work)
 
User avatar
eredhuin
Posts: 263
Joined: July 14th, 2002, 3:00 am

Slow for-loops in Matlab

June 24th, 2008, 7:12 pm

Cuch, the original MatLab was a wrapper for the fortran libraries, LINPACK and EISPACK. IIRC Cleve Moler was one of the people behind EISPACK. Matlab history
 
User avatar
spursfan
Posts: 893
Joined: October 7th, 2001, 3:43 pm

Slow for-loops in Matlab

June 25th, 2008, 3:22 am

I'd make the limitations sections even larger - it's like a cult consisting of geeks that enjoy coming up with workarounds instead of improving the core languageI had high hopes for the Excel Link toolbox but guess what - it just can't handle complex numbers - Matlab makes great play of it's facility with complex numbers but it can't be bothered to write some code that will easily return them to Excel or accept them from ExcelAnd the so-called help function is full of trivial stuff but fails to answer questions such as what format do you need for fprintf or dlmwrite to output complex numbers or even provide a list of possible delimiters (I wanted a line break) - that has a function to return output in 123 format but obviously Excel is still too new to think about (unless there are proprietary format considerations that prevent them)So I ended up using the diary command, added some variable names with semi-colons for the output I wanted in the .m files, pasted the code into the command window in order to see what the intermediate values were in a text file - but I shouldn't have had to if Excel Link performed as it should
 
User avatar
eredhuin
Posts: 263
Joined: July 14th, 2002, 3:00 am

Slow for-loops in Matlab

June 25th, 2008, 2:50 pm

spursfan, excel doesn't support complex numbers so I don't see how this is a matlab problem. You know what excel does when you type =COMPLEX(5,5) and it returns "5+5i"? It creates a string. Try it: =type(complex(1,1)) returns 2 for "text". Any complex matlab function you call from excel can trivially be wrapped by one that accepts x and y and then (in matlab) makes x+i*y before calling whatever it is you need to call. Further, you can return complex values to excel using matlab's "imag" and "real" to bifurcate your return values.fprintf and sprintf are included for the convenience of C programmers and C doesn't have complex numbers either. But this is trivial to work around:fprintf('%7f+%7fi',real(x),imag(x));
Last edited by eredhuin on June 24th, 2008, 10:00 pm, edited 1 time in total.
 
User avatar
spursfan
Posts: 893
Joined: October 7th, 2001, 3:43 pm

Slow for-loops in Matlab

June 26th, 2008, 12:25 am

since excel stores complex numbers as a text string, then excel link should be able to accept the string from excel and create a complex number in matlab - and the other way roundwhat you suggest about taking the real and imaginary parts is such a chore (though I'm happy to do it in Excel as it is so much quicker than using the built-in complex number functions)in my mind, trivial is not typing fprintf('%7f+%7fi",real(x),imag(x)) when all I ended up typing was x - even better if matlab had a special format for outputting complex numbers to a text file (it seems to manage to put them onto the screen easily enough)
 
User avatar
eredhuin
Posts: 263
Joined: July 14th, 2002, 3:00 am

Slow for-loops in Matlab

June 26th, 2008, 5:52 pm

The problem is a 3rd party add-in (Analysis ToolPak) uses an ugly kludge to represent complex numbers. That is, they store them as strings. Matlab sees this dinky kludge as a string - which it is. It then sends a string to matlab. Go on Matlab's site and report Matlab's reading this as a string as a bug if it bothers you. Or write the two second workaround I suggested.
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