diff options
| author | Tom Lane <tgl@sss.pgh.pa.us> | 2015-10-16 14:58:10 -0400 |
|---|---|---|
| committer | Tom Lane <tgl@sss.pgh.pa.us> | 2015-10-16 15:55:59 -0400 |
| commit | f5b7d103bc4a97a64f9e8ca83192a96767d9a34c (patch) | |
| tree | fd1311e86bbaa663fbfb1dbfe9da77417568b61c /src/backend/regex/regcomp.c | |
| parent | 579840ca05e73ac23a3c2616f050333ba853fb34 (diff) | |
| download | postgresql-f5b7d103bc4a97a64f9e8ca83192a96767d9a34c.tar.gz postgresql-f5b7d103bc4a97a64f9e8ca83192a96767d9a34c.zip | |
Improve performance of fixempties() pass in regular-expression compiler.
The previous coding took something like O(N^4) time to fully process a
chain of N EMPTY arcs. We can't really do much better than O(N^2) because
we have to insert about that many arcs, but we can do lots better than
what's there now. The win comes partly from using mergeins() to amortize
de-duplication of arcs across multiple source states, and partly from
exploiting knowledge of the ordering of arcs for each state to avoid
looking at arcs we don't need to consider during the scan. We do have
to be a bit careful of the possible reordering of arcs introduced by
the sort-merge coding of the previous commit, but that's not hard to
deal with.
Back-patch to all supported branches.
Diffstat (limited to 'src/backend/regex/regcomp.c')
| -rw-r--r-- | src/backend/regex/regcomp.c | 6 |
1 files changed, 2 insertions, 4 deletions
diff --git a/src/backend/regex/regcomp.c b/src/backend/regex/regcomp.c index ad9a79702ca..91eb77124c3 100644 --- a/src/backend/regex/regcomp.c +++ b/src/backend/regex/regcomp.c @@ -129,8 +129,6 @@ static struct arc *allocarc(struct nfa *, struct state *); static void freearc(struct nfa *, struct arc *); static void changearctarget(struct arc *, struct state *); static int hasnonemptyout(struct state *); -static int nonemptyouts(struct state *); -static int nonemptyins(struct state *); static struct arc *findarc(struct state *, int, pcolor); static void cparc(struct nfa *, struct arc *, struct state *, struct state *); static void sortins(struct nfa *, struct state *); @@ -160,8 +158,8 @@ static int push(struct nfa *, struct arc *); #define COMPATIBLE 3 /* compatible but not satisfied yet */ static int combine(struct arc *, struct arc *); static void fixempties(struct nfa *, FILE *); -static struct state *emptyreachable(struct nfa *, struct state *, struct state *); -static void replaceempty(struct nfa *, struct state *, struct state *); +static struct state *emptyreachable(struct nfa *, struct state *, + struct state *, struct arc **); static int isconstraintarc(struct arc *); static int hasconstraintout(struct state *); static void fixconstraintloops(struct nfa *, FILE *); |