Re: FYI: smarter indexing by logical masks

[Judd Storrs]

This is pretty cool!

Is it possible to somehow pre-compute/convert the mask? I've often
used find() to pre-convert a mask into index form because I think that
improves performance when the mask is used multiple times (but it may
have been a habit that I picked up when I was working primarily in IDL
where this is part of the collective folk wisdom). e.g. things along
these lines:

mask = find(a > 0) ;
a(mask) = b(mask) ;

I've been playing with the new code a bit and I think the find() trick
defeats the new optimization? I tried to create a simple where.oct
that converts its input into the new smart mask but I think I've
missed something

#include <octave/oct.h>

DEFUN_DLD(where, args, ,
          "Convert mask to index")
{
  idx_vector idx = args(0).index_vector() ;
  return octave_value(idx);
}

Spoiler alert: something's wrong here because 'where' is slower than
using the raw boolean matrix. Here's the modified benchmark code I've
been using:


for n = [1e5 1e6 1e7 4e7]
  printf ("n = %d\n", n);
  a = rand(n,1);
  b = rand(n,1);
  c = zeros(n,1);

  mask = a > 0.9;
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("sparse mask:        1st: %f, 2nd: %f\n", t1, t2);
  mask = find(a > 0.9);
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("sparse mask(find):  1st: %f, 2nd: %f\n", t1, t2);
  mask = where(a > 0.9);
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("sparse mask(where): 1st: %f, 2nd: %f\n", t1, t2);

  mask = a > 0.1;
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("dense mask:         1st: %f, 2nd: %f\n", t1, t2);
  mask = find(a > 0.1);
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("dense mask(find):   1st: %f, 2nd: %f\n", t1, t2);
  mask = where(a > 0.1);
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("dense mask(where):  1st: %f, 2nd: %f\n", t1, t2);

  a > 0.0;
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("full mask:          1st: %f, 2nd: %f\n", t1, t2);
  mask = find(a > 0.0);
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("full mask(find):    1st: %f, 2nd: %f\n", t1, t2);
  mask = where(a > 0.0);
  tic; c(mask) = a(mask) + b(mask); t1 = toc;
  tic; c(mask) = a(mask) + b(mask); t2 = toc;
  fprintf ("full mask(where):   1st: %f, 2nd: %f\n", t1, t2);

endfor


This is the output I get (core2 duo @ 1.80GHz).


n = 100000
sparse mask:        1st: 0.000999, 2nd: 0.000244
sparse mask(find):  1st: 0.000489, 2nd: 0.000264
sparse mask(where): 1st: 0.000327, 2nd: 0.000222
dense mask:         1st: 0.003210, 2nd: 0.004524
dense mask(find):   1st: 0.003246, 2nd: 0.002669
dense mask(where):  1st: 0.002386, 2nd: 0.002292
full mask:          1st: 0.002051, 2nd: 0.004716
full mask(find):    1st: 0.004231, 2nd: 0.003856
full mask(where):   1st: 0.004140, 2nd: 0.003120
n = 1000000
sparse mask:        1st: 0.012595, 2nd: 0.008671
sparse mask(find):  1st: 0.008518, 2nd: 0.008409
sparse mask(where): 1st: 0.007252, 2nd: 0.008931
dense mask:         1st: 0.040465, 2nd: 0.035385
dense mask(find):   1st: 0.038676, 2nd: 0.037124
dense mask(where):  1st: 0.036798, 2nd: 0.032833
full mask:          1st: 0.033531, 2nd: 0.035070
full mask(find):    1st: 0.041958, 2nd: 0.039313
full mask(where):   1st: 0.041469, 2nd: 0.038953
n = 10000000
sparse mask:        1st: 0.132680, 2nd: 0.086522
sparse mask(find):  1st: 0.087629, 2nd: 0.086389
sparse mask(where): 1st: 0.077222, 2nd: 0.074444
dense mask:         1st: 0.369931, 2nd: 0.350971
dense mask(find):   1st: 0.355203, 2nd: 0.367536
dense mask(where):  1st: 0.361620, 2nd: 0.361944
full mask:          1st: 0.355967, 2nd: 0.355466
full mask(find):    1st: 0.389125, 2nd: 0.391282
full mask(where):   1st: 0.388657, 2nd: 0.391113
n = 40000000
sparse mask:        1st: 0.524230, 2nd: 0.329079
sparse mask(find):  1st: 0.334702, 2nd: 0.334690
sparse mask(where): 1st: 0.318233, 2nd: 0.318034
dense mask:         1st: 1.391669, 2nd: 1.341700
dense mask(find):   1st: 1.350176, 2nd: 1.355216
dense mask(where):  1st: 1.359566, 2nd: 1.355399
full mask:          1st: 1.354963, 2nd: 1.353266
full mask(find):    1st: 1.482584, 2nd: 1.483595
full mask(where):   1st: 1.482001, 2nd: 1.483312


--judd