Thread Subject:

for loop slows dramatically with successive iterations

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.

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.

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.

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.

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).

Anyway, here's the code:

function z_bits = Repeat_decoding(y_bits,M_repeat)
% z_bits = Repeat_decoding(y_bits,M_repeat)
%
%=============Inputs=============
% y_bits = received channel bits repeat encoded
% M_repeat = source bit repeat factor, an integer
%=============Outputs============
% z_bits = majority vote decoded serial bit stream
%

% preallocate Z
z_bits = zeros(1, length(y_bits)/M_repeat );

 hunthousands=0;

for N=1:M_repeat:length(y_bits) %N=1,4,7...

     if N>hunthousands*200000 %just used to monitor progress
         display(N);
         hunthousands = hunthousands+1;
     end

    temp=sum(y_bits(N:N+M_repeat-1)) / M_repeat;
   if( temp > 0.5)
      z_bits(N*M_repeat-(N-1)) = 1;
   end
end

On 5/11/2012 2:51 PM, Justin wrote:
> 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.
...

> function z_bits = Repeat_decoding(y_bits,M_repeat)
> % z_bits = Repeat_decoding(y_bits,M_repeat)
...

> % preallocate Z
> z_bits = zeros(1, length(y_bits)/M_repeat );
...
> for N=1:M_repeat:length(y_bits) %N=1,4,7...
...
> temp=sum(y_bits(N:N+M_repeat-1)) / M_repeat;
> if( temp > 0.5)
> z_bits(N*M_repeat-(N-1)) = 1;
> end
> end

This reminds me very much of another thread sometime back. It appears
that there can be what looks like "lazy allocation" -- the references to
the latter larger-indexed array either are finally causing a real
allocation or you're running into paging memory faults.

Watching the system properties can probably show that to be the case if
so...

I don't recall precisely the end result of that previous thread--seems
like there were ways in which one could and one could not see a real
performance--but I don't remember the which/what/why of it or whether
there was an resolution, even...

I know that was a lot of help wasn't it? :)

--

"Justin " <justinbobo1618@gmail.com> wrote in message <jojqje$nc4$1@newscl01ah.mathworks.com>...
> z_bits(N*M_repeat-(N-1)) = 1;
- - - - - - - - - -
  Your problem comes with the line

 z_bits(N*M_repeat-(N-1)) = 1;

It should read

 z_bits((N-1)/M_repeat+1) = 1;

  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 slow-down.

  You might consider the following alternative method:

 z_bits = floor(2*sum(reshape(y_bits,M_repeat,[]),1)/(M_repeat+1));

Roger Stafford

Ah, it all makes sense now. Thanks for pointing out the problem in my code.

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 sooner--in the future, I'm coming straight here for help before I struggle for hours.

Here's my new function, much cleaner than my old one--only 4 lines of code. And I could easily make it 1 line, I just kept it like this for readability.

% convert vector into a matrix
y_reshape = reshape(y_bits,M_repeat,length(y_bits)/M_repeat);
% each column is M_repeat rows and represents the repeated values

y_sum = sum(y_reshape);
% y_sum is now a vector where each element is the sum of the corresponding column of y_reshape

% divide each element by the number of repeats to get an average value
% should be between 0 and 1 inclusive
y_norm = y_sum./M_repeat;

% majority rule means just round the average value to a 0 or 1
z_bits = round(y_norm);

"Roger Stafford" wrote in message <jojv7t$e5t$1@newscl01ah.mathworks.com>...
> "Justin " <justinbobo1618@gmail.com> wrote in message <jojqje$nc4$1@newscl01ah.mathworks.com>...
> > z_bits(N*M_repeat-(N-1)) = 1;
> - - - - - - - - - -
> Your problem comes with the line
>
> z_bits(N*M_repeat-(N-1)) = 1;
>
> It should read
>
> z_bits((N-1)/M_repeat+1) = 1;
>
> 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 slow-down.
>
> You might consider the following alternative method:
>
> z_bits = floor(2*sum(reshape(y_bits,M_repeat,[]),1)/(M_repeat+1));
>
> Roger Stafford