Re: [Chicken-users] an oddly slow regex ...

[Peter Bex]

On Sat, Oct 26, 2013 at 10:37:36AM -0700, Matt Welland wrote:
> This regex is so slow that you don't need a timer to see the impact (at
> least not on my machine with chicken 4.8.0):
> 
>  (string-match "[a-z][a-z0-9\\-_.]{0,20}" "a012345678901234567890123456789")
> 
> Changing the {0,20} to + makes it run normally fast so I just replaced the
> regex with a string-length and modified the "{0,20}" to "+" . I don't
> necessarily need a fix for this but it seems like a possible symptom of a
> deeper problem so I thought I'd report it.

Hi Matt,

Thanks for your report.  I'm afraid this is a known problem with
Irregex - to avoid producing a state machine with too many states,
it will always use a backtracking implementation for all repetition
counts.

I think it's best to take a look at how to fix this upstream first.
Maybe Alex has an idea of how to do that.

> Pre-compiling the regex didn't seem to make any difference.

That's because the backtracker matches really slowly.

> Just for completeness I compared with Ruby and the ruby equivalent
> is (in human terms) instant.
> 
> "a012345678901234567890123456789".match(/[a-z][a-z0-9]{0,20}/)

Thanks for that!  We need more of such real-world test cases.
Ideally I'd love to have a complete library of regex examples, which
we can use to optimize irregex further.

By the way, I note that your Ruby regex isn't exactly the same as the
one you used in CHICKEN.  Does it make a difference if you use the
same regex?

Cheers,
Peter
-- 
http://www.more-magic.net