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

Question

0 个投票

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?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

Follow Question

Answer 1

Ben 2013-5-18

在 MATLAB Online 中打开

0 个投票

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.

2 个评论
显示无隐藏无

Philip Borghesani 2013-5-20

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 2013-5-21

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.

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

回答（1 个）

2 个评论
显示无隐藏无

产品

标签

Community Treasure Hunt

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

0 个评论 显示 -2更早的评论 隐藏 -2更早的评论

回答（1 个）

2 个评论 显示 无 隐藏 无

产品

标签

另请参阅

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

2 个评论
显示无隐藏无