www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.regexp.split very slow - a bug?

reply Marc Lohse <lohse mpimp-golm.mpg.de> writes:
hi again,
two days ago i had posted that regular expressions
were running very slow - here comes a more detailed
description of that problem.

It seems that the std.regexp.split function has a 
problem (or i am a moron and use it in a wrong way,
but, as i mentioned before i am a biologist and not
a professional programmer and i'd be happy about 
help if case 2 is true).

The thing i want to do is read in a DNA sequence file
that also contains information about the genes found
in the raw DNA sequence. The file is in a commonly
used format called GenBank and the different data segments
are seperated by keywords which should make it easy 
to use std.regexp.split to dissect it. The following code 
is just an example that tries to split a GenBank file 
at the "ORIGIN" keyword. The file has a size of 323 KB
and if you want to reproduce my "experiment" you 
can obtain it here:
http://www.ncbi.nlm.nih.gov/entrez/viewer.fcgi?db=nucleotide&val=76559634


// regex.d
import std.stdio;
import std.regexp;
import std.file;

void main()
{
	char [] gb_data;
	char [][] segments;
	gb_data = cast(char[])read("/home/marc/Desktop/tobacco.gb");
	
	segments = split(gb_data, "ORIGIN", "");
	
	writefln("seq segments: ", segments.length);
	
}

The following happens when i run it:
marc marclinux:~/Desktop> time ./regex
seq segments: 197549

real    12m52.420s
user    12m48.132s
sys     0m2.812s

The execution takes ALMOST THIRTEEN MINUTES!! which
made me fall from my chair. After having climbed back
on it i tried the same in perl:

#regex.pl
#!/usr/bin/perl -w

use strict;

my $gb_data = "";
my  segments;

open FILE, "/home/marc/Desktop/tobacco.gb";
while (<FILE>)
{
	$gb_data .= $_;
}
close FILE;

 segments = split /ORIGIN/, $gb_data;

print "seq segment: ".length($segments[1])."\n"

output:
marc marclinux:~/Desktop> time ./regex.pl
seq segment: 197549

real    0m0.034s
user    0m0.024s
sys     0m0.012s

....well it took 34ms to do the same thing. I could
not believe it and rewrote it using std.regexp.search 
instead of std.regexp.split:

//regex2.d
import std.stdio;
import std.regexp;
import std.file;

void main()
{
	char [] gb_data;
	
	gb_data = cast(char[])read("/home/marc/Desktop/tobacco.gb");
	
	auto m = search(gb_data, "ORIGIN", "");
	
	writefln("seq segment: ", m.post.length);
	
}

output:
marc marclinux:~/Desktop> time ./regex2
seq segment: 197549

real    0m0.025s
user    0m0.024s
sys     0m0.000s

AHA. So D is faster than Perl - it took 25ms, but the
split function is obviously *not suitable* for splitting
a long text at a simple, single word (actually this does not
even make use of complicated regular expression snytax).

Becoming curious i rewrote the thing again, now using
std.string.find:

//find.d
import std.stdio;
import std.string;
import std.file;

void main()
{
	char [] gb_data, seq_segment, pattern;
	long pos;
	
	pattern = "ORIGIN";
	
	gb_data = cast(char[])read("/home/marc/Desktop/tobacco.gb");
	
	pos = find(gb_data, pattern);
	seq_segment = gb_data[(pos+pattern.length)..gb_data.length];
	
	writefln("seq segment: ",seq_segment.length);
	//writefln("SEQ segment", m.post);
	
}

output:
marc marclinux:~/Desktop> time ./find
seq segment: 197549

real    0m0.005s
user    0m0.000s
sys     0m0.004s
marc marclinux:~/Desktop> 

whoa! Now it only takes 5ms. So my problem seems to be
solved - i will use either the search or the find variant.

Interestingly, when splitting the same text at newlines
the execution just takes about 13ms. I have no idea why
the split function behaves so differently and this is also
my question for the experts.

cheers
ml
Feb 07 2007
next sibling parent Marc Lohse <lohse mpimp-golm.mpg.de> writes:
std.regex.split very slow -> bug?

 hi again,
 two days ago i had posted that regular expressions
 were running very slow - here comes a more detailed
 description of that problem.
 
 It seems that the std.regexp.split function has a 
 problem (or i am a moron and use it in a wrong way,
 but, as i mentioned before i am a biologist and not
 a professional programmer and i'd be happy about 
 help if case 2 is true).
 
 The thing i want to do is read in a DNA sequence file
 that also contains information about the genes found
 in the raw DNA sequence. The file is in a commonly
 used format called GenBank and the different data segments
 are seperated by keywords which should make it easy 
 to use std.regexp.split to dissect it. The following code 
 is just an example that tries to split a GenBank file 
 at the "ORIGIN" keyword. The file has a size of 323 KB
 and if you want to reproduce my "experiment" you 
 can obtain it here:
 http://www.ncbi.nlm.nih.gov/entrez/viewer.fcgi?db=nucleotide&val=76559634
 
 
 // regex.d
 import std.stdio;
 import std.regexp;
 import std.file;
 
 void main()
 {
 	char [] gb_data;
 	char [][] segments;
 	gb_data = cast(char[])read("/home/marc/Desktop/tobacco.gb");
 	
 	segments = split(gb_data, "ORIGIN", "");
 	
 	writefln("seq segments: ", segments.length);
 	
 }
 
 The following happens when i run it:
 marc marclinux:~/Desktop> time ./regex
 seq segments: 197549
 
 real    12m52.420s
 user    12m48.132s
 sys     0m2.812s
 
 The execution takes ALMOST THIRTEEN MINUTES!! which
 made me fall from my chair. After having climbed back
 on it i tried the same in perl:
 
 #regex.pl
 #!/usr/bin/perl -w
 
 use strict;
 
 my $gb_data = "";
 my  segments;
 
 open FILE, "/home/marc/Desktop/tobacco.gb";
 while (<FILE>)
 {
 	$gb_data .= $_;
 }
 close FILE;
 
  segments = split /ORIGIN/, $gb_data;
 
 print "seq segment: ".length($segments[1])."\n"
 
 output:
 marc marclinux:~/Desktop> time ./regex.pl
 seq segment: 197549
 
 real    0m0.034s
 user    0m0.024s
 sys     0m0.012s
 
 ....well it took 34ms to do the same thing. I could
 not believe it and rewrote it using std.regexp.search 
 instead of std.regexp.split:
 
 //regex2.d
 import std.stdio;
 import std.regexp;
 import std.file;
 
 void main()
 {
 	char [] gb_data;
 	
 	gb_data = cast(char[])read("/home/marc/Desktop/tobacco.gb");
 	
 	auto m = search(gb_data, "ORIGIN", "");
 	
 	writefln("seq segment: ", m.post.length);
 	
 }
 
 output:
 marc marclinux:~/Desktop> time ./regex2
 seq segment: 197549
 
 real    0m0.025s
 user    0m0.024s
 sys     0m0.000s
 
 AHA. So D is faster than Perl - it took 25ms, but the
 split function is obviously *not suitable* for splitting
 a long text at a simple, single word (actually this does not
 even make use of complicated regular expression snytax).
 
 Becoming curious i rewrote the thing again, now using
 std.string.find:
 
 //find.d
 import std.stdio;
 import std.string;
 import std.file;
 
 void main()
 {
 	char [] gb_data, seq_segment, pattern;
 	long pos;
 	
 	pattern = "ORIGIN";
 	
 	gb_data = cast(char[])read("/home/marc/Desktop/tobacco.gb");
 	
 	pos = find(gb_data, pattern);
 	seq_segment = gb_data[(pos+pattern.length)..gb_data.length];
 	
 	writefln("seq segment: ",seq_segment.length);
 	//writefln("SEQ segment", m.post);
 	
 }
 
 output:
 marc marclinux:~/Desktop> time ./find
 seq segment: 197549
 
 real    0m0.005s
 user    0m0.000s
 sys     0m0.004s
 marc marclinux:~/Desktop> 
 
 whoa! Now it only takes 5ms. So my problem seems to be
 solved - i will use either the search or the find variant.
 
 Interestingly, when splitting the same text at newlines
 the execution just takes about 13ms. I have no idea why
 the split function behaves so differently and this is also
 my question for the experts.
 
 cheers
 ml

The same funny thing happens when using std.regexp.sub. In the following line i want to remove all non-DNA characters from the read in sequence segment using sub: stripped_sequence = sub(seq_segment, "[0-9\n\t/ ]", "", "g"); output: time ./bio_test real 0m17.154s user 0m16.737s sys 0m0.032s Again this expression takes unexpectedly long to execute: about 17s on my PentiumM 1,8GHz. When i reformulate the task avoiding regular expressions: char[] clean_seq = ""; foreach (char N; stripped_sequence) { if ((N == '0') || (N == '1') || (N == '2') || (N == '3') || (N == '4') || (N == '5') || (N == '6') || (N == '7') || (N == '8') || (N == '9') || (N == ' ') || (N == '\n') || (N == '\t') || (N == '/')) continue; clean_seq ~= N; } it looks (and is) very ugly but it runs faster: output: time ./bio_test real 0m0.413s user 0m0.040s sys 0m0.004s Note that the actual computation time is only about 40ms (the real time is longer because the sequence and other info is printed to STDOUT). Again my question what's wrong here? I used the regexp.sub exactly the way that it's used in public example code snippets. Have other people also had these problems or am i the first to use the regular expressions of D on longer text strings? (although i wouldn't think that 323KB of text are really long). Any help and or suggestions|comments would be extremely welcome!
Feb 07 2007
prev sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Marc Lohse wrote:
 Becoming curious i rewrote the thing again, now using
 std.string.find:
 

 
 output:
 marc marclinux:~/Desktop> time ./find
 seq segment: 197549
 
 real    0m0.005s
 user    0m0.000s
 sys     0m0.004s
 marc marclinux:~/Desktop> 
 
 whoa! Now it only takes 5ms. So my problem seems to be
 solved - i will use either the search or the find variant.

I wanted to post this the first time, but I didn't feel like trying out the difference: std.string *also* has a 'split' function. I just tried it after reading the first part of your post and it took 4 milliseconds on my computer (while the regexp version is still running).
 Interestingly, when splitting the same text at newlines
 the execution just takes about 13ms. I have no idea why
 the split function behaves so differently and this is also
 my question for the experts.

Yes, that's a bit weird.
Feb 07 2007