Detecting "a and b are the same variable" in O(1) via pointers

3 次查看(过去 30 天)
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".

采纳的回答

Friedrich
Friedrich 2012-2-3
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 个评论
Federico
Federico 2012-2-3
Interesting. So these pointers are exposed through mex but there is no pure-Matlab interface to access them?
Friedrich
Friedrich 2012-2-3
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]));
}

请先登录,再进行评论。

更多回答(1 个)

David Young
David Young 2012-2-3
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 个评论
Federico
Federico 2012-2-3
Thanks for the feedback. I guess that the difference in time is due to the fact that twice as many elements need to be fetched into the cache.
Moreover, contrary to your comment, I think I do need a separate function in my use case. Indeed, I need something that returns in O(1) in any case, and answers "certainly yes" or "probably no" to the question "is a equal to b?".
David Young
David Young 2012-2-3
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?

请先登录,再进行评论。

类别

Help CenterFile Exchange 中查找有关 Write C Functions Callable from MATLAB (MEX Files) 的更多信息

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by