GrB_Vector_select (or GrB_Matric_select) accepts a mask M, but GB_selector essentially ignores it

[stevenzengg]

Users of the above operations will notice that the entire input A is scanned unconditionally, and the mask is applied only after the fact in GB_accum_mask. This is acknowledged in Source/select/GB_selector.c, but makes the mask on select essentially decorative. In practice, assign, apply, mxv, mxm, and eWise*` all exploit the mask to prune work, but select does not.

For our service, the tradeoff is thus this:

1. GrB_assign + GrB_select to achieve O(M) runtime via using O(M) memory, or
2. prevent memory spikes but accept O(A) runtime via GrB_select with a mask M

Compare with GrB_assign, which applies an operation over A restricted by mask M via iterating over mask entries and binary-searches into A. Fundamentally, I think select can do the same, something along the lines of:

1. pass M into GB_selector
2. iterate over entries of M
3. probe A for each masked index
4. apply predicate to matched entries
5. skip GB_accum_mask since the mask is already applied during selection

[DrTimothyAldenDavis]

Yes, it's definitely possible, and it's on my TODO list. I've added it as a reminder to myself here:
f1d9b40

[DrTimothyAldenDavis]

The algorithm would be different than that however, if M and A have many entries. For that case, a method like emult would be more appropriate, where I would traverse the intersection of M and A more efficiently. Scanning M and then looking up A would take an additional log-time factor, like O(M log n) in the worst case (but the n would be lower). That method would be suitable if M is very sparse and A is not. These strategies would work when M is not complemented.

It's not trivial to get it right; the emult method has about 17 different methods that handle these cases, only one of which is when M is complemented.

A complete suite of algorithms for select, which exploit the mask, would not require as many as 16 methods, I think, since emult has 3 matrices (M, A, B) while select has just 2. But it would still take quite a bit to flesh out a complete suite for select.

It's been lower on my list because very few algorithms require a masked select.

For your case, what is M and A? Are they both sparse/hypersparse? How does nnz(M) and nnz(A) compare?