Thread Subject: Allocating memory for a cell array of matrices

Suppose I want to allocate memory for an m x n cell array X
{m,n} for which each cell entry is a matrix of identical size (say
an MxN matrix). Can I pre-allocate with just one command? At the
moment, all I know how to do is something like

X = cell(m,n);
for i = 1:m
  for j = 1:n
     X{i,j} = zeros(M,N);
     ....
  end
end

Is there a single line that will do the same job?

Thanks,
Jim

Jim Rockford <jim.rockford1@gmail.com> wrote in message <7435e962-1791-4d2a-9ef3-e653aed7873f@d21g2000vbm.googlegroups.com>...
> Suppose I want to allocate memory for an m x n cell array X
> {m,n} for which each cell entry is a matrix of identical size (say
> an MxN matrix). Can I pre-allocate with just one command? At the
> moment, all I know how to do is something like
>
> X = cell(m,n);
> for i = 1:m
> for j = 1:n
> X{i,j} = zeros(M,N);
> ....
> end
> end
>
> Is there a single line that will do the same job?
>
> Thanks,
> Jim

Yes there is:

[X{1:m,1:n}] = deal(zeros(M,N))

Jos

Jim and Jos -- actually if the goal is to preallocate memory, then NO these two methods are *not* equivalent. The FOR-LOOP will allocate m x n separate zero blocks. The DEAL method will make each cell point toward a common shared zero matrix. So the DEAL method does not really allocate memory.

>> [x{1,1:2}]=deal(zeros(2));
>> format debug
>> x{1}

ans =


Structure address = 1792a688
m = 2
n = 2
pr = 1a124cf0
pi = 0
     0 0
     0 0

>> x{2}

ans =


Structure address = 1792a688
m = 2
n = 2
pr = 1a124cf0
pi = 0
     0 0
     0 0

>> for i=1:2
x{1,i}=zeros(2);
end
>> x{1}

ans =


Structure address = 1792a688
m = 2
n = 2
pr = 1a1250a0
pi = 0
     0 0
     0 0

>> x{2}

ans =


Structure address = 1792a688
m = 2
n = 2
pr = 1a125000
pi = 0
     0 0
     0 0

% Bruno

Jim Rockford <jim.rockford1@gmail.com> wrote in message <7435e962-1791-4d2a-9ef3-e653aed7873f@d21g2000vbm.googlegroups.com>...
> Suppose I want to allocate memory for an m x n cell array X
> {m,n} for which each cell entry is a matrix of identical size (say
> an MxN matrix). Can I pre-allocate with just one command? At the
> moment, all I know how to do is something like
>
> X = cell(m,n);
> for i = 1:m
> for j = 1:n
> X{i,j} = zeros(M,N);
> ....
> end
> end
>
> Is there a single line that will do the same job?
>
> Thanks,
> Jim

Why do you want to preallocate the cell array with non-empty entries? Aren't you just going to replace them with other entries later on anyway?

James Tursa

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <h6itu2$21r$1@fred.mathworks.com>...
>
> Why do you want to preallocate the cell array with non-empty entries? Aren't you just going to replace them with other entries later on anyway?
>

James make a good point here. Unless if the later use can justify, it is very that such preallocation helps. But only Jim an confirm.

Bruno

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <h6itu2$21r$1@fred.mathworks.com>...

> Why do you want to preallocate the cell array with non-empty entries? Aren't you just going to replace them with other entries later on anyway?
============


Unless perhaps the OP is planning to do a series of in-place modifications of X{i,j}, e.g.

for m=1:numiter.
 for i=1:N
  X{i,j}(1)=somefunction(i,j,m) %Trivial example
 end
end

Dear Jos!

> > X = cell(m,n);
> > for i = 1:m
> > for j = 1:n
> > X{i,j} = zeros(M,N);
> > ....
> > end
> > end
> >
> > Is there a single line that will do the same job?
> >
> > Thanks,
> > Jim
>
> Yes there is:
>
> [X{1:m,1:n}] = deal(zeros(M,N))

The two-liner is (much) faster than DEAL:
  X = cell(m, n);
  X(:) = {zeros(M, N)};

Kind regards, Jan

"Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message <h6nf82$41k$1@fred.mathworks.com>...
> Dear Jos!
>
> > > X = cell(m,n);
> > > for i = 1:m
> > > for j = 1:n
> > > X{i,j} = zeros(M,N);
> > > ....
> > > end
> > > end
> > >
> > > Is there a single line that will do the same job?
> > >
> > > Thanks,
> > > Jim
> >
> > Yes there is:
> >
> > [X{1:m,1:n}] = deal(zeros(M,N))
>
> The two-liner is (much) faster than DEAL:
> X = cell(m, n);
> X(:) = {zeros(M, N)};
>
> Kind regards, Jan

But again, unless OP is accessing the elements directly in downstream code like Matt's example, this pre-allocation is pointless.

James Tursa

"James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <h6nltt$u2$1@fred.mathworks.com>...

> > The two-liner is (much) faster than DEAL:
> > X = cell(m, n);
> > X(:) = {zeros(M, N)};
> >
> > Kind regards, Jan
>
> But again, unless OP is accessing the elements directly in downstream code like Matt's example, this pre-allocation is pointless.

And another point is that the two liner above produces shared data copies for the cells. So even if OP is accessing the elements of the individual cells downstream like in Matt's example, a deep copy will have to be made once an element is changed and thus nothing is gained by pre-allocating ... in fact it is wasteful to do so.

James Tursa

On Aug 20, 3:28 am, "James Tursa"
<aclassyguy_with_a_k_not_...@hotmail.com> wrote:
> Why do you want to preallocate the cell array with non-empty entries? Aren't you just going to replace them with other entries later on anyway?


James -- this cell array of matrices that I'd like to pre-allocate
are, in my example, square matrices whose entries that I will later
update. In my application, the matrices are in fact symmetric with
zero values on the diagonal. Thus, I only need to fill in the upper
triangular entries. I figured it would be convenient to pre-allocate
the zero entries so that I wouldn't have to fill in the diagonal.

I have need for code like

for i = 1:N
  for j = i+1:N
    X{i,j} = function(i,j);
  end
end

In any case, I was under the impression that it'd be beneficial to pre-
allocate each matrix in the cell array if I knew the size of each
matrix in advance. Wouldn't this be superior to simply assigning an
empty matrix to all the cell entries? I realize that you'll still get
pointers in memory, but if the size of these matrices are not
respected in the initial memory allocation, how could assigning a cell
array of empty matrices be superior to matrices of real numbers with
the correct dimensions? Perhaps there's something about memory
management that I do not grasp here.

Jim

Jim Rockford <jim.rockford1@gmail.com> wrote in message <66880d65-cf7e-4fa4-b5bf-2632cd77c617@j19g2000vbp.googlegroups.com>...
> On Aug 20, 3:28?am, "James Tursa"
> <aclassyguy_with_a_k_not_...@hotmail.com> wrote:
> > Why do you want to preallocate the cell array with non-empty entries? Aren't you just going to replace them with other entries later on anyway?
>
>
> James -- this cell array of matrices that I'd like to pre-allocate
> are, in my example, square matrices whose entries that I will later
> update. In my application, the matrices are in fact symmetric with
> zero values on the diagonal. Thus, I only need to fill in the upper
> triangular entries. I figured it would be convenient to pre-allocate
> the zero entries so that I wouldn't have to fill in the diagonal.
>
> I have need for code like
>
> for i = 1:N
> for j = i+1:N
> X{i,j} = function(i,j);
> end
> end
>
> In any case, I was under the impression that it'd be beneficial to pre-
> allocate each matrix in the cell array if I knew the size of each
> matrix in advance. Wouldn't this be superior to simply assigning an
> empty matrix to all the cell entries? I realize that you'll still get
> pointers in memory, but if the size of these matrices are not
> respected in the initial memory allocation, how could assigning a cell
> array of empty matrices be superior to matrices of real numbers with
> the correct dimensions? Perhaps there's something about memory
> management that I do not grasp here.
>
> Jim

I am not entirely sure what your application really is. In your example above, what does function(i,j) return? An n x n double matrix? If so, then pre-allocation is pointless in that case. Here is why:

A variable in MATLAB, behind the scenes, is just a structure with many fields. Those fields contain the class, size, and pointers to data among other things. For a double variable, the data area itself contains the 8-byte double precision elements. For a single variable, the data area itself contains the 4-byte single precision elements. Etc. For a cell array, however, the data area itself actually contains pointers to MATLAB variables. If you were to create what you would call a completely empty cell array, the data area would actually contain a bunch of NULL pointers. i.e., there are no actual MATLAB variables corresponding to the cells. So it is very efficient since nothing is spent creating these "empty" cells ... there is really nothing there at all. So now instead suppose you pre-allocate these cells with zero matrices. Fine. Now you have a bunch of actual matrices in these cells
(the pointers are no longer NULL, but contain the addresses of actual MATLAB variables). Now examine your loop above:

 for i = 1:N
   for j = i+1:N
     X{i,j} = function(i,j);
   end
 end

The assignment X{i,j} = function(i,j) throws away the zero matrix that *was* in the X{i,j} spot and replaces it with the results of the function(i,j) call. So that pre-allocation was a waste ... it wasn't used at all. It was simply created and then thrown away. It would have been better to not do any of the pre-allocation since it was just wasted effort, and instead just perform the loop to fill in your cells. As long as you pre-allocated X with NULL pointers for data, the X data area is not growing inside the loop so you don't get the slow-down one might expect e.g. with a double matrix that wasn't pre-allocated.

The scenario where pre-allocation makes sense is the example that Matt referred to in a previous post. That is, you are accessing the elements of the variables in the cells directly and modifying them, rather than replacing the entire cell with something else. If *that* is what you are doing, then pre-allocating the cells with zero matrices makes sense. But that is the only scenario where it does make sense, at least to me.

Contrast this with another method. Suppose you created a very large 4D array to hold your individual 2D NxN matrices. i.e., X is nxnxNxN, where nxn is the dimension of each individual matrix, and NxN is the number of individual 2D matrices. Then you would have X(:,:,i,j) = function(i,j). And then consider this loop that is similar to yours above:

 for i = 1:N
   for j = i+1:N
     X(:,:,i,j) = function(i,j);
   end
 end

Now you *would* have a major problem if you didn't preallocate, because the data area of X would be growing inside a loop, and you would get a tremendous waste of data movement eating up your CPU time.

James Tursa

On Aug 24, 3:44 am, "James Tursa"
<aclassyguy_with_a_k_not_...@hotmail.com> wrote:
> The scenario where pre-allocation makes sense is the example that Matt referred to in a >previous post. That is, you are accessing the elements of the variables in the cells directly >and modifying them, rather than replacing the entire cell with something else. If *that* is >what you are doing, then pre-allocating the cells with zero matrices makes sense. But that >is the only scenario where it does make sense, at least to me.
-----------------------------

James, that is precisely my application. I'm not rewriting the
cells. I should have written in my loop

X{i,j}(m,n) = some function

where (m,n) are the elements of the matrix in cell entry (i,j).

So, it seems that there is agreement that pre-allocation in this case
would make sense. But I have not seen a way to do it. Is this what
you're telling me, that although the pre-allocation is sensible there
is no quick way (single line command) to do it?

Jim

>> clear all
>> X(1:2,1:3) = {zeros(4)}
X =
    [4x4 double] [4x4 double] [4x4 double]
    [4x4 double] [4x4 double] [4x4 double]
>>

Jim Rockford <jim.rockford1@gmail.com> wrote in message <c47d4754-c9fd-4d71-9def-0983711ab7cf@q14g2000vbi.googlegroups.com>...
> Is this what
> you're telling me, that although the pre-allocation is sensible there
> is no quick way (single line command) to do it?
>

Exactly, there is no quick way beside for-loop.

Don't waste your CPU time with Jos or Matt's methods:

[X{1:m,1:n}] = deal(zeros(M,N)) % OR
X(1:m,1:n) = {zeros(M,N)}
...
for i=...
  for j=...
    for m=...
      for n=...
         X{i,j}(m,n) = ...
      end
   end
  end
end

Both methods allocate a *single* shared array, which get unshared and reallocated as soon as a new X{i,j} is changed in the for loop. So there is *zero* benefit of doing so.

This is the right way to do, and there is no shortcut.

for i=...
  for j=...
    X{i,j} = zeros(M,N);
    for m=...
      for n=...
         X{i,j}(m,n) = ...
      end
   end
  end
end

Bruno

Perhaps I am missing something (wouldn't be the first time), but Bruno how could you explain these results? I know you are much more CS savvy than myself, so if I have made a bad assumption, please tell me :-).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [] = cell_preall
N = 500;

X = cell(N,N); % Jan Simon's method
X(:) = {[1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02]};

% Matt Fig
Y(1:N,1:N) = {[1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02]};


Z = cell(N,N); % OP
for ii = 1:N
    for jj = 1:N
        Z{ii,jj} = [1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02];
    end
end

clear ii jj
whos % Note they all take up the same amount of memory.
% Now we will assign different values to each cell, thereby forcing
% copy-on-write behavior. This should be noticably slower for two of the
% methods(?!?)

tic
for ii = 1:N
    for jj = 1:N
        for kk = 1:3
            for mm = 1:3
                X{ii,jj}(kk,mm) = kk+mm;
            end
        end
    end
end
toc


tic
for ii = 1:N
    for jj = 1:N
        for kk = 1:3
            for mm = 1:3
                Y{ii,jj}(kk,mm) = kk+mm;
            end
        end
    end
end
toc


tic
for ii = 1:N
    for jj = 1:N
        for kk = 1:3
            for mm = 1:3
                Z{ii,jj}(kk,mm) = kk+mm;
            end
        end
    end
end
toc

whos
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



>> cell_preall
  Name Size Bytes Class Attributes

  N 1x1 8 double
  X 500x500 33000000 cell
  Y 500x500 33000000 cell
  Z 500x500 33000000 cell

Elapsed time is 2.614849 seconds.
Elapsed time is 2.617798 seconds.
Elapsed time is 2.622507 seconds.
  Name Size Bytes Class Attributes

  N 1x1 8 double
  X 500x500 33000000 cell
  Y 500x500 33000000 cell
  Z 500x500 33000000 cell
  ii 1x1 8 double
  jj 1x1 8 double
  kk 1x1 8 double
  mm 1x1 8 double

How come we don't see significant time differences if the first two methods are so much slower? If I have misunderstood the issue, please post code that shows the difference.

Matt

Matt, Matlab is so smart that sometime it hurts. When we do this:

> Z = cell(N,N); % NOT *OP*
> for ii = 1:N
> for jj = 1:N
> Z{ii,jj} = [1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02];
> end
> end
>

actually the the data is shared. If we want to make an unshared copy, we need to call a function to avoid the parse making his work. Try this:

function [] = cell_preall2
N = 500;

X = cell(N,N); % Jan Simon's method
X(:) = {[0 0 0; 0 0 0; 0 0 0]};

% Matt Fig
Y(1:N,1:N) = {[0 0 0; 0 0 0; 0 0 0]};

Z = cell(N,N); % OP
for ii = 1:N
    for jj = 1:N
        Z{ii,jj} = zeros(3); % force caling a function
    end
end

clear ii jj

% Bruno's change such that only the reallocation during copy-on-write
% better stands out

tic
for ii = 1:N
    for jj = 1:N
        X{ii,jj}(3,3) = 1;
    end
end
toc

tic
for ii = 1:N
    for jj = 1:N
        Y{ii,jj}(3,3) = 1;
    end
end
toc

tic
for ii = 1:N
    for jj = 1:N
        Z{ii,jj}(3,3) = 1;
    end
end
toc

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Command line
>> cell_preall2

Elapsed time is 0.258306 seconds.
Elapsed time is 0.255290 seconds.
Elapsed time is 0.153317 seconds. % <- faster here

  Name Size Bytes Class Attributes

  N 1x1 8 double
  X 500x500 33000000 cell
  Y 500x500 33000000 cell
  Z 500x500 33000000 cell
  ii 1x1 8 double
  jj 1x1 8 double

% Bruno

"Matt Fig" <spamanon@yahoo.com> wrote in message <h7crcj$rs0$1@fred.mathworks.com>...
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> function [] = cell_preall
> N = 500;
>
> X = cell(N,N); % Jan Simon's method
> X(:) = {[1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02]};
>
> % Matt Fig
> Y(1:N,1:N) = {[1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02]};
>
>
> Z = cell(N,N); % OP
> for ii = 1:N
> for jj = 1:N
> Z{ii,jj} = [1.0 1.01 1.02;1.0 1.01 1.02;1.0 1.01 1.02];
> end
> end

You need to be careful how the comparison is made. e.g., in the 3rd example above for the OP method, if you run that in a function or script then the assignment will be optimized and the Z cells will wind up getting shared data copies of the matrix. Whereas if you run the code from the command line the Z cells will get non-shared data copies. When I run the code above from a script then X, Y, and Z all end up with shared data copies for cells, so it is no surprise that the downstream code runs take the same time.

2nd, how much time is spent actually doing the replacement stuff vs the data copying vs the overhead of the loops? i.e., what is really being timed here? For 3x3 matrices, the amount of data copying may not amount to much compared to the other stuff going on.

So for a different test, try running this code from the command line:

N = 50;

r100 = rand(100);

X = cell(N,N); % Jan Simon's method
X(:) = {r100};

% Matt Fig
Y(1:N,1:N) = {r100};

Z = cell(N,N); % OP
for ii = 1:N
    for jj = 1:N
        Z{ii,jj} = rand(100);
    end
end

clear ii jj
whos % <-- Doesn't tell you much of *anything* about how much actual memory is used. See below.

That way X and Y will get shared data copies, but Z will not. Now run this timing test:

tic
for ii = 1:N
    for jj = 1:N
        X{ii,jj}(1,1) = ii+jj; % only 1 operation needed to force data copy
    end
end
toc

tic
for ii = 1:N
    for jj = 1:N
        Y{ii,jj}(1,1) = ii+jj; % only 1 operation needed to force data copy
    end
end
toc

tic
for ii = 1:N
    for jj = 1:N
        Z{ii,jj}(1,1) = ii+jj; % No data copy done, since not shared
    end
end
toc

whos

Now I think you will see a difference show up between the first two methods and the third method. I deleted the two innermost loops from the original posted code because they were not needed to force the data copy to take place and were just adding overhead that would bias the timing test.

The whos function call doesn't really tell you much about what is going on here, because it makes no accounting for shared data copies. i.e., a shared data copy is shown as taking the same amount of bytes as the original, when in actuality the memory isn't actually allocated for both.

James Tursa

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <h7ddv6$15e$1@fred.mathworks.com>...
>
  (snip)
>
> % Bruno

LOL ... amazing how similar our posts turned out to be, even down to eliminating the two innermost loops of the timing code! You are definitely the faster typist!

James Tursa

Dear Matt Fig!

> tic
> for ii = 1:N
> for jj = 1:N
> for kk = 1:3
> for mm = 1:3
> X{ii,jj}(kk,mm) = kk+mm;
> end
> end
> end
> end
> toc

@Bruno, James, Jim, and other Matkab cracks:
Please ignore this post. It does not concern the kernel of the discussion and is "trivial".

@Beginners and newbies:
This pice of code is more effective with a temporary variable:

tic
for ii = 1:N
    for jj = 1:N
       T = X{ii, jj};
       for kk = 1:3
            for mm = 1:3
                T(kk, mm) = kk+mm;
            end
       end
       X{ii, jj} = T;
    end
end
toc

This avoid finding the address of X{ii, jj} repeatedly. Instead of "T = X{ii, jj};" the preallocation could happen here.

Kind regards, Jan

Thanks Bruno and James, that really makes it stand out!

I will have to do some more timings myself to see when it makes sense to pre-allocate with the For loop from a performance standpoint. Obviously if someone was going to do an operation on each element of a cell (my nasty 4 For loop example, which I thought is what the OP meant) then we aren't seeing much of a difference at all.