Code Optimization and OOP programming

Hello :) ,

I have problems of runing time with the MatLab program I am working on, I hope someone could be able to give me a hand !

I am working with several classes and trying to use the power of OOP programming. But the size of the data I am working on is quite significant and I create huge arrays of classes object.

Before I show you part of the code in details, I explain that I am modestly familiar with the notion of MatLab code optimizing: I use the profiler to spot the slowness of my code, I pre-allocate my memory and I know what vectorization is.

I have a class called Vertix that has 6 properties, and I create an array V containing N "Vertix". N is big (around 100.000) ... Creating it and filling it is pretty fast (a few seconds), the problem is when I want to modify the following way.

I have :

 vertices2change = ... ; % something small of 1xn size, like [ 3 5 7 ]

I want to access V(3), V(5) and V(7) to modify one of their properties. So I do :

 for i=1:size(vertices2change,2)
    V(vertices2change(i)).property = smthg ;
 end

But this loop, of course, is VERY slow. Since I use it a lot in my code, this make my code run in hours, and according to the profiler, this is 99% the fault of this line...

The question is : how do I vectorize this line to make it faster ?

I already try the following but MatLab doesn't like it :

 >> V(vertices2change).property = smthg 
 Insufficient number of outputs from function on right hand side of
 equal sign to satisfy overloaded assignment.

Actually, the answer of

 >> V(vertices2change).property

correspond to V(vertices2change(1)).property. Weird right ? At least there is something I didn't get !

I hope I was clear in my explainations and that my question wasn't stupid.

Thanks in advance ! :)

[Babak]

just FYI, either say OO programming or OOP...

Answer 1

[Matt J]

But this loop, of course, is VERY slow.

Its not clear to me why it should be super-slow. Not if vertices2change consists of only 3 elements. Is 'Vertix' a handle class?

Anyway, it is a bad idea to work with object arrays of lengths like 100000. Same thing with structs. It scatters your data discontiguously across RAM, making it slow to access. It is better to combine your property data from the different V(i) into one matrix and make that a property of a scalar object V.

See also this recent, related thread,

http://www.mathworks.com/matlabcentral/answers/73715-data-structure-for-mixed-type-arrays-cellarray-dataset-structarray-struct-of-arrays-or-other

[Antoine]

It is slow because I use it a lot of time and vertices2change is in practice way bigger than 1x3, I just wanted to say that it was small compare to the size of V (hundred thousand). But I think you are right, it is slow to access the data because of the discontinuity of the RAM zones. It could be more clever to make arrays of properties directly.

So I would have something like this ?

 classdef Vertix < handle

    properties
        property1 ;
        ...
        property6 ; % let's imagine that property6 has 3 components
    end

    methods
        % constructor, more of an "allocator"
        function V = Vertix(N)
            V.property1 = zeros(1,N) ;
            ...
            V.property6 = zeros(3,N) ; % that would make array of array...
        end
    end
end

And then in the code to fill the data :

 for i = 1:N
     V.property1(i) = smthg ;
     ...
     V.property6(1,i) = smthg ; 
 end

In this way, I would solve my first problem by writing

 V.property(vertices2change) = smthg ;

And it should be way faster !

Ok thank you for the response, I will modify my code right away.

Answer 2

[Antoine]

Ok I made the modification and in fact it is way faster !

But by consequence of this modification I have an other problem that comes out and I don't know how to solve it without going in circles...

The property4 of my class Vertix is a property that can change of sizes in my work, and that I modify in a way that I add elements by concatenation. When I worked with an array of objects, I simply did :

 V(i).property4 = cat(2,V(i).property4,smthg) ;

With originaly V(i).property4 of size 1xn and smthg of size 1xm, I get V(i).property4 of size 1x(n+m).

But now that I work with properties that are matrices, I don't know how to initialize V.property4. If I initialize it like 1xN and then use cat(1,..,..), it fill my matrices with 0 (I don't like it for my work), it change dynamicly the dimension of V.property4 and it leads me to a big matrix...

If I initialize it in the maximum dimension and fill it by dealing with zero (twisted), I get Out of memory because NxN is too big for my RAM (to find a contiguous block).

Any idea please :) ?

[Matt J]

I get Out of memory because NxN is too big for my RAM (to find a contiguous block).

You could try a sparse matrix instead

V.property4=sparse(i,j,s,N,N,nzmax);

[Philip Borghesani]

I would make property4 a cell array:

V.property4{i} = cat(2,V.property4{i},smthg) ;

[Matt J]

A cell array of length 100000 will have the same RAM scattering problem as an object array of length 100000.

[Antoine]

I modified my code and use sparse matrix.

The problem of Out Of Memory is avoided, the matrix is quickly allocate and initialized (filling the first row in my case), but when I want to fill the other rows (for a given column), this is still pretty slow...

I have something like this :

 % S is my sparse matrix NxN

 S(idxA:idxB,k) = smthg ;  % slow 

 % smthg is a row vector "relatively small" (idxB-idxA+1)x1

This is slow because I use this line in a loop and the size of S is NxN with N ~ 10^4.

MatLab use column major order, maybe if I turn the matrice in the other way it could be faster to access data ?

I will try it soon, otherwise i am afraid I don't have anything else to do...

[Matt J]

No, modifying things column-wise should be fastest. Make sure you're specifying nzmax. I also hope you're not starting with S equal to all zeros. You should initialize S with as much data as you can, using the syntax,

 S=sparse(i,j,s,N,N,,nzmax)

[Matt J]

Actually, Philip's suggestion of a cell array might be the best option you have. Every time you insert into a sparse matrix, the table of non-sparse entries has to be resorted...

Maybe you could also store things in a matrix with columns of the form

 [idxA, idxB, smthg, zeros(1,pad)].'

If the smthg's are all of similar lengths, this might be too bad a way to encode things.

[Antoine]

"No, modifying things column-wise should be fastest." You mean should not be fastest ?

I start directly by writing S the way I want it to be at the beggining of my code yes. For nzmax, if I understood well it is the maximum number of non-zeros elements I will be able to write in my sparse memory ? Since I can't really have a precise estimation, I puted N*N/2. I could try to find a more precise (smaller) majoration, maybe it will get the non-sparses entries restoration faster ?

"Every time you insert into a sparse matrix, the table of non-sparse entries has to be resorted..." Yes, that's where the slowness come from.

"If the smthg's are all of similar lengths" Actually they are...

I will think about this cell array and get back to you (I need to get some sleep first xD). Thank for your help anyway !!

[Matt J]

"No, modifying things column-wise should be fastest." You mean should not be fastest ?

No, I would expect that modifying columns should be faster than modifying rows.

Answer 3

[Antoine]

I have now a decent code running, thank you very much for your help Matt J !