| Message ID | 1347571ef4ca6329de58394bfea71927c8e08151.1710972293.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | pack-bitmap: pseudo-merge reachability bitmaps | expand |
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
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
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) +{ + 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; + } + } + + /* + * 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; + + /* `self` is definitely a subset of `other` */ + return 1; +} + void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other) { size_t original_size = self->word_alloc; diff --git a/ewah/ewok.h b/ewah/ewok.h index c11d76c6f33..c334833b201 100644 --- a/ewah/ewok.h +++ b/ewah/ewok.h @@ -180,6 +180,7 @@ int bitmap_get(struct bitmap *self, size_t pos); void bitmap_free(struct bitmap *self); int bitmap_equals(struct bitmap *self, struct bitmap *other); int bitmap_is_subset(struct bitmap *self, struct bitmap *other); +int ewah_bitmap_is_subset(struct ewah_bitmap *self, struct bitmap *other); struct ewah_bitmap * bitmap_to_ewah(struct bitmap *bitmap); struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah);
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. Signed-off-by: Taylor Blau <me@ttaylorr.com> --- ewah/bitmap.c | 43 +++++++++++++++++++++++++++++++++++++++++++ ewah/ewok.h | 1 + 2 files changed, 44 insertions(+)