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.
[…] This question reminded me of a similar case that I answered exactly two years ago, of improving the performance of the built-in ismember function. In both cases, the solution to the performance question can be found by simply using Matlab’s built-in profiler in order to extract just the core processing functionality. […]
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.
For ismembc(), the first input needs NOT to be sorted. Follows the heuristic that tests the assertion(terminate execution with CTRL+C):
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:
To reproduce the same pos as with ismember() in >= R2012b, you do NOT need sorted A, but should have unique and sorted B.
[…] and infos. (Click here) Especially the performance // hidden functions are to be looked at. The ismembc2 tipp, hell yeah « One […]
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).
@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.
[…] bumping into them within the m-code of standard functions. Such was the case, for example, of the ismembc function, that I described here back in 2009, and the dtstr2dtnummx function that I described in 2011. Today […]
There is almost no difference in the new 2013b version of Matlab:
@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…
@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).
On my W10x64 machine this returns the following timings:
@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.
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.
@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.
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!