From: Taylor Blau <me@ttaylorr.com>
To: git@vger.kernel.org
Cc: Jeff King <peff@peff.net>, Elijah Newren <newren@gmail.com>,
Patrick Steinhardt <ps@pks.im>,
Junio C Hamano <gitster@pobox.com>
Subject: [PATCH v3 10/30] ewah: implement `ewah_bitmap_is_subset()`
Date: Tue, 21 May 2024 15:02:09 -0400 [thread overview]
Message-ID: <40eb6137618ad4c648eaafd720a9678d8d84c96a.1716318089.git.me@ttaylorr.com> (raw)
In-Reply-To: <cover.1716318088.git.me@ttaylorr.com>
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 | 6 ++++++
2 files changed, 49 insertions(+)
diff --git a/ewah/bitmap.c b/ewah/bitmap.c
index ac7e0af622a..d352fec54ce 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
+ * 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 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..2b6c4ac499c 100644
--- a/ewah/ewok.h
+++ b/ewah/ewok.h
@@ -179,7 +179,13 @@ void bitmap_unset(struct bitmap *self, size_t pos);
int bitmap_get(struct bitmap *self, size_t pos);
void bitmap_free(struct bitmap *self);
int bitmap_equals(struct bitmap *self, struct bitmap *other);
+
+/*
+ * Both `bitmap_is_subset()` and `ewah_bitmap_is_subset()` return 1 if the set
+ * of bits in 'self' are a subset of the bits in 'other'. Returns 0 otherwise.
+ */
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);
--
2.45.1.175.gbea44add9db
next prev parent reply other threads:[~2024-05-21 19:02 UTC|newest]
Thread overview: 157+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-20 22:04 [PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps Taylor Blau
2024-03-20 22:05 ` [PATCH 01/24] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-03-21 21:24 ` Junio C Hamano
2024-03-21 22:13 ` Taylor Blau
2024-03-21 22:22 ` Junio C Hamano
2024-03-20 22:05 ` [PATCH 02/24] config: repo_config_get_expiry() Taylor Blau
2024-04-10 17:54 ` Jeff King
2024-04-29 19:39 ` Taylor Blau
2024-03-20 22:05 ` [PATCH 03/24] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-04-10 18:05 ` Jeff King
2024-04-29 19:47 ` Taylor Blau
2024-03-20 22:05 ` [PATCH 04/24] pack-bitmap: drop unused `max_bitmaps` parameter Taylor Blau
2024-04-10 18:06 ` Jeff King
2024-03-20 22:05 ` [PATCH 05/24] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-04-10 18:10 ` Jeff King
2024-03-20 22:05 ` [PATCH 06/24] pseudo-merge.ch: initial commit Taylor Blau
2024-03-20 22:05 ` [PATCH 07/24] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 08/24] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-03-20 22:05 ` [PATCH 09/24] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-03-20 22:05 ` [PATCH 10/24] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 11/24] pack-bitmap-write.c: select " Taylor Blau
2024-03-20 22:05 ` [PATCH 12/24] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-03-20 22:05 ` [PATCH 13/24] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-03-20 22:05 ` [PATCH 14/24] pseudo-merge: scaffolding for reads Taylor Blau
2024-03-20 22:05 ` [PATCH 15/24] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-03-20 22:05 ` [PATCH 16/24] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 17/24] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-03-20 22:05 ` [PATCH 18/24] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-03-20 22:05 ` [PATCH 19/24] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-03-20 22:05 ` [PATCH 20/24] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-03-20 22:06 ` [PATCH 21/24] pack-bitmap: extra trace2 information Taylor Blau
2024-03-20 22:06 ` [PATCH 22/24] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-03-20 22:06 ` [PATCH 23/24] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-03-20 22:06 ` [PATCH 24/24] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-03-21 19:50 ` [PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps Junio C Hamano
2024-04-29 20:42 ` [PATCH v2 00/23] " Taylor Blau
2024-04-29 20:42 ` [PATCH v2 01/23] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 16:37 ` Taylor Blau
2024-05-10 11:46 ` Patrick Steinhardt
2024-05-13 19:47 ` Taylor Blau
2024-05-14 6:33 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 02/23] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 03/23] pack-bitmap: drop unused `max_bitmaps` parameter Taylor Blau
2024-04-29 20:43 ` [PATCH v2 04/23] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 18:24 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 05/23] pseudo-merge.ch: initial commit Taylor Blau
2024-04-29 20:43 ` [PATCH v2 06/23] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 18:48 ` Taylor Blau
2024-05-10 11:47 ` Patrick Steinhardt
2024-05-13 18:42 ` Jeff King
2024-05-13 20:19 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 07/23] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 08/23] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-05-13 18:50 ` Jeff King
2024-05-14 0:54 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 09/23] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-05-06 11:53 ` Patrick Steinhardt
2024-05-06 19:58 ` Taylor Blau
2024-05-13 19:03 ` Jeff King
2024-05-14 0:58 ` Taylor Blau
2024-05-16 8:07 ` Jeff King
2024-05-16 22:43 ` Junio C Hamano
2024-04-29 20:43 ` [PATCH v2 10/23] pack-bitmap-write.c: select " Taylor Blau
2024-05-06 11:53 ` Patrick Steinhardt
2024-05-06 20:05 ` Taylor Blau
2024-05-10 11:47 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 11/23] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-04-29 20:43 ` [PATCH v2 12/23] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-04-29 20:43 ` [PATCH v2 13/23] pseudo-merge: scaffolding for reads Taylor Blau
2024-04-29 20:43 ` [PATCH v2 14/23] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-04-29 20:44 ` [PATCH v2 15/23] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-04-29 20:44 ` [PATCH v2 16/23] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 17/23] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-04-29 20:44 ` [PATCH v2 18/23] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 19/23] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-04-29 20:44 ` [PATCH v2 20/23] pack-bitmap: extra trace2 information Taylor Blau
2024-04-29 20:44 ` [PATCH v2 21/23] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 22/23] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-04-29 20:44 ` [PATCH v2 23/23] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-04-30 20:03 ` [PATCH v2 00/23] pack-bitmap: pseudo-merge reachability bitmaps Junio C Hamano
2024-05-01 14:40 ` Taylor Blau
2024-05-21 19:01 ` [PATCH v3 00/30] " Taylor Blau
2024-05-21 19:01 ` [PATCH v3 01/30] object.h: add flags allocated by pack-bitmap.h Taylor Blau
2024-05-21 19:06 ` Taylor Blau
2024-05-21 19:01 ` [PATCH v3 07/30] Documentation/gitpacking.txt: initial commit Taylor Blau
2024-05-21 19:02 ` [PATCH v3 08/30] Documentation/gitpacking.txt: describe pseudo-merge bitmaps Taylor Blau
2024-05-21 19:02 ` [PATCH v3 09/30] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-05-21 19:02 ` Taylor Blau [this message]
2024-05-21 19:02 ` [PATCH v3 11/30] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-05-21 19:02 ` [PATCH v3 12/30] pseudo-merge.ch: initial commit Taylor Blau
2024-05-21 19:02 ` [PATCH v3 13/30] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-05-21 19:02 ` [PATCH v3 14/30] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-05-21 19:02 ` [PATCH v3 15/30] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-05-21 19:02 ` [PATCH v3 16/30] config: introduce git_config_float() Taylor Blau
2024-05-23 10:02 ` Jeff King
2024-05-23 17:51 ` Taylor Blau
2024-05-21 19:02 ` [PATCH v3 17/30] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-05-23 10:12 ` Jeff King
2024-05-23 17:56 ` Taylor Blau
2024-05-21 19:02 ` [PATCH v3 18/30] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-05-21 19:02 ` [PATCH v3 19/30] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-05-21 19:02 ` [PATCH v3 20/30] pseudo-merge: scaffolding for reads Taylor Blau
2024-05-21 19:02 ` [PATCH v3 21/30] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-05-21 19:02 ` [PATCH v3 22/30] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-05-23 10:40 ` Jeff King
2024-05-23 18:09 ` Taylor Blau
2024-05-21 19:02 ` [PATCH v3 23/30] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-05-21 19:02 ` [PATCH v3 24/30] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-05-21 19:02 ` [PATCH v3 25/30] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-05-23 10:42 ` Jeff King
2024-05-23 15:45 ` Junio C Hamano
2024-05-23 18:23 ` Taylor Blau
2024-05-21 19:03 ` [PATCH v3 26/30] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-05-23 10:48 ` Jeff King
2024-05-23 18:23 ` Taylor Blau
2024-05-21 19:03 ` [PATCH v3 27/30] pack-bitmap: extra trace2 information Taylor Blau
2024-05-21 19:03 ` [PATCH v3 28/30] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-05-21 19:03 ` [PATCH v3 29/30] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-05-21 19:03 ` [PATCH v3 30/30] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-05-23 10:54 ` Jeff King
2024-05-23 19:53 ` Taylor Blau
2024-05-25 3:13 ` Jeff King
2024-05-23 11:05 ` [PATCH v3 00/30] pack-bitmap: pseudo-merge reachability bitmaps Jeff King
2024-05-23 20:04 ` Taylor Blau
2024-05-25 3:15 ` Jeff King
2024-05-23 20:42 ` Taylor Blau
2024-05-23 21:26 ` [PATCH v4 00/24] " Taylor Blau
2024-05-23 21:26 ` [PATCH v4 01/24] Documentation/gitpacking.txt: initial commit Taylor Blau
2024-05-23 21:26 ` [PATCH v4 02/24] Documentation/gitpacking.txt: describe pseudo-merge bitmaps Taylor Blau
2024-05-23 21:26 ` [PATCH v4 03/24] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-05-23 21:26 ` [PATCH v4 04/24] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-05-23 21:26 ` [PATCH v4 05/24] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-05-23 21:26 ` [PATCH v4 06/24] pseudo-merge.ch: initial commit Taylor Blau
2024-05-23 21:26 ` [PATCH v4 07/24] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-05-23 21:26 ` [PATCH v4 08/24] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-05-23 21:26 ` [PATCH v4 09/24] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-05-23 21:26 ` [PATCH v4 10/24] config: introduce `git_config_double()` Taylor Blau
2024-05-23 21:26 ` [PATCH v4 11/24] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-05-25 3:22 ` Jeff King
2024-05-23 21:26 ` [PATCH v4 12/24] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-05-23 21:26 ` [PATCH v4 13/24] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-05-23 21:26 ` [PATCH v4 14/24] pseudo-merge: scaffolding for reads Taylor Blau
2024-05-23 21:26 ` [PATCH v4 15/24] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-05-23 21:26 ` [PATCH v4 16/24] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-05-23 21:27 ` [PATCH v4 17/24] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-05-23 21:27 ` [PATCH v4 18/24] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-05-23 21:27 ` [PATCH v4 19/24] t/test-lib-functions.sh: support `--notick` in `test_commit_bulk()` Taylor Blau
2024-05-25 3:25 ` Jeff King
2024-05-23 21:27 ` [PATCH v4 20/24] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-05-23 21:27 ` [PATCH v4 21/24] pack-bitmap: extra trace2 information Taylor Blau
2024-05-23 21:27 ` [PATCH v4 22/24] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-05-23 21:27 ` [PATCH v4 23/24] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-05-23 21:27 ` [PATCH v4 24/24] t/perf: implement performance tests for pseudo-merge bitmaps Taylor Blau
2024-05-25 3:26 ` [PATCH v4 00/24] pack-bitmap: pseudo-merge reachability bitmaps Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=40eb6137618ad4c648eaafd720a9678d8d84c96a.1716318089.git.me@ttaylorr.com \
--to=me@ttaylorr.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=newren@gmail.com \
--cc=peff@peff.net \
--cc=ps@pks.im \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).