Why mutating cell array in a class property is so slow?

Question

For example, I have the following class:

classdef testclass < handle
    properties
            buckets
    end
    methods
        function tc = testclass(sz)
            tc.buckets = cell(1, sz);
        end
        function put(tc,k)
            tc.buckets{k}{1} = 1;
        end
    end
end

And the following example loop, where I compare performance with a plain cell array:

tm = @java.lang.System.currentTimeMillis;

for N=[100 200 400 1000 2000 4000 8000]
    tc = testclass(N);
    Tstart = tm();
    for k=1:N
        tc.put(k);
    end
    Tend = tm();
    fprintf(1, 'filling hash class (size %d): %d ms\n', N, Tend - Tstart);

    arr = cell(1,N);
    Tstart = tm();
    for k=1:N
        arr{k}{1} = 1;
    end
    Tend = tm();
    fprintf(1, 'filling cell array (size %d): %d ms\n', N, Tend - Tstart);
end

The output is:

filling hash class (size 100): 8 ms
filling cell array (size 100): 0 ms
filling hash class (size 200): 9 ms
filling cell array (size 200): 0 ms
filling hash class (size 400): 24 ms
filling cell array (size 400): 1 ms
filling hash class (size 1000): 108 ms
filling cell array (size 1000): 2 ms
filling hash class (size 2000): 370 ms
filling cell array (size 2000): 5 ms
filling hash class (size 4000): 1396 ms
filling cell array (size 4000): 10 ms
filling hash class (size 8000): 5961 ms
filling cell array (size 8000): 21 ms

As you can see, plain cell array exhibits "linear" performance (which is to be expected), but array wrapped in a class gives horrible quadratic performance.

I tested this on Matlab 2008a and Matlab 2010a.

What causes this? And how can I work around it?

Answer 1

The true power of Matlab is only available to those who know what to avoid :)

One major issue with OOP in interpreted languages (Matlab is not alone in this) is the rather spectacular overhead involved with calling methods, as you have noticed. OOP requires completely different design strategies in Matlab, Python, etc. than in C++, Fortran, etc.

Anyway, you had best avoid calling methods so often, and vectorize as much as you can.

Compare this:

clc, clear classes    
feature accel off  % to make sure JIT doesn't throw things off

tm = @java.lang.System.currentTimeMillis;

for N = [100 200 400 1000 2000 4000 8000]

    tc = testclass(N);

    % call method inside loop
    Tstart = tm();
    for k=1:N
        tc.put(k);
    end
    Tend = tm();
    fprintf(1, 'filling hash class (loop, size %d)      : %d ms\n', N, Tend - Tstart);

    % call method only once
    Tstart = tm();
    tc.put(1:N);    
    Tend = tm();
    fprintf(1, 'filling hash class (vectorized, size %d): %d ms\n', N, Tend - Tstart);

    % cell-array direct assignment, looped version
    arr = cell(1,N);
    Tstart = tm();
    for k=1:N
        arr{k}{1} = 1;
    end
    Tend = tm();
    fprintf(1, 'filling cell array (loop, size %d)      : %d ms\n', N, Tend - Tstart);

    % cell-array direct assignment, vectorized version
    arr = cell(1,N);
    Tstart = tm();
    [arr{:}] = deal({1});
    Tend = tm();
    fprintf(1, 'filling cell array (vectorized, size %d): %d ms\n\n', N, Tend - Tstart);
end

where the relevant method in testclass is modified to handle vectorized as well as looped assignments:

classdef testclass < handle
    properties
            buckets
    end
    methods
        function tc = testclass(sz)
            tc.buckets = cell(1, sz);
        end
        function put(tc,k)
            [tc.buckets{k}] = deal({1});
        end
    end
end

Results:

filling hash class (loop, size 100)      : 5 ms
filling hash class (vectorized, size 100): 0 ms
filling cell array (loop, size 100)      : 0 ms
filling cell array (vectorized, size 100): 0 ms

filling hash class (loop, size 200)      : 7 ms
filling hash class (vectorized, size 200): 0 ms
filling cell array (loop, size 200)      : 0 ms
filling cell array (vectorized, size 200): 0 ms

filling hash class (loop, size 400)      : 15 ms
filling hash class (vectorized, size 400): 1 ms
filling cell array (loop, size 400)      : 1 ms
filling cell array (vectorized, size 400): 0 ms

filling hash class (loop, size 1000)      : 36 ms
filling hash class (vectorized, size 1000): 2 ms
filling cell array (loop, size 1000)      : 2 ms
filling cell array (vectorized, size 1000): 1 ms

filling hash class (loop, size 2000)      : 73 ms
filling hash class (vectorized, size 2000): 2 ms
filling cell array (loop, size 2000)      : 4 ms
filling cell array (vectorized, size 2000): 2 ms

filling hash class (loop, size 4000)      : 145 ms
filling hash class (vectorized, size 4000): 5 ms
filling cell array (loop, size 4000)      : 9 ms
filling cell array (vectorized, size 4000): 4 ms

filling hash class (loop, size 8000)      : 292 ms
filling hash class (vectorized, size 8000): 8 ms
filling cell array (loop, size 8000)      : 18 ms
filling cell array (vectorized, size 8000): 9 ms