Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
OOP: Pre-allocation of array of handle classes

Subject: OOP: Pre-allocation of array of handle classes

From: James

Date: 1 Jul, 2009 19:24:01

Message: 1 of 7

Hello Folks,

I am trying to implement a queue for objects, which actually uses an array of object handles to store the data. Unfortunately, using an object-of-arrays is not an option.

This is the code:

classdef theQueue < handle
    properties
       thequeue;
       length;
       capacity;
    end
    methods
        function obj = theQueue()
            obj.thequeue=[[]];
            obj.length=0;
            obj.capacity=0;
        end
        function push(obj,newobject)
           if((obj.length+1 > obj.capacity) & (obj.capacity > 1))
                obj.capacity = 10*obj.capacity;
                obj.thequeue = repmat(obj.thequeue,1,10);
                obj.length = obj.length + 1;
                obj.thequeue(obj.length) = newobject;
           elseif(obj.length < obj.capacity & obj.length ~= 0)
tic
                obj.thequeue(obj.length + 1) = newobject;
toc
                obj.length = obj.length+1;
           else
                obj.thequeue = [obj.thequeue newobject];
                obj.length = obj.length+1;
                obj.capacity = obj.capacity+1;
           end
        end
    end
end

classdef theObject < handle
    properties
        index;
    end
    methods
        function obj = theObject()
            persistent count;

            if(isempty(count))
                count = 1;
            else
                count = count + 1;
            end
            obj.index = count;
        end
    end
end

Option A: Why is this so slow?
clear all
testQueue = theQueue();
%tic
for(index = 1:1000)
   testQueue.push(theObject())
end
%toc
theArray = testQueue.thequeue;
whos
pause
theArray(1:end).index


Option B: Why is this so fast?
clear all
testQueue = theQueue();
%tic
for(index = 1:1000)
   testQueue.push(single(3934972394729735235))
end
%toc
theArray = testQueue.thequeue;
whos

My original thought was that these two should take the same amount of time to execute. A handle is the same size in memory as a single (4 bytes). There is a lot of overhead in creating the objects on-the-fly, but the placement of the tic/toc shouldn't include the time it takes to create the object.

I am pre-allocating in the sense that I use repmat to create a new array 10 times larger than the previous every time the array gets full.

Is it possible for Option A to approach the same speed as Option B? Does it have to do with how I've pre-allocated?

Interestingly, if you comment out the pre-allocation case, it does NOT make any difference in performance for Option A. It DOES make a difference for Option B.

Any insights you have would be greatly appreciated!

Thanks,

-James

Subject: OOP: Pre-allocation of array of handle classes

From: James

Date: 1 Jul, 2009 19:40:17

Message: 2 of 7

"James " <M8R-ektf5s@mailinator.com> wrote in message <h2gd4h$2g7$1@fred.mathworks.com>...
> Hello Folks,
>
> I am trying to implement a queue for objects, which actually uses an array of object handles to store the data. Unfortunately, using an object-of-arrays is not an option.
>
> This is the code:
>
> classdef theQueue < handle
> properties
> thequeue;
> length;
> capacity;
> end
> methods
> function obj = theQueue()
> obj.thequeue=[[]];
> obj.length=0;
> obj.capacity=0;
> end
> function push(obj,newobject)
> if((obj.length+1 > obj.capacity) & (obj.capacity > 1))
> obj.capacity = 10*obj.capacity;
> obj.thequeue = repmat(obj.thequeue,1,10);
> obj.length = obj.length + 1;
> obj.thequeue(obj.length) = newobject;
> elseif(obj.length < obj.capacity & obj.length ~= 0)
> tic
> obj.thequeue(obj.length + 1) = newobject;
> toc
> obj.length = obj.length+1;
> else
> obj.thequeue = [obj.thequeue newobject];
> obj.length = obj.length+1;
> obj.capacity = obj.capacity+1;
> end
> end
> end
> end
>
> classdef theObject < handle
> properties
> index;
> end
> methods
> function obj = theObject()
> persistent count;
>
> if(isempty(count))
> count = 1;
> else
> count = count + 1;
> end
> obj.index = count;
> end
> end
> end
>
> Option A: Why is this so slow?
> clear all
> testQueue = theQueue();
> %tic
> for(index = 1:1000)
> testQueue.push(theObject())
> end
> %toc
> theArray = testQueue.thequeue;
> whos
> pause
> theArray(1:end).index
>
>
> Option B: Why is this so fast?
> clear all
> testQueue = theQueue();
> %tic
> for(index = 1:1000)
> testQueue.push(single(3934972394729735235))
> end
> %toc
> theArray = testQueue.thequeue;
> whos
>
> My original thought was that these two should take the same amount of time to execute. A handle is the same size in memory as a single (4 bytes). There is a lot of overhead in creating the objects on-the-fly, but the placement of the tic/toc shouldn't include the time it takes to create the object.
>
> I am pre-allocating in the sense that I use repmat to create a new array 10 times larger than the previous every time the array gets full.
>
> Is it possible for Option A to approach the same speed as Option B? Does it have to do with how I've pre-allocated?
>
> Interestingly, if you comment out the pre-allocation case, it does NOT make any difference in performance for Option A. It DOES make a difference for Option B.
>
> Any insights you have would be greatly appreciated!
>
> Thanks,
>
> -James

Sorry, forgot to include version information

-------------------------------------------------------------------------------------
MATLAB Version 7.7.0.471 (R2008b)
MATLAB License Number: 168038
Operating System: Mac OS X Version: 10.5.7 Build: 9J61
Java VM Version: Java 1.5.0_16 with Apple Inc. Java HotSpot(TM) Client VM mixed mode, sharing
-------------------------------------------------------------------------------------

Subject: OOP: Pre-allocation of array of handle classes

From: James

Date: 1 Jul, 2009 20:34:02

Message: 3 of 7

classdef theQueue < handle
    properties
       thequeue;
       length;
       capacity;
    end
    methods
        function obj = theQueue()
            obj.thequeue=[[]];
            obj.length=0;
            obj.capacity=0;
        end
        function push(obj,newobject)
           if((obj.length+1 > obj.capacity) & (obj.capacity > 1))
                obj.capacity = 10*obj.capacity;
                
                %obj.thequeue = repmat(obj.thequeue,1,10); %THE CHANGED LINE
                obj.thequeue(obj.capacity) = newobject; %THE CHANGED LINE
                
                obj.length = obj.length + 1;
                obj.thequeue(obj.length) = newobject;
           elseif(obj.length < obj.capacity & obj.length ~= 0)
tic
                obj.thequeue(obj.length + 1) = newobject;
toc
                obj.thequeue;
                obj.thequeue(1);
                obj.thequeue(1).index;
                obj.thequeue(end);
                obj.thequeue(end).index;

                obj.length = obj.length+1;
           else
                obj.thequeue = [obj.thequeue newobject];
                obj.length = obj.length+1;
                obj.capacity = obj.capacity+1;
           end
        end
    end
end

Another interesting observation: using repmat to pre-allocate results in MUCH faster code than using obj.thequeue(newLength) to pre-allocate. The latter suggestion is mentioned on this page:

http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/matlab_oop/brd4btr.html&http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_oop/br09eqz.html#brd4nrh

but it's 10 times slower than using repmat.

My original question still remains. Rephrased, what is matlab doing when it sets array(length) = newobject? Why does it take so much longer to do this than it takes to do array(length) = newnumber? In both cases, the array is pre-allocated.

Subject: OOP: Pre-allocation of array of handle classes

From: James

Date: 1 Jul, 2009 21:05:17

Message: 4 of 7

%**********
%Option C
%**********
clear all
testQueue = theQueue();
for(index = 1000:-1:1)
    tArray(index) = theObject()
end
tic
for(index = 1:1000)
    testQueue.push(tArray(index))
end
%toc
theArray = testQueue.thequeue;
whos
pause
theArray(1:end).index

%**********
%Option D
%**********
clear all
testQueue = theQueue();
tic
for(index = 1:1000)
   temp = theObject();
   testQueue.push(temp)
end
%toc
theArray = testQueue.thequeue;
whos
pause
theArray(1:end).index

Another observation. Option C is MUCH faster than Option D. Why?

Subject: OOP: Pre-allocation of array of handle classes

From: Perttu Ranta-aho

Date: 2 Sep, 2009 18:40:19

Message: 5 of 7

Old thread, but are there any new ideas?

James, did you figure out same solution to the slowness? I have similar code and same problems.

_perttu

Subject: OOP: Pre-allocation of array of handle classes

From: James

Date: 2 Sep, 2009 20:15:07

Message: 6 of 7

Actually, I have come up with a solution. It is not the most elegant solution, but it makes adding to the queue very fast. this is my new push method.

The main change is the use of a "theWrapperObject" which is a very dumb class that only contains 1 parameter, called "contents". This parameter contains an instance of whatever class you actually want to put into the queue. This adds another layer between the queue and whatever you want to put into the queue. Using this wrapper object allows repmat to preallocate the array, and it still lets you put any instance of any class into the queue.

Believe it or not, this makes "push" a LOT faster.

The next bottleneck is the "pop" function. It still runs pretty slow, but my program doesn't actually need to "pop" that often, so it's not a big deal. I suppose if you really needed a fast "pop" you could extend this "theWrapperObject" idea by keeping track of the capacity of the array, the start index of actual data, and the end index of actual data. Then, when you "pop" you simply change the index. you don't actually have to reallocate any memory or delete anything from memory.

        function push(obj,newobject)
           if((obj.length+1 > obj.capacity) & (obj.capacity > 1))
                obj.capacity = 10*obj.capacity;
                temp = repmat(theWrapperObject(),1,obj.capacity);
                for(i=obj.length+1:obj.capacity)
                     temp(i) = theWrapperObject;
                end
                for(i=1:obj.length)
                     temp(i) = obj.thequeue(i);
                end
                obj.thequeue = temp;
                obj.length = obj.length + 1;
                obj.thequeue(obj.length).contents = newobject;
           elseif(obj.length < obj.capacity & obj.length ~= 0)
                obj.thequeue(obj.length + 1).contents = newobject;
                obj.length = obj.length+1;
           else
                obj.thequeue = theWrapperObject(newobject);
                obj.length = obj.length+1;
                obj.capacity = obj.capacity+1;
           end
        end

Hope this helps!


"Perttu Ranta-aho" <rantaaho+cssm@gmail.com> wrote in message <h7me6j$22j$1@fred.mathworks.com>...
> Old thread, but are there any new ideas?
>
> James, did you figure out same solution to the slowness? I have similar code and same problems.
>
> _perttu

Subject: OOP: Pre-allocation of array of handle classes

From: Perttu Ranta-aho

Date: 3 Sep, 2009 10:44:03

Message: 7 of 7

"James " <M8R-ektf5s@mailinator.com> wrote in message <h7mjob$4kq$1@fred.mathworks.com>...
> Actually, I have come up with a solution. It is not the most elegant solution, but it makes adding to the queue very fast. this is my new push method.
>
> The main change is the use of a "theWrapperObject" which is a very dumb class that only contains 1 parameter, called "contents". This parameter contains an instance of whatever class you actually want to put into the queue. This adds another layer between the queue and whatever you want to put into the queue. Using this wrapper object allows repmat to preallocate the array, and it still lets you put any instance of any class into the queue.
>
> Believe it or not, this makes "push" a LOT faster.
>

Thanks. After rechecking it seems that your original option C is the most practical for my application. With my code, creating 1000x1 array of "theObjects" takes something like 1.2 seconds, not very fast but I can live with that. Storing the array of theObjects to the property of theContainer takes around 60ms. But creating the array directly to theContainer takes 48 seconds! And it slows down nonlinearly when size of the array increases.

Having theWrapperObject is not practical for me, was it faster than the option C in your case? Or just "cleaner".


_perttu

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us