More backreference performance improvements [take 2]

[Bonzini]

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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: regex-more-backref-performance-2.patch
Type: application/octet-stream
Size: 5670 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20021023/4e332a57/attachment.obj>