www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Bad performance of simple regular expression - why??

reply MarcL <lohse mpimp-golm.mpg.de> writes:
hi everyone, 

first of all i want to say that i'm not a professional programmer  - so the
problem i have might be 
caused by my own  lack of experience. Nevertheless i want to describe it,
hoping that someone in this 
group might be able to tell me what's wrong. I am a molecular biologist and i
often have to deal with 
larger amounts of DNA and protein sequence data (which is in principle text). I
am mainly using Perl to 
process these DNA files, and Perl generally performs very well (regular
expressions are actually the killer 
tool for working with DNA sequences). Unfortunately not everything in Perl is a
fast as the regular 
expressions and so i started trying to learn a language that can be compiled to
produce fast 
executables : C++ - and went crazy because everything is so complicated. All
the ugly details that Perl 
takes care of for the user have to be organized manually and that really gave
me the creeps. Then i 
learned about D and it sounded like it the solution to my problem: A compilable
language that supports 
associative arrays, garbage collection and (most importantly for me) regular
expressions! Great! I 
experimented a bit and actually managed to write small working programlet
directly. I was delighted! 
But now comes the reason why i write all this: Being enthusiastic about this
new nice language i started 
to write a module that should implement basic functions for working with the
most common DNA 
sequence file formats. To parse these files i planned to use regular
expressions. So far so good. When 
testing my module with a small DNA file everything seemed OK -then i tried to
use it to parse a more 
real world-sized DNA file (~155000 characters of DNA sequence plus about the
same amount of textual 
information) and had to find out that a simple std.regexp.split call took about
59 seconds!!! I could not 
believe it and wrote a little Perl script doing the same thing and it took less
than 1s!! What's wrong 
here??? This can't really be true, can it? Is the implementation of regular
expressions in the phobos 
library so bad or preliminary that it is so much less performant than the Perl
regex engine? It's actually 
not usable for me like this (which is a sad think because i really like the
other features of D and would 
like to use it). Am i making mistakes or do i simply have to wait for a better
version of phobos? 

Any comments or suggestions would be great. 

cheers
Feb 05 2007
next sibling parent reply "Bill Lear" <rael see.sig.com> writes:
MarcL <lohse mpimp-golm.mpg.de> writes:


 .... Am i making mistakes or do i simply have to wait for a better
 version of phobos?
 
 Any comments or suggestions would be great. 


Please post a representative sample so we can help you, and do please
try to post lines < 80 characters long, if possible.


Bill
--
Bill Lear
r * e *   * o * y * a * c * m
* a * l * z * p * r * . * o *
Feb 05 2007
parent MarcL <lohse mpimp-golm.mpg.de> writes:
Bill Lear Wrote:


 MarcL <lohse mpimp-golm.mpg.de> writes:
 

 .... Am i making mistakes or do i simply have to wait for a better
 version of phobos?
 
 Any comments or suggestions would be great. 


 
 Please post a representative sample so we can help you, and do please
 try to post lines < 80 characters long, if possible.
 
 
 Bill
 --
 Bill Lear
 r * e *   * o * y * a * c * m
 * a * l * z * p * r * . * o *


first of all thanks a lot to everyone who answered on my
posting i did not expect to receive feedback so quickly.

This is the piece of code that runs so slowly:

<code>

	char[] raw_sequence, stripped_sequence, header_segment, feature_segment;
	char[][] gb_segments, seq_segments;
	
	raw_sequence = cast(char[])std.file.read("/Users/marc/Desktop/sequences.gb");
	gb_segments = std.regexp.split(raw_sequence, "FEATURES", "");
	writefln("split into ", gb_segments.length, " segments");
	seq_segments = std.regexp.split(gb_segments[1], "ORIGIN", "");
	header_segment = gb_segments[0];
	feature_segment = std.regexp.sub(seq_segments[0], "^.*location/qualifiers\n",
"", "i");
	stripped_sequence = std.string.toupper(std.regexp.sub(seq_segments[1], "[0-9\t
\n/]", "", "g"));

</code>

I did not precompile the regular expression, so maybe this 
is one of the reasons why it's slow, but it doesn't contain any loops
so the expressions are only used once. If anyone wants to try that
on his own machine - i attached the "sequences.gb" file.

I have tested the code on a PowerBook (G4 1,5GHz) using 
gdc and also on a Linux machine (1,8GHz PentiumM) using 
the original dmd compiler - but the results were the same
Feb 05 2007
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
MarcL wrote:

 hi everyone, 
 
 first of all i want to say that i'm not a professional programmer  - so the
problem i have might be 
 caused by my own  lack of experience. Nevertheless i want to describe it,
hoping that someone in this 
 group might be able to tell me what's wrong. I am a molecular biologist and i
often have to deal with 
 larger amounts of DNA and protein sequence data (which is in principle text).
I am mainly using Perl to 
 process these DNA files, and Perl generally performs very well (regular
expressions are actually the killer 
 tool for working with DNA sequences). Unfortunately not everything in Perl is
a fast as the regular 
 expressions and so i started trying to learn a language that can be compiled
to produce fast 
 executables : C++ - and went crazy because everything is so complicated. All
the ugly details that Perl 
 takes care of for the user have to be organized manually and that really gave
me the creeps. Then i 
 learned about D and it sounded like it the solution to my problem: A
compilable language that supports 
 associative arrays, garbage collection and (most importantly for me) regular
expressions! Great! I 
 experimented a bit and actually managed to write small working programlet
directly. I was delighted! 
 But now comes the reason why i write all this: Being enthusiastic about this
new nice language i started 
 to write a module that should implement basic functions for working with the
most common DNA 
 sequence file formats. To parse these files i planned to use regular
expressions. So far so good. When 
 testing my module with a small DNA file everything seemed OK -then i tried to
use it to parse a more 
 real world-sized DNA file (~155000 characters of DNA sequence plus about the
same amount of textual 
 information) and had to find out that a simple std.regexp.split call took
about 59 seconds!!! I could not 
 believe it and wrote a little Perl script doing the same thing and it took
less than 1s!! What's wrong 
 here??? This can't really be true, can it? Is the implementation of regular
expressions in the phobos 
 library so bad or preliminary that it is so much less performant than the Perl
regex engine? It's actually 
 not usable for me like this (which is a sad think because i really like the
other features of D and would 
 like to use it). Am i making mistakes or do i simply have to wait for a better
version of phobos? 
 
 Any comments or suggestions would be great. 
 
 cheers 
 


Like Bill said, a sample would be helpful.

The most common mistake is to not precompile the regexp.
For instance using std.regexp.search with the same pattern string is not 
optimal.

If you're going to be using the same pattern multiple times, then you 
should create a RegExp object once, and then apply it multiple times 
using its search, match etc methods.

Regardless, perl was basically created as a convenient way to use 
regular expressions, so it's implementation could very likely be more 
efficient than D's.

Do perl regexp's handle unicode/utf8 properly these days?
(Actually, do D's for that matter?)

--bb
Feb 05 2007
next sibling parent reply Tomas Lindquist Olsen <tomas famolsen.dk> writes:
On Tue, 06 Feb 2007 08:47:53 +0900, Bill Baxter wrote:

 Regardless, perl was basically created as a convenient way to use regular
 expressions, so it's implementation could very likely be more efficient
 than D's.


I stumbled across this link last night. It says something slightly
different...
Feb 05 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Tomas Lindquist Olsen wrote:

 On Tue, 06 Feb 2007 08:47:53 +0900, Bill Baxter wrote:

 Regardless, perl was basically created as a convenient way to use regular
 expressions, so it's implementation could very likely be more efficient
 than D's.


 
 I stumbled across this link last night. It says something slightly
 different...


I'm all ears...
Feb 05 2007
parent reply Tomas Lindquist Olsen <tomas famolsen.dk> writes:
On Tue, 06 Feb 2007 10:35:06 +0900, Bill Baxter wrote:


 Tomas Lindquist Olsen wrote:

 On Tue, 06 Feb 2007 08:47:53 +0900, Bill Baxter wrote:

 Regardless, perl was basically created as a convenient way to use
 regular expressions, so it's implementation could very likely be more
 efficient than D's.


 
 I stumbled across this link last night. It says something slightly
 different...


 
 I'm all ears...


Oups.. Here you go:

http://swtch.com/~rsc/regexp/regexp1.html
Feb 05 2007
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Tomas Lindquist Olsen wrote:

 http://swtch.com/~rsc/regexp/regexp1.html


That looks pretty cool. Anyone care to take a stab at implementing this 
in std.regexp? It could be done by examining the generated bytecode and 
attempting to convert it to an NFA. If that succeeds, then great, do the 
NFA. If it fails, then fallback to the original method.
Feb 05 2007
next sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Walter Bright <newshound digitalmars.com> wrote


 If it fails, then fallback to the original method.


It is a ridiculous business to incorporate additional algorithms 
because a current implementation is broken.

The well known chain of converting RE->NFA->DFA->minimal DFA
should handle that problem fast, because the minimal DFA for a RE of 
the form ((a?)^n a^n) for fixed n is a chain of 2n+1 nodes, which 
corresponds to the longest acceptable input plus final state.

In this chain the first n nodes are nonfinal, all others are final.
The first node is the start node.
All nodes have transitions to the next node under "a".

That is recognision time is linear in the length of the input: no 
exponential behaviour. 

-manfred
Feb 06 2007
parent reply Walter Bright <newshound digitalmars.com> writes:
Manfred Nowak wrote:

 Walter Bright <newshound digitalmars.com> wrote
 

 If it fails, then fallback to the original method.




My understanding is that backtracking is difficult to do with the DFA.
Feb 06 2007
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Walter Bright <newshound digitalmars.com> wrote


 My understanding is that backtracking is difficult to do with the
 DFA.


On converting _one_ regular expression to a DFA there is no need to 
backtrack ever.

The example considered in the article is roughly equivalent to
a^n a?^n. No need for backtracking and the normal tool chain handles 
this.

Also for maximal munching several regular expression there is no need 
for backtracking. 

-manfred
Feb 06 2007
parent reply Jascha Wetzel <"[firstname]" mainia.de> writes:
Manfred Nowak wrote:

 Also for maximal munching several regular expression there is no need 
 for backtracking. 


maximal munch, non-greedy matching and negative matches would usually
use backtracking. doing it without backtracking would require to use
several DFAs - or is there a simpler method?

afaik, the "school-book-way" for backtracking are deterministic pushdown
automatons (PDAs) that can also be interpreted efficiently or compiled
to bytecode.
so i don't see why there shouldn't be backtracking in the regexp
implementation.
Feb 08 2007
parent reply Benji Smith <dlanguage benjismith.net> writes:
Jascha Wetzel wrote:

 Manfred Nowak wrote:

 Also for maximal munching several regular expression there is no need 
 for backtracking. 


 
 maximal munch, non-greedy matching and negative matches would usually
 use backtracking. doing it without backtracking would require to use
 several DFAs - or is there a simpler method?
 
 afaik, the "school-book-way" for backtracking are deterministic pushdown
 automatons (PDAs) that can also be interpreted efficiently or compiled
 to bytecode.
 so i don't see why there shouldn't be backtracking in the regexp
 implementation.


The problem is that most regex engines (in fact, all of them, as far as 
I know) use backtracking even when a DFA implementation could be used to 
determine (much earlier in the search process) that a match is impossible.

A backtracking approach might be necessary with positive and negative 
lookaround assertions (though I still suspect that a DFA could even be 
used for these cases), but every mainstream regex engine uses a 
backtracking approach even for simple choice situations like (cat|car) 
where a DFA would be much more appropriate.

And, by the way, it's possible to create a DFA implementation that 
degrades into a backtracking matcher for certain subexpressions.

--benji
Feb 09 2007
parent "Joel C. Salomon" <JoelCSalomon Gmail.com> writes:
Benji Smith wrote:

 The problem is that most regex engines (in fact, all of them, as far as 
 I know) use backtracking even when a DFA implementation could be used to 
 determine (much earlier in the search process) that a match is impossible.


This has been linked to in this thread, but Ken Thompson’s algorithm 
does /not/ use backtracking, and there are open-source implementations 
around; see <http://www.swtch.com/~rsc/regexp/regexp1.html>.

--Joel
Feb 09 2007
prev sibling parent Benji Smith <dlanguage benjismith.net> writes:
Walter Bright wrote:

 Tomas Lindquist Olsen wrote:

 http://swtch.com/~rsc/regexp/regexp1.html


 
 That looks pretty cool. Anyone care to take a stab at implementing this 
 in std.regexp? It could be done by examining the generated bytecode and 
 attempting to convert it to an NFA. If that succeeds, then great, do the 
 NFA. If it fails, then fallback to the original method.


A little while back, at my job, I implemented a regex parser (in Java) 
that builds an NFA and then transforms it into a DFA, re-serializing it 
into a regex for consumption by any old regex engine.

For example, this regex assumes NFA performance characteristics when 
compiled by the (java, perl, python, etc) regex engine:

   (?:cat|car|cut|cute|cumbersome)

This regex is semantically identical (meaning that it will produce 
exactly the same set of matches as the simpler expression), but it 
assumes DFA performance characteristics in the regex engine:

   c(?:a[tr]|u(?:te?|umbersome))

Since I needed my regular expressions to execute in an ordinary regex 
engine, I couldn't tweak the engine internals, but I could trick the 
regex engine into being a DFA.

The major caveat to this approach is that parenthetical groups get 
jumbled. If you use parentheses to capture text (rather than just to 
match it), the numbering of your backreferences is going to get all 
screwed up. When I use this approach, I almost always use noncapturing 
parentheses (?: ... ) rather than ordinary parens.

However, if you had control of the regex engine itself (rather than just 
feeding tweaked expressions into an ordinary engine), you could easily 
implement DFA behavior characteristics without changing the capturing 
semantics.

I'd implement this myself for D, but I'm afraid my NDA with my employer 
would probably prevent me from doing so. The theory is straightforward, 
though, so it should be do-able by anyone with the appropriate RE 
experience.

--Benji Smith
Feb 07 2007
prev sibling parent "Joel C. Salomon" <JoelCSalomon Gmail.com> writes:
Tomas Lindquist Olsen wrote:

 I stumbled across this link last night. It says something slightly different...
 
 http://swtch.com/~rsc/regexp/regexp1.html


The regexp library isn’t the only really useful bit of software packed 
into Plan 9.  I’m implementing a compiler for the first time (C-ish, not 
D) under Plan 9, and it’s a constant temptation to add “just one more 
feature” because there’s a library to support it.

--Joel
Feb 05 2007
prev sibling parent MarcL <lohse mpimp-golm.mpg.de> writes:
 

 
 Like Bill said, a sample would be helpful.
 
 The most common mistake is to not precompile the regexp.
 For instance using std.regexp.search with the same pattern string is not 
 optimal.
 
 If you're going to be using the same pattern multiple times, then you 
 should create a RegExp object once, and then apply it multiple times 
 using its search, match etc methods.
 
 Regardless, perl was basically created as a convenient way to use 
 regular expressions, so it's implementation could very likely be more 
 efficient than D's.
 
 Do perl regexp's handle unicode/utf8 properly these days?
 (Actually, do D's for that matter?)
 
 --bb



here's a link to the sequences.gb file (attaching it didn't work)
http://www.ncbi.nlm.nih.gov/entrez/viewer.fcgi?db=nucleotide&val=76559634
Feb 05 2007