More backreference performance improvements [take 2]

["Bonzini" <bonzini at gnu dot org>]

This patch results in a 60% performance improvement with respect to my
previous more complicated patch (on top of which it should be applied).

Basically I do a limited form of hashing on the backreference cache in order
to check entry->hash only instead of both entry->node and entry->str_idx for
entries not in the cache.  I also cache the first and last enabled_idx for
the last node/str_idx pair.

Time without the patch for factor.sed 5.1s
With caching 4.0s
With caching+hashing 2.1s


2002-10-23  Paolo Bonzini  (bonzini@gnu.org)

        * posix/regexec.c (sift_states_bkref): cache the limits
        of the inner loop, and use a limited form of hashing
        to save a comparison for entries not belonging to the
        current node.
        (match_ctx_init): initialize the cache
        (match_ctx_add_entry): update the cache
        * posix/regex_internal.h (re_match_context_t): added
        fields for the cache
        (struct re_backref_cache_entry): added field for the hash

Paolo Bonzini

Attachment: regex-more-backref-performance-2.patch
Description: Binary data