Re: [PATCH] Three regex speedups, one of which is actually a bugfix

[Jakub Jelinek <jakub at redhat dot com>]

On Thu, Jan 01, 2004 at 09:58:22PM +0100, Paolo Bonzini wrote:
> > It is not initialized always, because in the common case there is no
> > \<, \>, \b, \B, \w and \W in regular expression and so differentiating
> > between word and non-word characters is not needed at all.
> 
> But, every match goes down to build_tr_table, which calls IS_WORD_CHAR 256 times and

AFAIK this is up to 256 times, not always 256.  Often just once.

> brings __ctype_b_loc high in the profile.  That's why it's better to always

1) in glibc it doesn't ever call __ctype_b_loc (), but uses __thread access
2) __ctype_b_loc () is __attribute__((const)), so if the compiler doesn't
   for the !_LIBC case move it out of the loop, it should be improved to do
   so

If that

              if (BE (dfa->word_char != NULL, 0)
                  && (dfa->word_char[i] & mask))

in my patch instead of the

	      if (dfa->word_char[i] & mask)

in your patch shows up in profiles (note that dfa->word_char will be usually
NULL), then the loop can be duplicated for if (BE (dfa->word_char != NULL, 0))
(where it checks if (dfa->word_char[i] & mask)) and in the else loop do
trtable[ch] = dest_states[j]; unconditionally.  On IA-32 this took
additional 144 .text bytes but if the loop is executed many times on average
(e.g. with many periods in regex), it would certainly speed up the loop.

> initialize word_char.  If you use a cached bitset instead of calling isalnum, it
> makes no difference if the cached bitset is correct (initialized with isalnum) or
> all-zeros (unless you go down into branch prediction which is overkill, isn't it?).
> Using a flag to avoid iswalnum calls in IS_WIDE_WORD_CHAR is again a complementary
> optimization, which can be done with a separate patch.

But as I said, I've posted yesterday just one variant of the patch and
talked about 2 variants (word_char == NULL when word ops are not seen and
word_char empty bitmap).  Below is attached the second variant:

	Jakub

Attachment: P5
Description: Text document