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: Thu, 25 Feb 2021 22:51:47 -0500
Message-ID: <221848.1614311507@sss.pgh.pa.us> (raw)
In-Reply-To: <168861.1614298592@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>
<4185677.1614208792@sss.pgh.pa.us>
<168861.1614298592@sss.pgh.pa.us>
I wrote:
> So I rearranged things to allocate arcs out of a common pool, and for
> good measure made the state allocation code do the same thing. I was
> pretty much blown away by the results: not only is the average-case
> space usage about half what it is on HEAD, but the worst-case drops
> by well more than a factor of ten.
BTW, I was initially a bit baffled by how this could be. Per previous
measurements, the average number of arcs per state is around 4; so
if the code is allocating ten arcs for each state right off the bat,
it's pretty clear how we could have a factor-of-two-or-so bloat
problem. And I think that does explain the average-case results.
But it can't possibly explain bloats of more than 10x.
After further study I think this is what explains it:
* The "average number of arcs" is pretty misleading, because in
a large NFA some of the states have hundreds of out-arcs, while
most have only a couple.
* The NFA is not static; the code moves arcs around all the time.
There's actually a function (moveouts) that deletes all the
out-arcs of a state and creates images of them on another state.
That operation can be invoked a lot of times during NFA optimization.
* Once a given state has acquired N out-arcs, it keeps that pool
of arc storage, even if some or all of those arcs get deleted.
Indeed, the state itself could be dropped and later recycled,
but it still keeps its arc pool. Unfortunately, even if it does
get recycled for re-use, it's likely to be resurrected as a state
with only a couple of out-arcs.
So I think the explanation for 20x or 30x bloat arises from the
optimize pass resulting in having a bunch of states that have large
but largely unused arc pools. Getting rid of the per-state arc pools
in favor of one common pool fixes that nicely.
I realized while looking at this that some cycles could be shaved
from moveouts, because there's no longer a reason why it can't just
scribble on the arcs in-place (cf. now-obsolete comment on
changearctarget()). It's late but I'll see about improving that
tomorrow.
regards, tom lane
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: <221848.1614311507@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