www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D 1.0: std.regexp incredibly slow!

reply Markus Dangl <danglm in.tum.de> writes:
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: 7bit

Hi *,

i stumbled on what seems to be a bug in std.regexp: It is incredibly
slow using the following pattern:
RegExp("^\\s+(\\d+)\\s+(\\d+)\\s+\\w+\\s+(\\w+)\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+(.*)\r?\n?$")

I don't really get the regexp code, so i can't debug it myself, but i
have a PHP (!!) script that executes the same regexp in milliseconds.

I attached code to test it, can someone please confirm?

Thanks,
Markus

PS: Is there a quick way to fix this or are there bindings for other
RegExp libs that i can use (Linux and Windows required) - i need to fix
my program soon :) atm i'm looking for workarounds (splitting it into
small regexps).
Sep 22 2009
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 22 Sep 2009 11:55:53 -0400, Markus Dangl <danglm in.tum.de> wrote:

 Hi *,

 i stumbled on what seems to be a bug in std.regexp: It is incredibly
 slow using the following pattern:
 RegExp("^\\s+(\\d+)\\s+(\\d+)\\s+\\w+\\s+(\\w+)\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+(.*)\r?\n?$")

 I don't really get the regexp code, so i can't debug it myself, but i
 have a PHP (!!) script that executes the same regexp in milliseconds.

 I attached code to test it, can someone please confirm?

 Thanks,
 Markus

 PS: Is there a quick way to fix this or are there bindings for other
 RegExp libs that i can use (Linux and Windows required) - i need to fix
 my program soon :) atm i'm looking for workarounds (splitting it into
 small regexps).

This is a common problem with some regex designs. Java has (or had) the same problem. I don't know if its fixable, you may want to try Tango's regex package. -Steve
Sep 22 2009
prev sibling next sibling parent reply Jeremie Pelletier <jeremiep gmail.com> writes:
Markus Dangl wrote:
 Hi *,
 
 i stumbled on what seems to be a bug in std.regexp: It is incredibly
 slow using the following pattern:
 RegExp("^\\s+(\\d+)\\s+(\\d+)\\s+\\w+\\s+(\\w+)\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+(.*)\r?\n?$")
 
 I don't really get the regexp code, so i can't debug it myself, but i
 have a PHP (!!) script that executes the same regexp in milliseconds.
 
 I attached code to test it, can someone please confirm?
 
 Thanks,
 Markus
 
 PS: Is there a quick way to fix this or are there bindings for other
 RegExp libs that i can use (Linux and Windows required) - i need to fix
 my program soon :) atm i'm looking for workarounds (splitting it into
 small regexps).
 

You could write your own bindings to PCRE and use that, since its what PHP uses. Maybe someone on dsource already did it too.
Sep 22 2009
parent Markus Dangl <danglm in.tum.de> writes:
Jeremie Pelletier schrieb:
 You could write your own bindings to PCRE and use that, since its what
 PHP uses. Maybe someone on dsource already did it too.

Thank you for the tip, i found some bindings at: http://svn.dsource.org/projects/dwin/trunk/text/pcre/ I'll have a look at them later. At the moment i wrote a custom workaround for the problematic regexp. (Doing std.string.split before the regexp can help in the presented case...). Anyways the implementation in Phobos is questionable.
Sep 22 2009
prev sibling next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Some regexes are very slow with phobos, I believe this is due to 
backtracking. I'm not familiar enough with the issue, whether some other 
regex engine might be able to avoid backtracking or not or how to rewrite 
it.

I found this link though, perhaps it is useful to you: 
http://www.regular-expressions.info/catastrophic.html
Sep 22 2009
prev sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Markus Dangl wrote:
 Hi *,
 
 i stumbled on what seems to be a bug in std.regexp: It is incredibly
 slow using the following pattern:
 RegExp("^\\s+(\\d+)\\s+(\\d+)\\s+\\w+\\s+(\\w+)\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+(.*)\r?\n?$")
 

I admit my regex-fu is weak (especially for PCRE), but doesn't $ match end of line, making \r?\n? unnecessary or even causing the thing to match one line with a bunch of stuff followed by an empty line? If you take \r?\n? out, RegExp performs considerably faster, though I couldn't say what implications it would have on what you're using it for.
Sep 22 2009
parent Markus Dangl <danglm in.tum.de> writes:
Ellery Newcomer schrieb:
 Markus Dangl wrote:
 Hi *,

 i stumbled on what seems to be a bug in std.regexp: It is incredibly
 slow using the following pattern:
 RegExp("^\\s+(\\d+)\\s+(\\d+)\\s+\\w+\\s+(\\w+)\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+\\S+\\s+(.*)\r?\n?$")

I admit my regex-fu is weak (especially for PCRE), but doesn't $ match end of line, making \r?\n? unnecessary or even causing the thing to match one line with a bunch of stuff followed by an empty line? If you take \r?\n? out, RegExp performs considerably faster, though I couldn't say what implications it would have on what you're using it for.

In this case $ matches end of subject, i.e. the end of the string. I assume there is an option for making it match at end-of-line. (At least thats the way it works in PCRE).
Sep 22 2009