July 29, 2020
July 29, 2020#
I’ve always been thrown off by the fact that the Matlab programming language doesn’t support pointers. This has thrown me off in the past when trying to optimize Matlab code–it’s a whole different paradigm from C/C++ code where passing by reference or by pointer can help boost speed and memory performance significantly.
Recently I realized that you actually can use pointers within Matlab–kind of. And this method can yield a fairly significant speed boost in some situations.
In the classic reference Introduction to Algorithms by Thomas Corman, Section 10.3 is all about synthesizing pointers and objects in languages that don’t support them natively. All you need is for the language to support arrays. (This requirement is unquestionably satisfied by Matlab; the name itself is a portmanteau of Matrix Laboratory.)
Here’s the key idea: What is a pointer? An address in memory. A pointer directs you to a location in memory and allows you to reference and/or change the information at that location.
An array is simply a bunch of memory locations which sit one after the other. The first location is labeled with the index 1, the second location with 2, and so on and so forth. If the array holding the data is named A, we access the kth location in memory with the syntax A(k).
Suppose we have an variable to store the index number; for example p = 1 or p = 2 or p = 103049284. The variable p is technically a pointer. It points to an address in memory.
We can assign p new memory locations and “dereference” it:
p = 1;
A[p] % "Dereferencing" the pointer p
p = 314; % Reassigning pointer to new memory location
A[p] % "Dereferencing" p and getting value from different location
Really simple and obvious stuff. Why would this ever be useful?
Here’s an unfortunate fact of Matlab: using objects can be slow. It’s improved over time (read all updates to the answer at the previous link), but using objects (especially an array of user-defined objects) can be a lot slower than using structs or matrices with native datatypes.
As per Cormen’s book, you can synthesize an array of objects by creating a separate array for each object member. For example, suppose we’re implementing an A* search algorithm in the 2D plane. We want to create a Node class with the following members:
Node parentdouble[2] locationdouble cost_to_comedouble heuristic_value
Let’s start with the third and fourth members. I can create two arrays in Matlab: cost_to_come_array and heuristic_value_array. When I create the first Node object, I store its cost_to_come value in cost_to_come_array[1]. The second Node’s value goes in cost_to_come_array[2], and so on and so forth. We can do the same for heuristic_value. Notice that if I want to access the members of the kth Node, all I need to do is put the index k into the appropriate arrays.
Dealing with the location variable isn’t much harder. The location is just the [x,y] position of the node, and so we can create an (n x 2) array called location_array. When I create the first Node object, its x position goes in location_array[1,1] and its y position goes in location_array[1,2]. And so on and so forth.
But what about the parent attribute? In C/C++ this is generally implemented with an actual pointer. In this case however, our “pointer” is simply the index of the parent node. We can therefore create an array parent_array containing the integer indices of the parent nodes. The kth entry (parent_array[k]) contains the index or “pointer” to the parent of Node k).
So to give a concrete example, since our first Node (the “start” node) is the parent for the entire path, we’ll set parent_array(1) = 0. Since Matlab is 1 indexed, this is a useful flag–if my “pointer” ever has the value of 0, I’ll know that I’m at the start node. Like discussed previously, the start node’s location, cost_to_come and heuristic_value go in the 1st entry of the appropriate arrays.
When the second Node is created with Node 1 being its parent, we set parent_array(2) = 1. This is the pointer to Node 1 (which is Node 2’s parent). We store Node 2’s location, cost_to_come, and heuristic_value in the 2nd entry of the appropriate matrices.
That’s the essential idea. So what are the advantages and disadvantages of using this method?
As discussed earlier, from my (incomplete) testing this actually seems to speed up code quite a bit as opposed to storing an array of Node objects. In addition, this method allows you to create a very simple min-heap priority queue consisting of an array holding the “pointers” (indices) of the objects being sorted. (I’ll explain more in a future post, but the method can also be found in Cormen’s book, Chapter 6).
There are a few disadvantages to this method. The most significant is readability and complexity. When dealing with complicated objects, this method can become very verbose and unintuitive when juggling around the different arrays. In particular, implementing this method will most likely require that any relevant arrays holding the object members be passed into a function which manipulates the object. Function calls can become verbose when passing in a lot of arrays, although perhaps wrapping them in a struct could help. In addition, Matlab’s copy on write behavior only works if the arrays passed in aren’t modified, meaning if you edit the arrays passed in at all then Matlab will essentially be passing by value rather than by reference (which can hurt performance).
So in the end, this idea isn’t meant to be any kind of a magic bullet or solution for a wide class of problems. It’s just a creative hack that might have the potential to boost performance in special situations.