Detecting "a and b are the same variable" in O(1) via pointers
3 views (last 30 days)
Show older comments
I know Matlab uses copy-on-write; that is, if I assign a=b and then never modify a and b, they point to the same chunk of memory. So, in theory, it should be possible to detect that a and b are two copies of the very same matrix with a O(1) pointer comparison, no matter how large they are, in contrast to something like all(a==b). Is there a way to do it in practice?
Alternative formulation, if you are familiar with Java: Matlab's comparisons work like Java's a.equals(b). Is there anything that works like java's a==b?
Use case: I would like to implement low-rank matrices by storing nxr vectors u,v such that M=u*v' is the sparse matrix, and r<<n.
The sum of u1*v1'+ u2*v2' in general has rank 2r, however, if u1==u2 then I can just sum v1 and v2 without any rank increase. In order to optimize for these cases, I need a fast way to check whether u1==u2. Typically this case will arise from u1 and u2 being constructed with the same matrix and never modified, so it is a good tradeoff to check only for "address equality".
0 Comments
Accepted Answer
Friedrich
on 3 Feb 2012
Hi,
if you need O(1) try a mex function:
#include "mex.h"
void mexFunction( int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[] )
{
if ((mwSize)mxGetPr(prhs[0]) == (mwSize)mxGetPr(prhs[1]))
mexPrintf("equal \n");
else
mexPrintf("not equal \n");
}
There is not error checking so far. So be carefull. But basically, it takes the pointer to the data and check if its the same adress.
>> a = rand(100);
>> b = a;
>> equal_test(a,b)
equal
Or:
>> a = rand(100);
>> b = a(1);
>> equal_test(a,b)
not equal
Or
>> a = {'text',[1 3 4]};
>> b = a
>> equal_test(a,b)
equal
2 Comments
Friedrich
on 3 Feb 2012
Yes, they are read only inputs to a mex. So you can get the adress pretty fast and easy. But you cant modify them. This will most likly crash ML.
In order to add a return value to that mex function simply do:
void mexFunction( int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[] )
{
if (nrhs == 2)
plhs[0] = mxCreateLogicalScalar((mwSize)mxGetData(prhs[0]) == (mwSize)mxGetData(prhs[1]));
}
More Answers (1)
David Young
on 3 Feb 2012
I tried experimenting (in ver 2011b). I used
a = rand(5000);
b = a;
tic; isequal(a, b); toc
to test. On my laptop, the time was about 0.05s (fastest over many trials).
This very slow time indicates that isequal does not do a pointer equality test before checking the data. This seems to me very surprising: it's such an obvious optimisation.
I then updated the last element of b and timed again. The comparison time was consistently 50% greater after the copy. It puzzled me that updating b made any consistent difference to the time if pointer equality isn't checked, but I expect it's a cache effect.
This isn't really an answer - more a suggestion that if someone does not give a better reply it might be worth contacting MathWorks support to ask why isequal is so slow in the trivial case of identical pointers. (There's no need for a separate user function for this, since MATLAB doesn't allow pointer manipulation - isequal should just do it efficiently.)
2 Comments
David Young
on 3 Feb 2012
OK, yes I see that point, though if getting "no" was much faster than the operations you need to perform in that case, an efficient isequal would still help.
But indeed, an "isidentical" would give you just what you need. I wonder if a MEX function can reliably and simply check this?
See Also
Categories
Find more on Write C Functions Callable from MATLAB (MEX Files) in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!