[PDF] Writing Fast MATLAB Code 3 Array Preallocation. Matlab's

View - Download Writing Fast MATLAB Code

Previous PDF

Next PDF

Pascal Getreuer, February 2009

Contents

Page

1 Introduction1

2 The Proler3

3 Array Preallocation 5

4 JIT Acceleration7

5 Vectorization9

6 Inlining Simple Functions 14

7 Referencing Operations 16

8 SolvingAx=b19

9 Numerical Integration 22

10 Signal Processing26

11 Miscellaneous29

12 Further Reading31

1

Introduction

Matlabis aprototypingenvironment, meaning it focuses on the ease of development with language

exibility, interactive debugging, and other conveniences lacking in performance-oriented languages like

C andFortran. WhileMatlabmay not be as fast as C, there are ways to bring it closer.DisclaimerThis is not a beginner's tutorial toMatlab, but a tutorial on

performance. The methods discussed here are generally fast, butno claim is

madeon what is fastest. Use at your own risk.Before beginning our main topic, let's step back for a moment and ask ourselves what we really want. Do

we want the fastest possible code?|if so, we should switch to a performance language like C. Probably

more accurately, we want to spend less timetotalfrom developing, debugging, running, and until nally obtaining results. This section gives some tips on working smart, not hard.

M-Lint Messages

In more recent versions ofMatlab, the integrated editor automatically gives feedback on possible code

errors and suggested optimizations. These messages are helpful in improving a program and in learning

more aboutMatlab.fork = 1:NumTrials r = rand; x(k) = runsim(r); end hist(x); Plot histogram of simulation outputs p xpmight be growing inside a loop. Consider preallocating for speed.Hold the mouse cursor over :::::::::::::::underlined codeto read a message. O r,see all M-Lin tmessages at once with Tools!M-Lint!Show M-Lint Report.

Organization

?Use a separate folder for each project. A separate folder for each project keeps related things together and simplies making copies and backups of project les. ?Write header comments, especially H1. The rst line of the header comment is called the H1 comment. Typehelp(cd)to get a listing of all project les and their H1 comments. 1 ?Save frequent console commands as a script. If you nd yourself repeating certain commands on the console, save them as a script. Less typing means fewer opportunities for typos.

Avoid losing data

?Don't useclear allin a script. This is an unfortunate common practice|any important variables in the base workspace will be irretrievably lost. ?Beware of clobber. \File clobber" refers to the kind of data loss when a le is accidentally overwritten with another one having the same lename. This phenomenon can occur with variables as well: >>result = bigoperation(input1);% Store the result of a t imeconsumingoperation >>result = bigoperation(input2);% Run again with another input Variableresultwas clobbered and the rst output was lost. ?Beware of what can crash MATLAB. WhileMatlabis generally reliable, crashes are possible when using third-party MEX functions or extremely memory-intensive operations, for example, with video and very large arrays. Now with good working habits covered, we begin our discussion of writing fastMatlabcode. The rest

of this article is organized by topic, rst on techniques that are useful in general application, and next

on specic computational topics (table of contents is on the rst page). 2 2

The Proler

Matlab5.0 (R10) and newer versions include a tool called the proler that helps identify bottlenecks in a program. Use it with theprofilecommand: profile on Turn the proler on profile off Turn it back o profile clear Clear prole statistics profile report View the results from the proler For example, consider proling the following function:functionresult = example1(Count) for k = 1:Count result(k) = sin(k/50); if result(k) <0.9 result(k) = gammaln(k); end endTo analyze the eciency this function, rst enable and clear the proler, run the function, and then view the prole report: >>profileon , profileclear >>example1(5000); >>profilereport

There is a slight parsing overhead when running code for the rst time; run the test code twice and time

the second run. Theprofiler reportcommand shows a report. Depending on the system, proler results may dier from this example.MATLAB Prole Report: Summary

Report generated 30-Jul-2004 16:57:01

Total recorded time: 3.09 s

Number of M-functions: 4

Clock precision: 0.016 s

3

Function List

Name Time Time Time/call Self time Location

example13.09 100.0% 1 3.094000 2.36 76.3%~/example1.mgammaln0.73 23.7% 3562 0.000206 0.73 23.7%../toolbox/matlab/specfun/gammaln.mprofile0.00 0.0% 1 0.000000 0.00 0.0%../toolbox/matlab/general/profile.mprofreport0.00 0.0% 1 0.000000 0.00 0.0%../toolbox/matlab/general/profreport.mClicking the \example1" link gives more details:

Lines where the most time was spentLine Number Code Calls Total Time % Time

4result(k) = sin(k/50);5000 2.11 s 68%

7result(k) = gammaln(k);721 0.84 s 27%

6if result(k) < -0.95000 0.14 s 5%Totals3.09 s 100%The most time-consuming lines are displayed, along with time, time percentage, and line number. The

most costly lines are the computations on lines 4 and 7.

Another helpful section of the prole report is \M-Lint Results," which gives feedback from the M-Lint

code analyzer. Possible errors and suggestions are listed here.

M-Lint resultsLine number Message

4`result' might be growing inside a loop. Consider preallocating for speed.

7`result' might be growing inside a loop. Consider preallocating for speed.(Preallocation is discussed in the next section.)

The proler has limited time resolution, so to prole a piece of code that runs too quickly, run the test

code multiple times with a loop. Adjust the number of loop iterations so that the time it takes to run

is noticeable. More iterations yields better time resolution. The proler is an essential tool for identifying bottlenecks and per-statement analysis, however, for more accurate timing of a piece of code, use thetic/tocstopwatch timer. >>tic; example1(5000); toc;

Elapsed time is 3.082055 seconds

For serious benchmarking, also close your web browser, anti-virus, and other background processes that

may be taking CPU cycles. 4 3

Array Preallocation

Matlab's matrix variables have the ability to dynamically augment rows and columns. For example, >>a = 2 a = 2 >>a(2,6) = 1 a =

2 0 0 0 0 0

0 0 0 0 0 1

Matlabautomatically resizes the matrix. Internally, the matrix data memory must be reallocated

with larger size. If a matrix is resized repeatedly|like within a loop|this overhead can be signicant.

To avoid frequent reallocations,preallocatethe matrix with thezeroscommand.

Consider the code:a(1) = 1;

b(1) = 0; for k = 2:8000 a(k) = 0.99803 *a(k1)0.06279*b(k1); b(k) = 0.06279 *a(k1) + 0.99803*b(k1);

endThis code takes 0.47 seconds to run. After theforloop, both arrays are row vectors of length 8000,

thus to preallocate, create emptyaandbrow vectors each with 8000 elements.a = zeros(1,8000);% Preallocation

b = zeros(1,8000); a(1) = 1; b(1) = 0; for k = 2:8000 a(k) = 0.99803 *a(k1)0.06279*b(k1); b(k) = 0.06279 *a(k1) + 0.99803*b(k1);

endWith this modication, the code takes only 0.14 seconds (over three times faster). Preallocation is often

easy to do, in this case it was only necessary to determine the right preallocation size and add two lines.

5 What if the nal array size can vary? Here is an example: a = zeros(1,10000);

Preallocate

count = 0; for k = 1:10000 v = exp(rand *rand); if v >0.5% Conditionally add to array count = count + 1; a(count) = v; end end a = a(1:count); Trim extra zeros from the

results The average run time of this program is 0.42 seconds without preallocation and 0.18 seconds with it.

Preallocation is also benecial for cell arrays, using thecellcommand to create a cell array of the desired size. 6 4

JIT Acceleration

Matlab6.5 (R13) and later feature the Just-In-Time (JIT) Accelerator for improving the speed of M-functions, particularly with loops. By knowing a few things about the accelerator, you can improve its performance. The JIT Accelerator is enabled by default. To disable it, type \featureaccel off " in the console, and \featureaccel on " to enable it again. As ofMatlabR2008b, only a subset of theMatlablanguage is supported for acceleration. Upon

encountering an unsupported feature, acceleration processing falls back to non-accelerated evaluation.

Acceleration is most eective when signicant contiguous portions of code are supported. ?Data types:Code must use supported data types for acceleration:double(both real and complex),logical,char,int8{32,uint8{32. Somestruct,cell,classdef, and function handle usage is supported. Sparse arrays are not accelerated. ?Array shapes:Array shapes of any size with 3 or fewer dimensions are supported. Changing the shape or data type of an array interrupts acceleration. A few limited situations with 4D arrays are accelerated. ?Function calls:Calls to built-in functions and M-functions are accelerated. Calling MEX func- tions and Java interrupts acceleration. (See also page 14 on inlining simple functions.) ?Conditionals and loops:The conditional statementsif,elseif, and simpleswitchstatements are supported if the conditional expression evaluates to a scalar. Loops of the formfor k=a:b, for k=a:b:c, andwhileloops are accelerated if all code within the loop is supported.

In-place computation

Introduced inMatlab7.3 (R2006b), the element-wise operators (+,.*, etc.) and some other functions can be computed in-place. That is, a computation like x = 5 *sqrt(x.ˆ2 + 1); is handled internally without needing temporary storage for accumulating the result. An M-function can also be computed in-place if its output argument matches one of the input arguments. x = myfun(x); function x = myfun(x) x = 5 *sqrt(x.ˆ2 + 1); return To enable in-place computation, the in-place operation must be within an M-function (and for an in-

place function, the function itself must be called within an M-function). Currently, there is no support

for in-place computation with MEX-functions. 7

Multithreaded Computation

Matlab7.4 (R2007a) introduced multithreaded computation for multicore and multiprocessor com-

puters. Multithreaded computation accelerates some per-element functions when applied to large arrays

(for example,.^,sin,exp) and certain linear algebra functions in the BLAS library. To enable it, select

File!Preferences!General!Multithreading and select \Enable multithreaded computation." Fur- ther control over parallel computation is possible with the Parallel Computing Toolbox?usingparfor andspmd.

JIT-Accelerated Example

For example, the following loop-heavy code is supported for acceleration:functionB = bilateral(A,sd,sr,R)

The bilateral image denoising filter

B = zeros(size(A));

for i = 1:size(A,1) for j = 1:size(A,2) zsum = 0; for m = R:R if i+m >= 1 && i+m<= size(A,1) for n = R:R if j+n >= 1 && j+n<= size(A,2) z = exp((A(i+m,j+n)A(i,j))ˆ2/(2*sdˆ2))... exp((mˆ2 + nˆ2)/(2*srˆ2)); zsum = zsum + z;

B(i,j) = B(i,j) + z

*A(i+m,j+n); end end end end

B(i,j) = B(i,j)/zsum;

end endFor a 128128 input image andR= 3, the run time is 53:3 seconds without acceleration and 0:68 seconds with acceleration. 8 5

Vectorization

A computation isvectorizedby taking advantage of vector operations. A variety of programming

situations can be vectorized, and often improving speed to 10 times faster or even better. Vectorization

is one of the most general and eective techniques for writing fast M-code. 5.1

V ectorizedComputations

Many standardMatlabfunctions are \vectorized": they can operate on an array as if the function had been applied individually to every element. >>sqrt([1,4;9,16]) ans = 1 2

3 4>>abs([0,1,2,5,6,7])

ans =

0 1 2 5 6 7

Consider the following function:functiond = minDistance(x,y,z) Find the min distance between a set of points and the origin nPoints = length(x); d = zeros(nPoints,1);

Preallocate

for k = 1:nPoints

Compute

distance for every point d(k) = sqrt(x(k)ˆ2 + y(k)ˆ2 + z(k)ˆ2); end d = min(d); Get the minimum

distance For every point, its distance from the origin is computed and stored ind. For speed, arraydis

preallocated (see Section 3). The minimum distance is then found withmin. To vectorize the distance computation, replace theforloop with vector operations:functiond = minDistance(x,y,z) Find the min distance between a set of points and the origin d = sqrt(x.ˆ2 + y.ˆ2 + z.ˆ2);

Compute

distance for every point d = min(d); Get the minimum distance The modied code performs the distance computation with vector operations. Thex,yandzarrays are rst squared using the per-element power operator,.^(the per-element operators for multiplication and division are.*and./). The squared components are added with vector addition. Finally, the square root of the vector sum is computed per element, yielding an array of distances. (A further improvement: it is equivalent to computed = sqrt(min(x.^2 + y.^2 + z.^2))). 9 The rst version of theminDistanceprogram takes 0.73 seconds on 50000 points. The vectorized version takes less than 0.04 seconds, more than 18 times faster. Some useful functions for vectorizing computations: 5.2quotesdbs_dbs14.pdfusesText_20

[PDF] append matlab list

[PDF] append matlab save

[PDF] append matlab string

[PDF] append matlab table

[PDF] append matlab vector

[PDF] apple accessories

[PDF] apple provisioning utility apu

[PDF] apple provisioning utility download

[PDF] apple support

[PDF] applescript indesign tutorial

[PDF] applet program for event handling in java

[PDF] application approach business

[PDF] application approach database

[PDF] application approach meaning in hindi

[PDF] application approach means