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

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".

Answer 1

[Friedrich]

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

[Federico]

Interesting. So these pointers are exposed through mex but there is no pure-Matlab interface to access them?

[Friedrich]

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]));

}

Answer 2

[David Young]

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.)

[Federico]

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]

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?