Thank you for running the profiles.
On Tue, 27 Jun 2023 at 21:11, Yuya Watari <[email protected]> wrote:
> On Sat, Jun 24, 2023 at 1:15 PM David Rowley <[email protected]> wrote:
> > I think it's also important to check we don't slow anything down for
> > more normal-sized sets. The vast majority of sets will contain just a
> > single word, so we should probably focus on making sure we're not
> > slowing anything down for those.
>
> I agree with you and thank you for sharing the results. I ran
> installcheck with your patch. The result is as follows. The speedup
> was 0.33%. At least in my environment, I did not observe any
> regression with this test. So, the patch looks very good.
>
> Master: 2.559648 seconds
> Patched: 2.551116 seconds (0.33% faster)
I wondered if the common case could be made slightly faster by
checking the 0th word before checking the word count before going onto
check the remaining words. For bms_equal(), that's something like:
if (a->words[0] != b->words[0] || a->nwords != b->nwords)
return false;
/* check all the remaining words match */
for (int i = 1; i < a->nwords; i++) ...
I wrote the patch and tried it out, but it seems slightly slower than
the v4 patch.
Linux with AMD 3990x, again using the patch from [1] with make installcheck
master: 1.41720145 seconds
v4: 1.392969606 seconds (1.74% faster than master)
v4 with 0th word check: 1.404199748 seconds (0.93% faster than master)
I've attached a delta patch of what I used to test. Since it's not
any faster, I don't think it's worth doing. It'll also produce
slightly more compiled code.
David
[1]
https://postgr.es/m/caaphdvo68m_0juthnehfnsdsjeb2upphk6bwxstj93u_qei...@mail.gmail.com
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 9cda3b1cc1..2ee7385f02 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -9,12 +9,7 @@
* the minimum possible number of words, i.e, there are never any trailing
* zero words. Enforcing this requires that an empty set is represented as
* NULL. Because an empty Bitmapset is represented as NULL, a non-NULL
- * Bitmapset always has at least 1 Bitmapword. We can exploit this fact to
- * speedup various loops over the Bitmapset's words array by using "do while"
- * loops instead of "for" loops. This means the code does not waste time
- * checking the loop condition before the first iteration. For Bitmapsets
- * containing only a single word (likely the majority of them) this reduces
- * the loop condition tests by half.
+ * Bitmapset always has at least 1 Bitmapword.
*
*
* Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -96,8 +91,6 @@ bms_copy(const Bitmapset *a)
bool
bms_equal(const Bitmapset *a, const Bitmapset *b)
{
- int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
{
@@ -108,17 +101,20 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
else if (b == NULL)
return false;
- /* can't be equal if the word counts don't match */
- if (a->nwords != b->nwords)
+ /*
+ * Most Bitmapsets will likely just have 1 word, so check for equality
+ * there before checking the number of words match. The sets cannot be
+ * equal when they don't have the same number of words.
+ */
+ if (a->words[0] != b->words[0] || a->nwords != b->nwords)
return false;
- /* check each word matches */
- i = 0;
- do
+ /* check all the remaining words match */
+ for (int i = 1; i < a->nwords; i++)
{
if (a->words[i] != b->words[i])
return false;
- } while (++i < a->nwords);
+ }
return true;
}
@@ -353,25 +349,27 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
bool
bms_is_subset(const Bitmapset *a, const Bitmapset *b)
{
- int i;
-
/* Handle cases where either input is NULL */
if (a == NULL)
return true; /* empty set is a subset of
anything */
if (b == NULL)
return false;
- /* 'a' can't be a subset of 'b' if it contains more words */
- if (a->nwords > b->nwords)
+ /*
+ * Check the 0th word first as many sets will only have 1 word.
+ * Otherwise, 'a' can't be a subset of 'b' if it contains more words, so
+ * there's no need to check remaining words if 'a' contains more words
+ * than 'b'.
+ */
+ if ((a->words[0] & ~b->words[0]) != 0 || a->nwords > b->nwords)
return false;
- /* Check all 'a' members are set in 'b' */
- i = 0;
- do
+ /* Check all remaining words to see 'b' has members not set in 'a'. */
+ for (int i = 1; i < a->nwords; i++)
{
if ((a->words[i] & ~b->words[i]) != 0)
return false;
- } while (++i < a->nwords);
+ }
return true;
}
