0007-smarter-arc-allocation.patch

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 = nfa->free;
 		nfa->free = s->next;
+		/* the state's free arcs stay as they are */
 	}
 	else
 	{
+		int			i;
+
 		if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE)
 		{
 			NERR(REG_ETOOBIG);
@@ -157,9 +160,16 @@ newstate(struct nfa *nfa)
 			return NULL;
 		}
 		nfa->v->spaceused += sizeof(struct state);
-		s->oas.next = NULL;
-		s->free = NULL;
-		s->noas = 0;
+		s->lastab = NULL;
+		/* initialize free arcs; this should match allocarc() */
+		for (i = 0; i < NINITARCS - 1; i++)
+		{
+			s->inita[i].type = 0;
+			s->inita[i].freechain = &s->inita[i + 1];
+		}
+		s->inita[i].type = 0;
+		s->inita[i].freechain = NULL;
+		s->free = &s->inita[0];
 	}
 
 	assert(nfa->nstates >= 0);
@@ -255,11 +265,11 @@ destroystate(struct nfa *nfa,
 	struct arcbatch *abnext;
 
 	assert(s->no == FREESTATE);
-	for (ab = s->oas.next; ab != NULL; ab = abnext)
+	for (ab = s->lastab; ab != NULL; ab = abnext)
 	{
 		abnext = ab->next;
+		nfa->v->spaceused -= ARCBATCHSIZE(ab->narcs);
 		FREE(ab);
-		nfa->v->spaceused -= sizeof(struct arcbatch);
 	}
 	s->ins = NULL;
 	s->outs = NULL;
@@ -377,41 +387,39 @@ allocarc(struct nfa *nfa,
 {
 	struct arc *a;
 
-	/* shortcut */
-	if (s->free == NULL && s->noas < ABSIZE)
-	{
-		a = &s->oas.a[s->noas];
-		s->noas++;
-		return a;
-	}
-
 	/* if none at hand, get more */
 	if (s->free == NULL)
 	{
 		struct arcbatch *newAb;
-		int			i;
+		size_t		narcs;
+		size_t		i;
 
 		if (nfa->v->spaceused >= REG_MAX_COMPILE_SPACE)
 		{
 			NERR(REG_ETOOBIG);
 			return NULL;
 		}
-		newAb = (struct arcbatch *) MALLOC(sizeof(struct arcbatch));
+		narcs = (s->lastab != NULL) ? s->lastab->narcs * 2 : FIRSTABSIZE;
+		if (narcs > MAXABSIZE)
+			narcs = MAXABSIZE;
+		newAb = (struct arcbatch *) MALLOC(ARCBATCHSIZE(narcs));
 		if (newAb == NULL)
 		{
 			NERR(REG_ESPACE);
 			return NULL;
 		}
-		nfa->v->spaceused += sizeof(struct arcbatch);
-		newAb->next = s->oas.next;
-		s->oas.next = newAb;
+		nfa->v->spaceused += ARCBATCHSIZE(narcs);
+		newAb->narcs = narcs;
+		newAb->next = s->lastab;
+		s->lastab = newAb;
 
-		for (i = 0; i < ABSIZE; i++)
+		for (i = 0; i < narcs - 1; i++)
 		{
 			newAb->a[i].type = 0;
 			newAb->a[i].freechain = &newAb->a[i + 1];
 		}
-		newAb->a[ABSIZE - 1].freechain = NULL;
+		newAb->a[i].type = 0;
+		newAb->a[i].freechain = NULL;
 		s->free = &newAb->a[0];
 	}
 	assert(s->free != NULL);
@@ -3413,7 +3421,7 @@ dumparc(struct arc *a,
 		FILE *f)
 {
 	struct arc *aa;
-	struct arcbatch *ab;
+	bool		found = false;
 
 	fprintf(f, "\t");
 	switch (a->type)
@@ -3451,15 +3459,29 @@ dumparc(struct arc *a,
 	}
 	if (a->from != s)
 		fprintf(f, "?%d?", a->from->no);
-	for (ab = &a->from->oas; ab != NULL; ab = 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 the
+	 * space; but it's enough to catch the likely problem of an arc being
+	 * misassigned to a different parent state.
+	 */
+	if (a >= a->from->inita && a < a->from->inita + NINITARCS)
+		found = true;			/* member of initial arcset */
+	else
 	{
-		for (aa = &ab->a[0]; aa < &ab->a[ABSIZE]; aa++)
-			if (aa == a)
+		struct arcbatch *ab;
+
+		for (ab = a->from->lastab; ab != NULL; ab = ab->next)
+		{
+			if (a >= ab->a && a < ab->a + ab->narcs)
+			{
+				found = true;
 				break;			/* NOTE BREAK OUT */
-		if (aa < &ab->a[ABSIZE])	/* propagate break */
-			break;				/* NOTE BREAK OUT */
+			}
+		}
 	}
-	if (ab == NULL)
+	if (!found)
 		fprintf(f, "?!?");		/* not in allocated space */
 	fprintf(f, "->");
 	if (a->to == 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 separate
+ * malloc for states with few out-arcs.  If more arcs are needed, the first
+ * 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 arcbatch, 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
 
 /*