ismembc – undocumented helper function

Wednesday, April 8th, 2009

Matlab has a variety of internal helper functions which are used by the main (documented) functions. Some of these helper functions are undocumented and unsupported, but may be helpful in their own right – not just as internal support functions.

In this post I want to present Matlab’s built-in ismembc helper function. This function is used within the stock Matlab ismember and setxor functions for fast processing of the core ismember functionality in “regular” cases: arrays of sorted, non-sparse, non-NaN data in which we’re only interested in the logical membership information (not the index locations of the found members). In such cases, ismembc can be used directly, saving ismember‘s sanity-checks overhead. ismembc uses the same interface (two inputs, single logical output) as ismember and can be a drop-in replacement for ismember for these “regular” cases.

The performance improvement may be significant: In a recent post, MathWorks’ Loren Shure presented different approaches for fast data retrieval, highlighting the ismember function. Let’s compare:

>> % Initial setup
>> n=2e6; a=ceil(n*rand(n,1)); b=ceil(n*rand(n,1));

>> % Run ismember several times, to rule-out JIT compilation overheads
>> tic;ismember(a,b);toc;
Elapsed time is 2.882907 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 2.818318 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 3.005967 seconds.

>> % Now use ismembc:
>> tic;ismembc(a,b);toc;
Elapsed time is 0.162108 seconds.
>> tic;ismembc(a,b);toc;
Elapsed time is 0.204108 seconds.
>> tic;ismembc(a,b);toc;
Elapsed time is 0.156963 seconds.

ismembc is actually a MEX file (%matlabroot%\toolbox\matlab\ops\ismembc.mexw32). Its source code is included in the same folder (%matlabroot%\toolbox\matlab\ops\ismembc.cpp) and is actually very readable. From the source code comments we learn that the comment in setxor about ismembc usage is misleading: that comment stated that the inputs must be real, but the source-code indicates that imaginary numbers are also accepted and that only the real-part should be sorted.

ismembc should not be used carelessly: as noted, its inputs must be sorted non-sparse non-NaN values. In the general case we should either ensure this programmatically (as done in setxor) or use ismember, which handles this for us.

The nice thing about ismembc is that its source code (ismembc.cpp) is included, so even if future Matlab releases stop using this function, you can always mex-compile the source code and use it.

Readers interested in ismembc might also be interested in its sibling help function, ismembc2, which is also a mex file located (with source-code) in the same folder as ismembc. Whereas ismembc returns an array of logical values, ismembc2 returns the index locations of the found members.

Related posts:

  1. Datenum performance – The performance of the built-in Matlab function datenum can be significantly improved by using an undocumented internal help function...
  2. sprintfc – undocumented helper function – The built-in sprintfc function can be used to quickly generate a cell-array of formatted strings. ...
  3. uisplittool & uitogglesplittool – Matlab's undocumented uisplittool and uitogglesplittool are powerful controls that can easily be added to Matlab toolbars - this article explains how...
  4. Creating a simple UDD class – This article explains how to create and test custom UDD packages, classes and objects...
  5. Profiling Matlab memory usage – mtic and mtoc were a couple of undocumented features that enabled users of past Matlab releases to easily profile memory usage. ...
  6. A few parfor tips – The parfor (parallel for) loops can be made faster using a few simple tips. ...
Categories: Medium risk of breaking in future versions, Stock Matlab function, Undocumented function

Tags: , , , ,

Bookmark and SharePrint Print

14 Responses to ismembc – undocumented helper function

  1. Pingback: Datenum performance | Undocumented Matlab

  2. Rob says:
    June 1, 2011 at 5:17 pm

    interestingly, it appears that the variable “a” does not have to be sorted for using ismembc(), but the algorithm runs much more quickly if it is.

    Reply
    • Oleg Komarov says:
      October 5, 2014 at 9:45 am

      For ismembc(), the first input needs NOT to be sorted. Follows the heuristic that tests the assertion(terminate execution with CTRL+C):

      c = 0;
while true 
    c          = c+1;
    A          = randi(1e6,1e5,1);
    B          = sort(randi(1e6,1e3,1)); 
    [idx, pos] = ismember(A,B);
    if ~isequal(idx,ismembc(A,B))
        disp('fail')
        disp(c)
        break 
    end
end

      The same holds true for ismembc2(), i.e. first input needs not to be sorted, IFF we are getting the positions under the ‘legacy’ flag:
      The pos output:

      c = 0;
while true 
    c          = c+1;
    A          = randi(1e6,1e5,1);
    B          = sort(randi(1e6,1e3,1)); 
    [idx, pos] = ismember(A,B,'legacy');
    if ~isequal(pos,ismembc2(A,B))
        disp('fail')
        disp(c)
        break 
    end
end

      To reproduce the same pos as with ismember() in >= R2012b, you do NOT need sorted A, but should have unique and sorted B.

  3. Pingback: Undocumented Matlab at Nordt Blog

  4. Vivien says:
    October 6, 2011 at 1:04 am

    It doesn’t work if it’s not sorted. The function stops as soon as it meets a higher value. The given example is bad because the function stops most of the time too early (but ismembc is indeed faster).

    >> a = [3,5]; b = [1,2,3,4,9,5];
>> ismembc(a,b)
ans =
     1     0
    Reply
    • Yair Altman says:
      October 6, 2011 at 1:14 pm

      @Vivien – the preconditions required by ismembc were indeed mentioned in the article:

      ismembc should not be used carelessly: as noted, its inputs must be sorted non-sparse non-NaN values. In the general case we should either ensure this programmatically (as done in setxor) or use ismember, which handles this for us.

  5. Pingback: sprintfc – undocumented helper function | Undocumented Matlab

  6. Ramy says:
    November 27, 2013 at 6:56 pm

    There is almost no difference in the new 2013b version of Matlab:

    >> n=2e6; a=ceil(n*rand(n,1)); b=ceil(n*rand(n,1));
>> tic;ismember(a,b);toc;
Elapsed time is 0.846894 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 0.817701 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 0.808824 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 0.817153 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 0.817318 seconds.
>> tic;ismember(a,b);toc;
Elapsed time is 0.810535 seconds.
    Reply
    • Yair Altman says:
      November 28, 2013 at 1:16 am

      @Ramy – I am not sure I understand – you ran the same ismember command several times, of course it would take a similar amount of time. If you run the same thing with ismembc you’ll see that it’s much faster. On the other hand, remember that ismembc must have sorted inputs, and your inputs are currently random…

    • Rik Wisselink says:
      July 14, 2018 at 8:40 pm

      @Yair, unfortunately, that is the same sample data as you use in your article. If you include the sort, ismembc becomes much slower to use. Interestingly, ismember on the older releases is similar to doing a sort of b and then calling ismembc, while in R2018a it has similar timings to a double sort before a call to ismembc. So sorting your own data is worth it (even with calling sort to an already sorted array, it is still faster than ismember).

      clc,n=2e6; a=ceil(n*rand(n,1)); b=ceil(n*rand(n,1)); c=sort(b);d=sort(a);
tic;ismember(a,b);fprintf('%.3f sec, ',toc);
tic;ismember(a,b);fprintf('%.3f sec, ',toc);
tic;ismember(a,b);fprintf('%.3f sec (ismember)\n',toc);
tic;ismembc(a,sort(b));fprintf('%.3f sec, ',toc);
tic;ismembc(a,sort(b));fprintf('%.3f sec, ',toc);
tic;ismembc(a,sort(b));fprintf('%.3f sec (ismembc and sort)\n',toc);
tic;ismembc(a,c);fprintf('%.3f sec, ',toc);
tic;ismembc(a,c);fprintf('%.3f sec, ',toc);
tic;ismembc(a,c);fprintf('%.3f sec (ismembc, unsorted a)\n',toc);
tic;ismembc(d,c);fprintf('%.3f sec, ',toc);
tic;ismembc(d,c);fprintf('%.3f sec, ',toc);
tic;ismembc(d,c);fprintf('%.3f sec (ismembc, sorted a)\n',toc);

      On my W10x64 machine this returns the following timings:

      %ML6.5
0.137 sec, 0.139 sec, 0.138 sec (pre-sorted a and b)
0.896 sec, 0.901 sec, 0.909 sec (ismember)
0.582 sec, 0.582 sec, 0.578 sec (sort(a),sort(b))
0.865 sec, 0.862 sec, 0.866 sec (unsorted a,sort(b))
 
%R2012b
0.120 sec, 0.119 sec, 0.119 sec (pre-sorted a and b)
0.676 sec, 0.662 sec, 0.651 sec (ismember)
0.257 sec, 0.258 sec, 0.261 sec (sort(a),sort(b))
0.676 sec, 0.673 sec, 0.639 sec (unsorted a,sort(b))
 
%R2018a
0.127 sec, 0.124 sec, 0.123 sec (pre-sorted a and b)
0.249 sec, 0.248 sec, 0.256 sec (ismember)
0.287 sec, 0.272 sec, 0.289 sec (sort(a),sort(b))
0.664 sec, 0.676 sec, 0.664 sec (unsorted a,sort(b))
    • Yair Altman says:
      July 14, 2018 at 8:55 pm

      @Rik – your outputs don’t correspond to your code, so they do not make any sense. Moreover, instead of reporting 3 separate timing instances, it would be better to report the total run-time of a loop of [say] 10-20 iterations.

    • Rik Wisselink says:
      July 15, 2018 at 4:01 pm

      I’m sorry, I edited my code after I already pasted the code here and forgot to update the code along with the output. The remarks in the posted text still stand though. Below is a 20 iteration version along with the sum timings.

      clc,n=2e6; a=ceil(n*rand(n,1)); b=ceil(n*rand(n,1)); d=sort(b);c=sort(a);
t_option=zeros(4,20);
for n_tic=1:size(t_option,2)
   tic; ismembc(c,d);              t_option(1,n_tic)=toc;
   tic; ismember(a,b);             t_option(2,n_tic)=toc;
   tic; ismembc(sort(a),sort(b));  t_option(3,n_tic)=toc;
   tic; ismembc(a,sort(b));        t_option(4,n_tic)=toc;
end
fprintf('%06.3f sec (pre-sorted a and b)\n',sum(t_option(1,:)));
fprintf('%06.3f sec (ismember)\n',          sum(t_option(2,:)));
fprintf('%06.3f sec (sort(a),sort(b))\n',   sum(t_option(3,:)));
fprintf('%06.3f sec (unsorted a,sort(b))\n',sum(t_option(4,:)));
      %ML6.5
02.835 sec (pre-sorted a and b)
19.311 sec (ismember)
12.037 sec (sort(a),sort(b))
18.909 sec (unsorted a,sort(b))
 
%R2012b
02.415 sec (pre-sorted a and b)
14.289 sec (ismember)
05.581 sec (sort(a),sort(b))
14.176 sec (unsorted a,sort(b))
 
%R2018a
02.635 sec (pre-sorted a and b)
05.794 sec (ismember)
06.050 sec (sort(a),sort(b))
14.147 sec (unsorted a,sort(b))
    • Yair Altman says:
      July 15, 2018 at 5:39 pm

      @Rik – in a vast number of real-life use-cases, we already know in advance that either a or b or both are already sorted, and in this case ismembc is still faster than ismember, to this very day.
      Even if you sort the arrays yourself (as in your 3rd usage example), ismembc is still much faster than ismember for most Matlab releases and almost as fast even on the latest release.
      To make a long story short, there is very little (or no) down-side to using ismembc, at least from a performance viewpoint, as long as your inputs are non-sparse etc.

  7. Ilya says:
    August 7, 2015 at 6:16 am

    If I’ve understood (and tested) it correctly, Inf-padding at the end of any of the 2 input vectors should not be a problem (sometimes vectors are 0 or NaN padded to preserve certain dimensionality)…
    Otherwise, a very nice post, it really helped me a lot!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *