• Tom Lane's avatar
    Improve performance of fixempties() pass in regular-expression compiler. · f5b7d103
    Tom Lane authored
    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.
    f5b7d103
regcomp.c 54.4 KB