Re: Some regular-expression performance hacking

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