Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
FOR Loop slows down with each iteration?

Subject: FOR Loop slows down with each iteration?

From: James Ramm

Date: 17 Aug, 2010 11:44:06

Message: 1 of 12

Hi,
I have a for loop with 2 nested loops inside - i.e. it iterates through a 3D array:
for k = 1:Nz
 for i = 1:Nx
   for j = 1:Ny
     do stuff.

In the do stuff part, it simply goes through the matrix, writing each point which isnt NaN to file and updating a matrix of indices. It also updates a simple text progress bar (percentage complete: xx%). When I run through the program, from just looking at the progress bar it seems to slow down with each iteration....I was wondering why this could be...are there any common errors which would cause a loop to get progressively slower??
Thanks

Subject: FOR Loop slows down with each iteration?

From: Walter Roberson

Date: 17 Aug, 2010 12:03:05

Message: 2 of 12

James Ramm wrote:

> are there any common errors which would cause a loop to get
> progressively slower??

The most common would likely be failing to pre-allocate the output
array. Each time an array gets dynamically extended, all of the old data
has to be copied to the new (larger) space; as you go through more
iterations of the loop, there is more and more data to copy, so the
iterations get slower.

Subject: FOR Loop slows down with each iteration?

From: Andy

Date: 17 Aug, 2010 12:30:23

Message: 3 of 12

P.S. Don't write to a file inside a triple for loop. Collect all of your data and write to a file once.

Subject: FOR Loop slows down with each iteration?

From: James Ramm

Date: 17 Aug, 2010 16:50:22

Message: 4 of 12

"Andy " <myfakeemailaddress@gmail.com> wrote in message <i4dvcv$d0f$1@fred.mathworks.com>...
> P.S. Don't write to a file inside a triple for loop. Collect all of your data and write to a file once.

Well, there you have hit upon my paradox. The index array is allocated space before the loop so its not a problem. For the stuff that is written to file in the loop, its size varies according to the program input and its output size is unknown...having a variable which increases size on each iteration causes matlab to complain, hence the writing results to a file...

Subject: FOR Loop slows down with each iteration?

From: Andy

Date: 17 Aug, 2010 17:03:05

Message: 5 of 12

"James Ramm" <theres_ambrosia_there@hotmail.com> wrote in message <i4eeke$2ba$1@fred.mathworks.com>...
> "Andy " <myfakeemailaddress@gmail.com> wrote in message <i4dvcv$d0f$1@fred.mathworks.com>...
> > P.S. Don't write to a file inside a triple for loop. Collect all of your data and write to a file once.
>
> Well, there you have hit upon my paradox. The index array is allocated space before the loop so its not a problem. For the stuff that is written to file in the loop, its size varies according to the program input and its output size is unknown...having a variable which increases size on each iteration causes matlab to complain, hence the writing results to a file...

Store the individual things that are to be written to file in a cell array. You can preallocate the cell array, because you know the number of things to be written (even though you don't know their varying sizes).

Subject: FOR Loop slows down with each iteration?

From: Walter Roberson

Date: 17 Aug, 2010 18:01:54

Message: 6 of 12

Andy wrote:
> P.S. Don't write to a file inside a triple for loop. Collect all of
> your data and write to a file once.

If you have a large amount of data whose size cannot be predicted in advance,
then the cost of recording the data dynamically may turn out to exceed the
overheads of writing to disk. Writing to disk is generally done asynchronously
by the operating system when the program requests to write one or more pages;
pages were traditionally 4 K byte, but these days are more likely to be 16 K
byte. All else being equal, the larger the more pages of data you can submit
to write at one time, the less overhead will be involved, but only if those
buffers can be pre-allocated (if not then the buffer management can be more
expensive than the system overhead of writing smaller blocks of pages.)

Subject: FOR Loop slows down with each iteration?

From: James Ramm

Date: 17 Aug, 2010 20:21:21

Message: 7 of 12

Walter Roberson <roberson@hushmail.com> wrote in message <i4eirr$nro$1@canopus.cc.umanitoba.ca>...
> Andy wrote:
> > P.S. Don't write to a file inside a triple for loop. Collect all of
> > your data and write to a file once.
>
> If you have a large amount of data whose size cannot be predicted in advance,
> then the cost of recording the data dynamically may turn out to exceed the
> overheads of writing to disk. Writing to disk is generally done asynchronously
> by the operating system when the program requests to write one or more pages;
> pages were traditionally 4 K byte, but these days are more likely to be 16 K
> byte. All else being equal, the larger the more pages of data you can submit
> to write at one time, the less overhead will be involved, but only if those
> buffers can be pre-allocated (if not then the buffer management can be more
> expensive than the system overhead of writing smaller blocks of pages.)

...So writing to file in a loop is better than writing to a dynamic array? I cannot pre- allocate an array for the data that is being written as the number of data is unknown...it is basically iterating through arrays and extracting relevant data...

Subject: FOR Loop slows down with each iteration?

From: Andy

Date: 17 Aug, 2010 20:33:22

Message: 8 of 12

"James Ramm" <theres_ambrosia_there@hotmail.com> wrote in message <i4er01$ld2$1@fred.mathworks.com>...
> Walter Roberson <roberson@hushmail.com> wrote in message <i4eirr$nro$1@canopus.cc.umanitoba.ca>...
> > Andy wrote:
> > > P.S. Don't write to a file inside a triple for loop. Collect all of
> > > your data and write to a file once.
> >
> > If you have a large amount of data whose size cannot be predicted in advance,
> > then the cost of recording the data dynamically may turn out to exceed the
> > overheads of writing to disk. Writing to disk is generally done asynchronously
> > by the operating system when the program requests to write one or more pages;
> > pages were traditionally 4 K byte, but these days are more likely to be 16 K
> > byte. All else being equal, the larger the more pages of data you can submit
> > to write at one time, the less overhead will be involved, but only if those
> > buffers can be pre-allocated (if not then the buffer management can be more
> > expensive than the system overhead of writing smaller blocks of pages.)
>
> ...So writing to file in a loop is better than writing to a dynamic array? I cannot pre- allocate an array for the data that is being written as the number of data is unknown...it is basically iterating through arrays and extracting relevant data...

Which way is better will depend on the amount of data you have. And of course, if you have enough data, storing it all at once might be just impossible. You should try both to see which is faster.

As for whether or not you can preallocate, I suppose you might not have told us enough about your code inside the for loop. But it looks to me like you should preallocate as follows:

C=cell(Nx,Ny,Nz);
for k = 1:Nz
 for i = 1:Nx
   for j = 1:Ny
     C{i,j,k} = do some stuff;
   end
 end
end

Subject: FOR Loop slows down with each iteration?

From: Steven_Lord

Date: 17 Aug, 2010 20:48:11

Message: 9 of 12



"James Ramm" <theres_ambrosia_there@hotmail.com> wrote in message
news:i4er01$ld2$1@fred.mathworks.com...
> Walter Roberson <roberson@hushmail.com> wrote in message
> <i4eirr$nro$1@canopus.cc.umanitoba.ca>...
>> Andy wrote:
>> > P.S. Don't write to a file inside a triple for loop. Collect all of
>> > your data and write to a file once.
>>
>> If you have a large amount of data whose size cannot be predicted in
>> advance, then the cost of recording the data dynamically may turn out to
>> exceed the overheads of writing to disk. Writing to disk is generally
>> done asynchronously by the operating system when the program requests to
>> write one or more pages; pages were traditionally 4 K byte, but these
>> days are more likely to be 16 K byte. All else being equal, the larger
>> the more pages of data you can submit to write at one time, the less
>> overhead will be involved, but only if those buffers can be pre-allocated
>> (if not then the buffer management can be more expensive than the system
>> overhead of writing smaller blocks of pages.)
>
> ...So writing to file in a loop is better than writing to a dynamic array?
> I cannot pre- allocate an array for the data that is being written as the
> number of data is unknown...it is basically iterating through arrays and
> extracting relevant data...

At this point, I think everyone in this thread (except for you, James, as
the original poster) is just guessing at what's going on. Can you show a
(small) sample of your actual code, with the "do stuff" section from your
original posting replaced with the actual guts of the function?

If not, you might want to open your code in the Editor and check and see if
there are any Code Analyzer warnings being displayed. You could also run
your code in the Profiler (see HELP PROFILE) and check if it offers any
insight into specific lines that are proving to be a bottleneck.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: FOR Loop slows down with each iteration?

From: James Ramm

Date: 22 Aug, 2010 14:45:19

Message: 10 of 12

"Steven_Lord" <slord@mathworks.com> wrote in message <i4esib$33q$1@fred.mathworks.com>...
>
>
> "James Ramm" <theres_ambrosia_there@hotmail.com> wrote in message
> news:i4er01$ld2$1@fred.mathworks.com...
> > Walter Roberson <roberson@hushmail.com> wrote in message
> > <i4eirr$nro$1@canopus.cc.umanitoba.ca>...
> >> Andy wrote:
> >> > P.S. Don't write to a file inside a triple for loop. Collect all of
> >> > your data and write to a file once.
> >>
> >> If you have a large amount of data whose size cannot be predicted in
> >> advance, then the cost of recording the data dynamically may turn out to
> >> exceed the overheads of writing to disk. Writing to disk is generally
> >> done asynchronously by the operating system when the program requests to
> >> write one or more pages; pages were traditionally 4 K byte, but these
> >> days are more likely to be 16 K byte. All else being equal, the larger
> >> the more pages of data you can submit to write at one time, the less
> >> overhead will be involved, but only if those buffers can be pre-allocated
> >> (if not then the buffer management can be more expensive than the system
> >> overhead of writing smaller blocks of pages.)
> >
> > ...So writing to file in a loop is better than writing to a dynamic array?
> > I cannot pre- allocate an array for the data that is being written as the
> > number of data is unknown...it is basically iterating through arrays and
> > extracting relevant data...
>
> At this point, I think everyone in this thread (except for you, James, as
> the original poster) is just guessing at what's going on. Can you show a
> (small) sample of your actual code, with the "do stuff" section from your
> original posting replaced with the actual guts of the function?
>
> If not, you might want to open your code in the Editor and check and see if
> there are any Code Analyzer warnings being displayed. You could also run
> your code in the Profiler (see HELP PROFILE) and check if it offers any
> insight into specific lines that are proving to be a bottleneck.
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

Hi
I have no warnings, and the loop is like this:

for j = 1:ncellY+1
    for i = ncellX+1
        if ~isnan(dem(i,j))
           pX = xmin+((i-1)*resolution);
           pY = ymin +((ncellY-(j-1))*resolution);
           pZ = dem(i,j)

           fprintf(fid,repmat('%i ',size(3,1)),[pX pY pZ]);
           fprintf(fid, '\n');
       end
   end
end

basically, it is searching through a matrix of elevation points, and for ones which are not NaN, it assigns an X co-ordinate and y-cordinate, then writes these 3 points to file as a row vector. Eventually ending up with a n-by-3 matrix of X Y Z points. Obviously the printing to file is severely slowing the loop down...

Subject: FOR Loop slows down with each iteration?

From: dpb

Date: 22 Aug, 2010 15:01:56

Message: 11 of 12

James Ramm wrote:
> "Steven_Lord" <slord@mathworks.com> wrote in message
> <i4esib$33q$1@fred.mathworks.com>...
>>
>>
>> "James Ramm" <theres_ambrosia_there@hotmail.com> wrote in message
>> news:i4er01$ld2$1@fred.mathworks.com...
>> > Walter Roberson <roberson@hushmail.com> wrote in message >
>> <i4eirr$nro$1@canopus.cc.umanitoba.ca>...
>> >> Andy wrote:
>> >> > P.S. Don't write to a file inside a triple for loop. Collect all
>> of >> > your data and write to a file once.
>> >>
>> >> If you have a large amount of data whose size cannot be predicted
>> in >> advance, then the cost of recording the data dynamically may
>> turn out to >> exceed the overheads of writing to disk. Writing to
>> disk is generally >> done asynchronously by the operating system when
>> the program requests to >> write one or more pages; pages were
>> traditionally 4 K byte, but these >> days are more likely to be 16 K
>> byte. All else being equal, the larger >> the more pages of data you
>> can submit to write at one time, the less >> overhead will be
>> involved, but only if those buffers can be pre-allocated >> (if not
>> then the buffer management can be more expensive than the system >>
>> overhead of writing smaller blocks of pages.)
>> >
>> > ...So writing to file in a loop is better than writing to a dynamic
>> array? > I cannot pre- allocate an array for the data that is being
>> written as the > number of data is unknown...it is basically iterating
>> through arrays and > extracting relevant data...
>>
>> At this point, I think everyone in this thread (except for you, James,
>> as the original poster) is just guessing at what's going on. Can you
>> show a (small) sample of your actual code, with the "do stuff" section
>> from your original posting replaced with the actual guts of the function?
>>
>> If not, you might want to open your code in the Editor and check and
>> see if there are any Code Analyzer warnings being displayed. You
>> could also run your code in the Profiler (see HELP PROFILE) and check
>> if it offers any insight into specific lines that are proving to be a
>> bottleneck.
>>
>> --
>> Steve Lord
>> slord@mathworks.com
>> comp.soft-sys.matlab (CSSM) FAQ:
>> http://matlabwiki.mathworks.com/MATLAB_FAQ
>> To contact Technical Support use the Contact Us link on
>> http://www.mathworks.com
>
> Hi
> I have no warnings, and the loop is like this:
>
> for j = 1:ncellY+1
> for i = ncellX+1
> if ~isnan(dem(i,j))
> pX = xmin+((i-1)*resolution);
> pY = ymin +((ncellY-(j-1))*resolution);
> pZ = dem(i,j)
>
> fprintf(fid,repmat('%i ',size(3,1)),[pX pY pZ]);
> fprintf(fid, '\n');
> end
> end
> end
>
> basically, it is searching through a matrix of elevation points, and for
> ones which are not NaN, it assigns an X co-ordinate and y-cordinate,
> then writes these 3 points to file as a row vector. Eventually ending up
> with a n-by-3 matrix of X Y Z points. Obviously the printing to file is
> severely slowing the loop down...

As written, the repmat() could be removed to a fixed string outside the
nested loops as a minimum. Also w/o a lot of thought looks like some
vectorization should be possible w/ logical addressing on elements from
isfinite() (don't know if there's any speed advantage of it over
~isnan() as well).

As somebody else said, store the points in an array then write. Since
it's a counted loop, size must be known a priori so could preallocate an
array of (ncellX*ncellY,3) which is maximum size if all elements are
finite then truncate when built the zero elements. Or a little extra
logic up front to locate the finite elements and counting to derive the
actual size as well. Either would likely be faster overall.

Also, of course, when looking at speed issues, until actual have a
profile of where time is being spent for sure, one may presume the wrong
thing about what is actually the slowest portion.

--

Subject: FOR Loop slows down with each iteration?

From: James Ramm

Date: 22 Aug, 2010 23:17:23

Message: 12 of 12

Thanks to everyone, Ive followed the advice and removed all the in-loop file writing, reducing the computation time from ~14 mins to 35 seconds!

I also did a test of ~isnan against isfinite and found isfinite to be marginally quicker. However, when I changed all the ~isnan to isfinite in my program, it ran marginally (0.1s) slower....how could that be? (just curiosity, 0.1s obv isnt a problem..)

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us