Re: [PATCH 03/24] ewah: implement `ewah_bitmap_is_subset()`

[Jeff King <peff@peff.net>]

On Wed, Mar 20, 2024 at 06:05:08PM -0400, Taylor Blau wrote:

> In order to know whether a given pseudo-merge (comprised of a "parents"
> and "objects" bitmaps) is "satisfied" and can be OR'd into the bitmap
> result, we need to be able to quickly determine whether the "parents"
> bitmap is a subset of the current set of objects reachable on either
> side of a traversal.
> 
> Implement a helper function to prepare for that, which determines
> whether an EWAH bitmap (the parents bitmap from the pseudo-merge) is a
> subset of a non-EWAH bitmap (in this case, the results bitmap from
> either side of the traversal).
> 
> 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.

> 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).

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?

> +{
> +	struct ewah_iterator it;
> +	eword_t word;
> +	size_t i;
> +
> +	ewah_iterator_init(&it, self);
> +
> +	for (i = 0; i < other->word_alloc; i++) {
> +		if (!ewah_iterator_next(&word, &it)) {
> +			/*
> +			 * If we reached the end of `self`, and haven't
> +			 * rejected `self` as a possible subset of
> +			 * `other` yet, then we are done and `self` is
> +			 * indeed a subset of `other`.
> +			 */
> +			return 1;
> +		}
> +		if (word & ~other->words[i]) {
> +			/*
> +			 * Otherwise, compare the next two pairs of
> +			 * words. If the word from `self` has bit(s) not
> +			 * in the word from `other`, `self` is not a
> +			 * proper subset of `other`.
> +			 */
> +			return 0;
> +		}
> +	}

OK, so we expand the ewah as we go, comparing words, and then quit early
if we can. That's the best we can do when comparing to a regular bitmap.
I suspect we could do more clever things for ewah-to-ewah (like saying
"oh, they both have a run of 10,000 zeroes" without expanding), but
that wouldn't be helpful here, as your use case will be comparing
against a bitmap we're building in memory.

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).

> +	/*
> +	 * 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.

As above, ditto on the use of "proper subset" here.

-Peff