2

I'm trying to implement a 8 puzzle program using the manhattan heuristic using OOP in matlab, with each node represented by an object "state". However, i'm having lost of speed problems implementing an object array for queue. After lots of trial and error, this is the fastest i could go (i hate using global objects but it seems that any attempts at passing the array or using an object for it slows it down tremendously):

.classdef state < handle    
.    properties
.        position; %3x3 array
.        moves;  
.        blank;
.        parent;
.        prevmove;
.        mdist;
.   end

....

queue is preallocated

queue = repmat(state,1,5000);

.function newfront = q(item,front)

.global queue;
.if isempty(front)
.    newfront = 1;
.    queue(1) = item;
.else
.    for i = front:-1:0
.        if i == 0
.            break;
.        end
.        a = item.mdist;        
.        b = queue(i).mdist;
.        if (a < b)
.            break;
.        else
.            queue(i+1) = queue(i);
.        end    
.    end
.    newfront = front + 1;
.    queue(i+1) = item;
.end
.end

Using MATLAB profiler:

eightpuzzle                     1       67.941 s    2.550 s 
eightpuzzle>q                   4722    59.657 s    59.657 s    
....
118 queue(i+1) = queue(i);     2583916  29.064 s    48.7%   
120 end                        2583916  16.202 s    27.2%   
114 b = queue(i).mdist;        2587318  4.357 s     7.3%    
113 a = item.mdist;            2587318  2.783 s     4.7%    
115 if (a < b)                 2587318  2.721 s     4.6%

is there anyway to make it run faster? interesting thing to note was that by using

a = item.mdist;        
b = queue(i).mdist;
if (a < b)
...

instead of

if (item.mdist < queue(i).mdist)

overall runtime was already halved.

Thanks!

Oh Sing Kiat
  • 21
  • 2

2 Answers2

1

I don't know if it might related to this topic about general OOP slowness in MATLAB: Is MATLAB OOP slow or am I doing something wrong?

And here's yet another link about slow behaviour of handle classes, but it's likely fixed so far since the bug was reported years ago: http://www.mathworks.com/matlabcentral/newsreader/view_thread/288746

Community
  • 1
  • 1
tim
  • 9,896
  • 20
  • 81
  • 137
1

There is a large amount of memory overhead when using object arrays in MATLAB, just as in structure arrays. Each field of each array element is its own mxArray and that adds significant memory overhead. Consider using a 1x1 structure with non-scalar fields, rather than a 1xN structure with scalar fields - it will be substantially smaller in memory, and the access to each field will be much faster.

An example:

A 1x100 structure array with two scalar fields "a" and "b" requires (100*2) + 1 mxArray objects in memory.

A 1x1 structure array with two non-scalar fields "a" and "b" each of size 1x100 requires 3 mxArray objects in memory.

Your array of objects is very similar to a structure array, where the fields of each array element can be thought of as pointers. Let's say you have an object array "obj" that is 1xN with fields "a" and "b". Referencing the Kth object field's "a":

obj(K).a

This is an index operation and also an mxArray pointer dereference to the field "a".

I concede that using a scalar object would make your code less intuitive, but that's a trade-off you'll have to weigh.

siliconwafer
  • 732
  • 4
  • 9
  • thanks siliconwafer for the explanation, i guess since MATLAB is built towards matrix operations a small number of large arrays is better than a large number of small arrays. However, the code is an assignment to illustrate OOP so going the other way around doesn't make sense. I had initially made queue an object on its own with methods but the performance was terrible. What i dont understand is aren't handle objects supposed to work like pointers but the slow way they are performing doesn't make sense. Calling a handle object from an array is much slower than calling it from a variable. – Oh Sing Kiat Feb 02 '12 at 16:11