On Wed, Apr 10, 2024 at 02:05:05PM -0400, Jeff King wrote: > > This function makes use of the EWAH iterator to avoid inflating any part > > of the EWAH bitmap after we determine it is not a subset of the non-EWAH > > bitmap. This "fail-fast" allows us to avoid a potentially large amount > > of wasted effort. > > Makes sense, as we have an expanded bitmap_is_subset() already, and this > should be more efficient. Yep, the idea is that we already have a deflated non-EWAH bitmap in memory, but we're comparing it against a potentially large EWAH compressed bitmap. If we can determine early that the EWAH bitmap has bits that are *not* in the non-EWAH bitmap, then we can avoid inflating a large part of the EWAH bitmap. > > diff --git a/ewah/bitmap.c b/ewah/bitmap.c > > index ac7e0af622a..5bdae3fb07b 100644 > > --- a/ewah/bitmap.c > > +++ b/ewah/bitmap.c > > @@ -138,6 +138,49 @@ void bitmap_or(struct bitmap *self, const struct bitmap *other) > > self->words[i] |= other->words[i]; > > } > > > > +int ewah_bitmap_is_subset(struct ewah_bitmap *self, struct bitmap *other) > > It wasn't immediately obvious to me if we were checking that "other" is > a subset of "self" or vice versa. I wonder if we could use different > names here to make it more clear (though really it matters more in the > declaration, not the implementation). We check whether 'self' is a subset of 'other', but I'll document it here for both functions. > I think bitmap_is_subset() suffers from the same issue (and is even more > confusing because the two have the same type!). Maybe just a header file > comment would help? Yeah, agreed. > I think your use of the phrase "proper subset" is a little confusing > here, as it is not a subset at all, let alone the distinction between a > regular and proper one (in the mathematical definitions). Thanks for catching, this should definitely say just "subset" (indicating that 'self' and 'other' can have an identical set of bits in each and self is still considered a subset of other). > > + /* > > + * If we got to this point, there may be zero or more words > > + * remaining in `self`, with no remaining words left in `other`. > > + * If there are any bits set in the remaining word(s) in `self`, > > + * then `self` is not a proper subset of `other`. > > + */ > > + while (ewah_iterator_next(&word, &it)) > > + if (word) > > + return 0; > > OK, so here we keep expanding to see if there are any bits set, meaning > we may read past a bunch of 0-words that we don't care about. I suspect > this could be optimized to just ask the ewah "are there any bits left?" > but I don't think we have an easy function for that. And it's not clear > to me that it would produce measurable speedups anyway, so probably not > worth worrying about. Yep. > As above, ditto on the use of "proper subset" here. Thanks, fixed. Thanks, Taylor
