From: Tom Lane <tgl@sss.pgh.pa.us>
To: Joel Jacobson <joel@compiler.org>
Cc: Chapman Flack <chap@anastigmatix.net>
Cc: pgsql-hackers@lists.postgresql.org
Subject: Re: Some regular-expression performance hacking
Date: Wed, 24 Feb 2021 18:19:52 -0500
Message-ID: <4185677.1614208792@sss.pgh.pa.us> (raw)
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>
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
Attachments:0007-smarter-arc-allocation.patch (text/x-diff, 5.7K) downloaddiff --git a/src/backend/regex/regc_nfa.c b/src/backend/regex/regc_nfa.cindex 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.hindex 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
/*
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tgl@sss.pgh.pa.us, joel@compiler.org, chap@anastigmatix.net, pgsql-hackers@lists.postgresql.org
Subject: Re: Some regular-expression performance hacking
In-Reply-To: <4185677.1614208792@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox