From: Tom Lane <tgl@sss.pgh.pa.us>
To: Joel Jacobson <joel@compiler.org>
cc: Chapman Flack <chap@anastigmatix.net>, pgsql-hackers@lists.postgresql.org
Subject: Re: Some regular-expression performance hacking
In-reply-to: <4019408.1614133970@sss.pgh.pa.us>
References: <1340281.1613018383@sss.pgh.pa.us>
 <85140bfb-516c-449b-8a03-7930abb42b88@www.fastmail.com>
 <1813969.1613250697@sss.pgh.pa.us>
 <913516b8-c3d7-4dea-bf60-d735cf4673f1@www.fastmail.com>
 <2155152.1613358697@sss.pgh.pa.us>
 <99f6cbe0-6e58-4e41-add0-977271a5cf84@www.fastmail.com>
 <2752386.1613595636@sss.pgh.pa.us>
 <5deabab3-a335-4b57-a046-8a9ad8f2f142@www.fastmail.com>
 <12e6381c-adc1-4711-a619-864fb8df969c@www.fastmail.com>
 <2840118.1613671847@sss.pgh.pa.us> <2845172.1613674385@sss.pgh.pa.us>
 <b16bccc0-3f98-47ad-81aa-699a3e00630d@www.fastmail.com>
 <3028106.1613748380@sss.pgh.pa.us> <60319BDB.2040302@anastigmatix.net>
 <3374539.1613870009@sss.pgh.pa.us> <4019408.1614133970@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Tue, 23 Feb 2021 21:32:50 -0500"
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <4185655.1614208762.0@sss.pgh.pa.us>
Date: Wed, 24 Feb 2021 18:19:52 -0500
Message-ID: <4185677.1614208792@sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <4185655.1614208762.1@sss.pgh.pa.us>

I wrote:
> On my machine, the combination of these two ideas reduces the
> runtime of the example above from ~150 seconds to ~53 seconds,
> or nearly 3x better.  I see something like a 2% improvement on
> Joel's test corpus, which might just be noise.  So this isn't
> any sort of universal panacea, but it sure helps when LACON
> evaluation is the bottleneck.

After another round of testing, I really can't see any improvement
at all from that patch on anything except the original Tcl test
case.  Indeed, a lot of cases seem very slightly worse, perhaps
because compact() now has to make two passes over all the arcs.
So that's leaving me a bit dissatisfied with it; I'm going to
stick it on the back burner for now, in hopes of a better idea.

However, in a different line of thought, I realized that the
memory allocation logic could use some polishing.  It gives out
ten arcs per NFA state initially, and then adds ten more at a time.
However, that's not very bright when you look at the actual usage
patterns, because most states have only one or two out-arcs,
but some have lots and lots.  I instrumented things to gather
stats about arcs-per-state on your larger corpus, and I got this,
where the seond column is the total fraction of states having
the given number of arcs or fewer:

 arcs |      cum_fraction      
------+------------------------
    0 | 0.03152871318455725868
    1 | 0.55852399556959499493
    2 | 0.79408539124378449284
    3 | 0.86926656199366447221
    4 | 0.91726891675794579062
    5 | 0.92596934405572457792
    6 | 0.93491612836055807037
    7 | 0.94075102352639209644
    8 | 0.94486598829672779379
    9 | 0.94882085883928361399
   10 | 0.95137992908336444821
   11 | 0.95241399914559696173
   12 | 0.95436547669138874594
   13 | 0.95534682472329051385
   14 | 0.95653340893356523452
   15 | 0.95780804864876924571
   16 | 0.95902387577636979702
   17 | 0.95981494467267418552
   18 | 0.96048662216159976997
   19 | 0.96130294229052153065
   20 | 0.96196856160309755204
...
 3238 | 0.99999985870142624926
 3242 | 0.99999987047630739515
 4095 | 0.99999987342002768163
 4535 | 0.99999987930746825457
 4642 | 0.99999988225118854105
 4706 | 0.99999989402606968694
 5890 | 0.99999989696978997342
 6386 | 0.99999990874467111931
 7098 | 0.99999991168839140579
 7751 | 0.99999994701303484347
 7755 | 0.99999998233767828116
 7875 | 0.99999998822511885410
 8049 | 1.00000000000000000000

So it seemed clear to me that we should only give out a couple of arcs
per state initially, but then let it ramp up faster than 10 arcs per
additional malloc.  After a bit of fooling I have the attached.
This does nothing for the very largest examples in the corpus (the
ones that cause "regex too complex") --- those were well over the
REG_MAX_COMPILE_SPACE limit before and they still are.  But all the
rest get nicely smaller.  The average pg_regcomp memory consumption
drops from ~89K to ~48K.

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff; name="0007-smarter-arc-allocation.patch";
	charset="us-ascii"
Content-ID: <4185655.1614208762.2@sss.pgh.pa.us>
Content-Description: 0007-smarter-arc-allocation.patch
Content-Transfer-Encoding: quoted-printable

diff --git a/src/backend/regex/regc_nfa.c b/src/backend/regex/regc_nfa.c
index 69929eddfc..411c86f4ff 100644
--- a/src/backend/regex/regc_nfa.c
+++ b/src/backend/regex/regc_nfa.c
@@ -142,9 +142,12 @@ newstate(struct nfa *nfa)
 	{
 		s =3D nfa->free;
 		nfa->free =3D s->next;
+		/* the state's free arcs stay as they are */
 	}
 	else
 	{
+		int			i;
+
 		if (nfa->v->spaceused >=3D REG_MAX_COMPILE_SPACE)
 		{
 			NERR(REG_ETOOBIG);
@@ -157,9 +160,16 @@ newstate(struct nfa *nfa)
 			return NULL;
 		}
 		nfa->v->spaceused +=3D sizeof(struct state);
-		s->oas.next =3D NULL;
-		s->free =3D NULL;
-		s->noas =3D 0;
+		s->lastab =3D NULL;
+		/* initialize free arcs; this should match allocarc() */
+		for (i =3D 0; i < NINITARCS - 1; i++)
+		{
+			s->inita[i].type =3D 0;
+			s->inita[i].freechain =3D &s->inita[i + 1];
+		}
+		s->inita[i].type =3D 0;
+		s->inita[i].freechain =3D NULL;
+		s->free =3D &s->inita[0];
 	}
 =

 	assert(nfa->nstates >=3D 0);
@@ -255,11 +265,11 @@ destroystate(struct nfa *nfa,
 	struct arcbatch *abnext;
 =

 	assert(s->no =3D=3D FREESTATE);
-	for (ab =3D s->oas.next; ab !=3D NULL; ab =3D abnext)
+	for (ab =3D s->lastab; ab !=3D NULL; ab =3D abnext)
 	{
 		abnext =3D ab->next;
+		nfa->v->spaceused -=3D ARCBATCHSIZE(ab->narcs);
 		FREE(ab);
-		nfa->v->spaceused -=3D sizeof(struct arcbatch);
 	}
 	s->ins =3D NULL;
 	s->outs =3D NULL;
@@ -377,41 +387,39 @@ allocarc(struct nfa *nfa,
 {
 	struct arc *a;
 =

-	/* shortcut */
-	if (s->free =3D=3D NULL && s->noas < ABSIZE)
-	{
-		a =3D &s->oas.a[s->noas];
-		s->noas++;
-		return a;
-	}
-
 	/* if none at hand, get more */
 	if (s->free =3D=3D NULL)
 	{
 		struct arcbatch *newAb;
-		int			i;
+		size_t		narcs;
+		size_t		i;
 =

 		if (nfa->v->spaceused >=3D REG_MAX_COMPILE_SPACE)
 		{
 			NERR(REG_ETOOBIG);
 			return NULL;
 		}
-		newAb =3D (struct arcbatch *) MALLOC(sizeof(struct arcbatch));
+		narcs =3D (s->lastab !=3D NULL) ? s->lastab->narcs * 2 : FIRSTABSIZE;
+		if (narcs > MAXABSIZE)
+			narcs =3D MAXABSIZE;
+		newAb =3D (struct arcbatch *) MALLOC(ARCBATCHSIZE(narcs));
 		if (newAb =3D=3D NULL)
 		{
 			NERR(REG_ESPACE);
 			return NULL;
 		}
-		nfa->v->spaceused +=3D sizeof(struct arcbatch);
-		newAb->next =3D s->oas.next;
-		s->oas.next =3D newAb;
+		nfa->v->spaceused +=3D ARCBATCHSIZE(narcs);
+		newAb->narcs =3D narcs;
+		newAb->next =3D s->lastab;
+		s->lastab =3D newAb;
 =

-		for (i =3D 0; i < ABSIZE; i++)
+		for (i =3D 0; i < narcs - 1; i++)
 		{
 			newAb->a[i].type =3D 0;
 			newAb->a[i].freechain =3D &newAb->a[i + 1];
 		}
-		newAb->a[ABSIZE - 1].freechain =3D NULL;
+		newAb->a[i].type =3D 0;
+		newAb->a[i].freechain =3D NULL;
 		s->free =3D &newAb->a[0];
 	}
 	assert(s->free !=3D NULL);
@@ -3413,7 +3421,7 @@ dumparc(struct arc *a,
 		FILE *f)
 {
 	struct arc *aa;
-	struct arcbatch *ab;
+	bool		found =3D false;
 =

 	fprintf(f, "\t");
 	switch (a->type)
@@ -3451,15 +3459,29 @@ dumparc(struct arc *a,
 	}
 	if (a->from !=3D s)
 		fprintf(f, "?%d?", a->from->no);
-	for (ab =3D &a->from->oas; ab !=3D NULL; ab =3D ab->next)
+
+	/*
+	 * Check that arc belongs to its from-state's arc space.  This is
+	 * approximate, since we don't verify the arc isn't misaligned within th=
e
+	 * space; but it's enough to catch the likely problem of an arc being
+	 * misassigned to a different parent state.
+	 */
+	if (a >=3D a->from->inita && a < a->from->inita + NINITARCS)
+		found =3D true;			/* member of initial arcset */
+	else
 	{
-		for (aa =3D &ab->a[0]; aa < &ab->a[ABSIZE]; aa++)
-			if (aa =3D=3D a)
+		struct arcbatch *ab;
+
+		for (ab =3D a->from->lastab; ab !=3D NULL; ab =3D ab->next)
+		{
+			if (a >=3D ab->a && a < ab->a + ab->narcs)
+			{
+				found =3D true;
 				break;			/* NOTE BREAK OUT */
-		if (aa < &ab->a[ABSIZE])	/* propagate break */
-			break;				/* NOTE BREAK OUT */
+			}
+		}
 	}
-	if (ab =3D=3D NULL)
+	if (!found)
 		fprintf(f, "?!?");		/* not in allocated space */
 	fprintf(f, "->");
 	if (a->to =3D=3D NULL)
diff --git a/src/include/regex/regguts.h b/src/include/regex/regguts.h
index 306525eb5f..65e6ace9d1 100644
--- a/src/include/regex/regguts.h
+++ b/src/include/regex/regguts.h
@@ -294,12 +294,23 @@ struct arc
 	struct arc *colorchainRev;	/* back-link in color's arc chain */
 };
 =

+/*
+ * We include NINITARCS arcs directly in the parent state, to save a sepa=
rate
+ * malloc for states with few out-arcs.  If more arcs are needed, the fir=
st
+ * arcbatch has size FIRSTABSIZE; each succeeding batch doubles in size,
+ * up to MAXABSIZE.
+ */
+#define  NINITARCS		2		/* 2 is enough for about 80% of states */
+#define  FIRSTABSIZE	8		/* 2+8 is enough for 95% of states */
+#define  MAXABSIZE		64		/* don't waste too much space per arcbatch */
+
 struct arcbatch
 {								/* for bulk allocation of arcs */
-	struct arcbatch *next;
-#define  ABSIZE  10
-	struct arc	a[ABSIZE];
+	struct arcbatch *next;		/* chain link */
+	size_t		narcs;			/* number of arcs allocated in this arcbatch */
+	struct arc	a[FLEXIBLE_ARRAY_MEMBER];
 };
+#define  ARCBATCHSIZE(n)  ((n) * sizeof(struct arc) + offsetof(struct arc=
batch, a))
 =

 struct state
 {
@@ -312,10 +323,10 @@ struct state
 	struct arc *outs;			/* chain of outarcs */
 	struct arc *free;			/* chain of free arcs */
 	struct state *tmp;			/* temporary for traversal algorithms */
-	struct state *next;			/* chain for traversing all */
-	struct state *prev;			/* back chain */
-	struct arcbatch oas;		/* first arcbatch, avoid malloc in easy case */
-	int			noas;			/* number of arcs used in first arcbatch */
+	struct state *next;			/* chain for traversing all live states */
+	struct state *prev;			/* back-link in chain of all live states */
+	struct arcbatch *lastab;	/* chain of associated arcbatches */
+	struct arc	inita[NINITARCS];	/* a few arcs to avoid extra malloc */
 };
 =

 struct nfa
@@ -413,7 +424,7 @@ struct cnfa
  */
 #ifndef REG_MAX_COMPILE_SPACE
 #define REG_MAX_COMPILE_SPACE  \
-	(100000 * sizeof(struct state) + 100000 * sizeof(struct arcbatch))
+	(100000 * sizeof(struct state) + 2000000 * sizeof(struct arc))
 #endif
 =

 /*

------- =_aaaaaaaaaa0--