Advanced Notation #234

Activity

1. eriknw

   added

   enhancementImprove existing functionality or make things work betterImprove existing functionality or make things work better

   discussionDiscussing a topic with no specific actions yetDiscussing a topic with no specific actions yet

   on May 19, 2022
2. eriknw commented on May 19, 2022

   

   eriknw

   on May 19, 2022

   Last edited by eriknw

   Member

   More actions

   I think number (1) (using boolean objects as value masks) will give us the biggest bang for the buck. It should be easy to implement and handy to use. It also unlocks some of the other notation.

   Regarding (4), would the recipe for updater << A.select(B.S) be:

   • updater(mask=B.S) << A if updater doesn't have a mask
   • updater << A.dup(mask=B.S) if updater does have a mask

   I guess (1) and (4) combined would allow e.g. A.select(B < 5). I don't hate this (it may actually be kinda nice), and it makes it easier to punt on A[A < 1] and A[B < 1] notation, which might be a can of worms.

   (3) already works with boolean objects, (A > 1) & (A < 7) etc. The thing that is missing is treating masks as value-y. The first step to do so is to give masks .new(dtype=None, *, mask=None, name=None). We can add .new to masks and still decide to not treat them as value-y. This exercise can help us figure out how to best combine masks. Possible recipes for M1.new(mask=M2) (whose values are always True or 1 depending on given dtype) are:

   • One structural mask S, any other mask A:
     • unary.one(S.parent).new(mask=A)
   • One value mask V, any other mask A:
     • select.nonzero(V.parent).new(bool, mask=A)
     • If the output dtype is not bool, then we have more work to make the output values 1.
   • Both complemented masks, bigger and smaller where bigger.nvals >= smaller.nvals:
     • result = Matrix(...)
     • result(bigger) << True
     • r(smaller, replace=True) << result
     • Realizing complemented masks can be very expensive; let's hope it's not done for hypersparse objects!
       • Heh, a crazy idea would be to combine multiple masks into a "lazy" mask.
       • A less crazy idea is to output a result that is intended to be used as a complemented (structural?) mask
         • Perhaps this could be enabled via a keyword (complement=True?)
         • Recipes could be similar to the alternative below:
           • S-S: result = binary.pair(S1 | S2).new() ; result(result.S) << True
           • V-V: result = binary.lor(V1 | v2).new() ; result(result.V, replace=True) << True
           • S-V: result = binary.pair(unary.one(S) | V).new() ; result(result.V, replace=True) << True
           • We should play around with other recipes for these
           • For V-V and S-V, do we need the step where we drop 0s? Probably, for consistency. We do this so it can be used as a structural mask. Without dropping 0s, it can be used as a value mask to get the same result.
     • Alternative to explore:
       • temp = binop(bigger.parent | smaller.parent).new()
       • result(~temp.X) << True
       • where binop and X are chosen as appropriate (such as pair-S for S-S, lor-V for V-V)
       • Still need to figure out when one mask is value and one is structural
         • In the cases where it works, perhaps we can decide whether this or the previous recipe will be better based on nvals.
       • Edit: okay, given one complemented value mask V and complemented structural mask S, I think the recipe can be:
         • result(~binop(V.parent | unary.one(S.parent)).V) << True
         • where binop can be second, lor, le, or pair. I think I like pair.

   Given how tricky it can be to combine two masks in general--and how intuitive combining two masks is--I'm +1 for adding .new to masks regardless of whether we decide to make them value-y.

   Also, @jim22k, where is select.nonzero? I think this would be nice to have.
3. jim22k commented on May 20, 2022

   

   jim22k

   on May 20, 2022

   MemberAuthor

   More actions

   Thanks for the detailed thoughts on this. I don't have the mental space to dig into this right now, but you bring up many edge cases that need to be handled when combining masks.

   As for the missing A.select.nonzero(), what is wrong with select.value(A != 0)? I'm not totally opposed to including .nonzero, but I feel like it's not needed as the more general pattern is both sort and readable.
4. eriknw commented on May 21, 2022

   

   eriknw

   on May 21, 2022

   Member

   More actions

   I wonder whether select.valuene is as fast as select.nonzero, b/c I suspect Tim added the operations that ignore the scalar values for performance reasons. I'm fine with select.value(A != 0), but if we can automatically make it faster if the scalar is 0, then I think we should. Counterpoint: people familiar with SuiteSparse:GraphBLAS (and I expect heavy users will read its userguide) may reach for nonzero and be surprised it's not there.

   Regarding mask1.new(mask=m2, complement=complement), it's worth pointing out that the semantics we want to match are:

   val = Vector(bool, size=size)
   val << True
   val = val.dup(mask=mask1).dup(mask=mask2)

   or

   val = Vector(bool, size=size)
   val(mask1) << True
   val(mask2, replace=True) << val

   and

   if complement:
       val(~val.S, replace=True) << True

   So, we could always start or fall back to these recipes, and add others when there is a need or once we get a chance to benchmark them. My priorities: (1) memory usage where hypersparse will blow up (and it won't always do so), (2) performance, (3) cleanliness of recipes. For example, in regards to (3), I'm happy to have a different recipe for each combination of masks if justified.
5. eriknw commented on May 25, 2022

   

   eriknw

   on May 25, 2022

   Member

   More actions

   @jim22k and I discussed this today, and I think we're both comfortable with adding (1), (3), and (4). When masks are treated value-y, they are equivalent to iso-valued (True) objects where the structure matches where the mask would be applied.

   (2) seems complicated and unnecessary.

   Also, these are nice-to-haves, not need-to-haves. There is no particular urgency to add them.
6. eriknw commented on Jun 17, 2022

   

   eriknw

   on Jun 17, 2022

   Member

   More actions

   @jim22k, for (3)--the last thing to do in this issue--how "value-y" do you think we should make masks?

   We now allow boolean objects to be used as masks, but I'm hesitant to do the converse.

   I think it would be sufficient to support e.g. A.S | B.S and (~A.S) & B.V. Moreover, I think these expressions should probably return mask objects, not expressions that will result in a vector or matrix. Perhaps it could return a MaskExpression or what-have-you (maybe just a different kind of Mask), which would give us the opportunity to rewrite the expression to something more efficient. As per normal rules, we should be able to combine a mask with a boolean object as a value mask: A.S | B.

   In other words, in order to close this issue, I think we just need to implement __or__ and __and__ on mask objects (and decide what they do). __xor__ is a stretch goal!
7. jim22k commented on Jun 17, 2022

   

   jim22k

   on Jun 17, 2022

   MemberAuthor

   More actions

   I agree this should be restricted to masks, hence only support A.S, A.V, and A (with dtype==bool).
   I don't have a strong opinion on MaskExpression. I would be okay restricting this to only returning masks until we see a strong need for more.
8. eriknw

   added a commit that references this issue on Jul 4, 2022

   Allow masks to be combined with `|` and`&`

   ...

   This issue will close once commit 995c022 is merged into the 'master' branch.

   995c022
9. jim22k

   closed this as completedin #267on Jul 7, 2022
10. jim22k

    added a commit that references this issue on Jul 7, 2022

    Allow masks to be combined with `|` and`&` (#267)

    ...

    This issue will close once commit ef4b1ca is merged into the 'main' branch.

    ef4b1ca