Why does setting individual elements in a large matrix take so long?

I have a sub-function that was taking a really long time, so I profiled it (Matlab 2012b). Here is the relevant excerpt:

    function [dslope, endb] = fixStream(s, b, dslope, endb)
        for i=1:length(s.u)
            ui = s.u(i);
            vi = s.v(i);
            ds = dslope(vi,ui);
            if ds < b
                b = ds;
                if b < 0
                    break;
                end
            end
            assert(numel(ui)==1 && numel(vi)==1);

            dslope(vi,ui) = 0; %ds - b;
        end

        endb(s.id) = b;

When I fire up the profiler, it tells me that the dslope(vi,ui) = 0 line is what is causing the problem -- only 291 calls takes 18.9 seconds!! dslope is a big (10800x10800) double matrix and ui and vi are just integer indexes into that matrix. When I try to reproduce the problem in stand alone code, I can't do it -- this works fine (elapsed time of basically nothing for the for loop):

    N = 10800;
    z = rand(N);
    uv = floor(rand(1000,2)*N)+1;

    tic;
    for i=1:size(uv,1)
        z(uv(i,1),uv(i,2)) = 0;
    end
    toc

What could possibly be going on here?

Answer 1

[Ben]

I've worked around the problem, but the workaround doesn't make any sense to me. This is the complete text of the M file I'm using to demonstrate the problem (this version takes interminably long to run):

    function dslope = fixHeads(dslope, heads)

    endb = containers.Map('KeyType','uint32','ValueType','double');

    stime = tic;
    ltime = tic;
    for h=1:length(heads)
        if ~endb.isKey(heads(h).id)
            ds0 = dslope(heads(h).v(1),heads(h).u(1));
            dslope = fixStream(dslope(heads(h).v(1),heads(h).u(1)), dslope, endb);
        end

        if toc(ltime) > 10
            dispProgress(stime, h, length(heads));
            ltime = tic;
        end
    end

    end

    function [dslope] = fixStream(x, dslope, ~)
        dslope(5000,2000) = 0;
    end

If I change just the dslope = fixStream... line to

    dslope = fixStream(ds0, dslope, endb);

...then the program works fine -- as speedy as expected, 3.5 orders of magnitude faster. Why does adding an intermediate variable to the calling function cause the same statement in a subfunction to run 3.5 orders of magnitude faster? Because Matlab is crazy, as far as I know.

[Philip Borghesani]

The precalculation of the value ds0 is allowing the inplace optimization to take place without it each call to fixStream must copy dslope when it is modified.

[Ben]

Wow, I would have never guessed. I read the article and understand the idea of in-place optimization, but why would passing an argument that involves dslope prevent the optimization? Shouldn't Matlab just compute the values of the arguments and then pass those values to fixStream? fixStream would then separately recognize that input argument 2 should be modified in-place to produce the output argument. I don't understand why making the ds0 computation explicit should change any of the in-place behavior...but then again, I think the inputname function is ridiculous also.