http://www.mathworks.com/matlabcentral/newsreader/view_thread/319984
MATLAB Central Newsreader  for loop slows dramatically with successive iterations
Feed for thread: for loop slows dramatically with successive iterations
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Fri, 11 May 2012 19:51:10 +0000
for loop slows dramatically with successive iterations
http://www.mathworks.com/matlabcentral/newsreader/view_thread/319984#876539
Justin
This loop goes through approximately 2.4 million iterations. It goes through the first 200K in a few seconds, then up through 400k in less than 30, then up to 600k in about 5 minutes, etc. I haven't bothered going past about 1.5M because by then I'm already measuring in hours. I'm trying to figure out why it slows down so significantly.<br>
<br>
The next couple paragraphs just explain the function, so if you don't care and just want to see the code, feel free to skip down.<br>
<br>
This code takes a binary bit stream (y_bits) that has had each digit duplicated M_repeat times. As I'm using it, y_bits is a vector of length~2.4 million and M_repeat is 3. <br>
<br>
For example, in the encoding part, 1010 would have been turned into 111000111000. Then bit errors were added to the encoded vector to simulate noise from transmission. This decoder looks at each chunk of 3 bits (well, M_repeat bits) and decides what the original number was based on majority rule. So if it sees 101, it assumes that there was a bit error on the middle digit and it was originally 111.<br>
<br>
Finally, it takes that digit and puts it into z_bits, which should yield the original vector that was encoded. So M_repeat*length(z_bits) = length(y_bits).<br>
<br>
Anyway, here's the code:<br>
<br>
function z_bits = Repeat_decoding(y_bits,M_repeat)<br>
% z_bits = Repeat_decoding(y_bits,M_repeat)<br>
%<br>
%=============Inputs=============<br>
% y_bits = received channel bits repeat encoded<br>
% M_repeat = source bit repeat factor, an integer<br>
%=============Outputs============<br>
% z_bits = majority vote decoded serial bit stream<br>
%<br>
<br>
% preallocate Z<br>
z_bits = zeros(1, length(y_bits)/M_repeat );<br>
<br>
hunthousands=0;<br>
<br>
for N=1:M_repeat:length(y_bits) %N=1,4,7...<br>
<br>
if N>hunthousands*200000 %just used to monitor progress<br>
display(N);<br>
hunthousands = hunthousands+1;<br>
end<br>
<br>
temp=sum(y_bits(N:N+M_repeat1)) / M_repeat;<br>
if( temp > 0.5)<br>
z_bits(N*M_repeat(N1)) = 1;<br>
end<br>
end

Fri, 11 May 2012 20:01:06 +0000
Re: for loop slows dramatically with successive iterations
http://www.mathworks.com/matlabcentral/newsreader/view_thread/319984#876541
dpb
On 5/11/2012 2:51 PM, Justin wrote:<br>
> This loop goes through approximately 2.4 million iterations. It goes<br>
> through the first 200K in a few seconds, then up through 400k in less<br>
> than 30, then up to 600k in about 5 minutes, etc. I haven't bothered<br>
> going past about 1.5M because by then I'm already measuring in hours.<br>
> I'm trying to figure out why it slows down so significantly.<br>
...<br>
<br>
> function z_bits = Repeat_decoding(y_bits,M_repeat)<br>
> % z_bits = Repeat_decoding(y_bits,M_repeat)<br>
...<br>
<br>
> % preallocate Z<br>
> z_bits = zeros(1, length(y_bits)/M_repeat );<br>
...<br>
> for N=1:M_repeat:length(y_bits) %N=1,4,7...<br>
...<br>
> temp=sum(y_bits(N:N+M_repeat1)) / M_repeat;<br>
> if( temp > 0.5)<br>
> z_bits(N*M_repeat(N1)) = 1;<br>
> end<br>
> end<br>
<br>
This reminds me very much of another thread sometime back. It appears <br>
that there can be what looks like "lazy allocation"  the references to <br>
the latter largerindexed array either are finally causing a real <br>
allocation or you're running into paging memory faults.<br>
<br>
Watching the system properties can probably show that to be the case if <br>
so...<br>
<br>
I don't recall precisely the end result of that previous threadseems <br>
like there were ways in which one could and one could not see a real <br>
performancebut I don't remember the which/what/why of it or whether <br>
there was an resolution, even...<br>
<br>
I know that was a lot of help wasn't it? :)<br>
<br>


Fri, 11 May 2012 21:10:21 +0000
Re: for loop slows dramatically with successive iterations
http://www.mathworks.com/matlabcentral/newsreader/view_thread/319984#876549
Roger Stafford
"Justin " <justinbobo1618@gmail.com> wrote in message <jojqje$nc4$1@newscl01ah.mathworks.com>...<br>
> z_bits(N*M_repeat(N1)) = 1;<br>
         <br>
Your problem comes with the line<br>
<br>
z_bits(N*M_repeat(N1)) = 1;<br>
<br>
It should read<br>
<br>
z_bits((N1)/M_repeat+1) = 1;<br>
<br>
As it stands, it skips by 9 each step so that at the end z_bits occupies 9 times as much space as you originally allocated for it. That should pretty well explain your slowdown.<br>
<br>
You might consider the following alternative method:<br>
<br>
z_bits = floor(2*sum(reshape(y_bits,M_repeat,[]),1)/(M_repeat+1));<br>
<br>
Roger Stafford

Fri, 11 May 2012 21:44:12 +0000
Re: for loop slows dramatically with successive iterations
http://www.mathworks.com/matlabcentral/newsreader/view_thread/319984#876554
Justin
Ah, it all makes sense now. Thanks for pointing out the problem in my code.<br>
<br>
Before I read your response, I had an epiphany and I completely rewrote the function and it works beautifully now. Coincidentally, I ended up using pretty similar strategy to your suggestion. I wish I'd asked soonerin the future, I'm coming straight here for help before I struggle for hours.<br>
<br>
Here's my new function, much cleaner than my old oneonly 4 lines of code. And I could easily make it 1 line, I just kept it like this for readability.<br>
<br>
% convert vector into a matrix<br>
y_reshape = reshape(y_bits,M_repeat,length(y_bits)/M_repeat);<br>
% each column is M_repeat rows and represents the repeated values<br>
<br>
y_sum = sum(y_reshape);<br>
% y_sum is now a vector where each element is the sum of the corresponding column of y_reshape<br>
<br>
% divide each element by the number of repeats to get an average value<br>
% should be between 0 and 1 inclusive<br>
y_norm = y_sum./M_repeat;<br>
<br>
% majority rule means just round the average value to a 0 or 1<br>
z_bits = round(y_norm);<br>
<br>
"Roger Stafford" wrote in message <jojv7t$e5t$1@newscl01ah.mathworks.com>...<br>
> "Justin " <justinbobo1618@gmail.com> wrote in message <jojqje$nc4$1@newscl01ah.mathworks.com>...<br>
> > z_bits(N*M_repeat(N1)) = 1;<br>
>          <br>
> Your problem comes with the line<br>
> <br>
> z_bits(N*M_repeat(N1)) = 1;<br>
> <br>
> It should read<br>
> <br>
> z_bits((N1)/M_repeat+1) = 1;<br>
> <br>
> As it stands, it skips by 9 each step so that at the end z_bits occupies 9 times as much space as you originally allocated for it. That should pretty well explain your slowdown.<br>
> <br>
> You might consider the following alternative method:<br>
> <br>
> z_bits = floor(2*sum(reshape(y_bits,M_repeat,[]),1)/(M_repeat+1));<br>
> <br>
> Roger Stafford