GraphBLAS icon indicating copy to clipboard operation
GraphBLAS copied to clipboard

Structural Select isn't very memory efficient on full, iso-valued objects

Open eriknw opened this issue 3 years ago • 1 comments

I would expect some select operations to be more memory efficient then they currently are.

Here are a couple examples where I get OutOfMemory error:

  • Large, full iso-valued Matrix as input and using a mask with few elements (i.e., whose indices comfortably fit in memory); for example, when selecting with TRIL.
  • Large, full iso-valued Vector as input with select operator "ROWLE" with small thunk value (i.e., final indices comfortably fit in memory).

I stumbled upon the first one when writing an algorithm. The second one was simply exploration and not important to me.

eriknw avatar Apr 24 '22 18:04 eriknw

My GrB_select method currently does the select as T = select(A,...), which does not exploit the mask, followed by C<M>=T. That's why you're seeing the out-of-memory error. T is very large and is explicitly constructed. I realize that's not optimal. I have this marked as a "TODO": https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/4bb44bb93a30b54c7039d1c6f5d87e3c85ec45a5/Source/GB_selector.c#L14

It's on my radar to speed up GrB_select when a sparse mask is present.

DrTimothyAldenDavis avatar Apr 25 '22 13:04 DrTimothyAldenDavis