Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Slow Regex Code

Reply
Thread Tools

Slow Regex Code

 
 
brad
Guest
Posts: n/a
 
      06-08-2008
Still learning C++. I'm writing some regex using boost. It works great.
Only thing is... this code seems slow to me compared to equivelent Perl
and Python. I'm sure I'm doing something incorrect. Any tips?

#include <boost/regex.hpp>
#include <iostream>

// g++ numbers.cpp -o numbers -I/usr/local/include/boost-1_35
/usr/local/lib/libboost_regex-gcc41-mt-s.a
// g++ numbers.cpp -o numbers.exe
-Ic://Boost/include/boost-1_35://Boost/lib/libboost_regex-mgw34-mt-s.lib

void number_search(const std::string& portion)
{

static const boost::regex Numbers("\\b\\d{9}\\b");
static const boost::regex& rNumbers = Numbers;
boost::smatch matches;

std::string::const_iterator Start = portion.begin();
std::string::const_iterator End = portion.end();

while (boost::regex_search(Start, End, matches, rNumbers))
{
std::cout << matches.str() << std::endl;
Start = matches[0].second;
}
}

int main ()
{
std::string portion;
while (std::getline(std::cin, portion))
{
number_search(portion);
}
return 0;
}
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      06-09-2008
On Jun 8, 6:32 pm, brad <(E-Mail Removed)> wrote:
> Still learning C++. I'm writing some regex using boost. It
> works great. Only thing is... this code seems slow to me
> compared to equivelent Perl and Python.


Seems slow, or is measurably slower. There are two
possibilities:

1. it only seems slower, because the rest of the code is
significantly faster, or

2. it really is slower, because perl and python can compile it
into some sort of efficient byte code, since they already
have an "execution" machine for such byte code loaded.

Note that pure (non-extended) regular expressions can be made to
run considerably faster, since they can be converted to a pure
DFA. My own regular expression class does this. For most
purposes, however, boost:regex will be fast enough, and worth
the added flexibility. (My own regular expression class was
designed for a very specific use. Where it doesn't need the
extensions, but it does need some additional features which
aren't in Boost. For most general use, boost::regex is
preferable.)

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
 
Juha Nieminen
Guest
Posts: n/a
 
      06-09-2008
brad wrote:
> // g++ numbers.cpp -o numbers -I/usr/local/include/boost-1_35
> /usr/local/lib/libboost_regex-gcc41-mt-s.a
> // g++ numbers.cpp -o numbers.exe
> -Ic://Boost/include/boost-1_35://Boost/lib/libboost_regex-mgw34-mt-s.lib


For starters, you could try adding some optimization flags, such as
-O3 and -march=<your architecture> (eg. -march=pentium4).

(No, I don't know if that will make the regexp matching faster, but it
doesn't hurt to try.)
 
Reply With Quote
 
Roland Pibinger
Guest
Posts: n/a
 
      06-09-2008
On Sun, 08 Jun 2008 12:32:30 -0400, brad <(E-Mail Removed)> wrote:
>I'm writing some regex using boost. It works great.
>Only thing is... this code seems slow to me compared to equivelent Perl
>and Python. I'm sure I'm doing something incorrect. Any tips?


Try PCRE.



--
Roland Pibinger
"The best software is simple, elegant, and full of drama" - Grady Booch
 
Reply With Quote
 
Mirco Wahab
Guest
Posts: n/a
 
      06-09-2008
brad wrote:
> Still learning C++. I'm writing some regex using boost. It works great.
> Only thing is... this code seems slow to me compared to equivelent Perl
> and Python. I'm sure I'm doing something incorrect. Any tips?


It's not necessarily slower. But most probably. This caught my attention,
so I did some tests. Your code mainly messes around with the
initialization stuff within the function. This has nothing to
do w/boost regex.

I modified your code to do the following:

- slurp (read-into-buffer) a >120MB text file (actually,
it's the Nietzsche full text, 8 times copied
- find all "free" numbers >= 10 (that have 2 digits and
word boundaries on the left & right sides)
- show the total count of these numbers
- do the same in Perl.

The results (multicore results are "single-threaded"):

[Windows XP-32, Athlon-64/3200+,@2290MHz]
- Visual Studio 2008 + Boost 1.35.0 9.3 sec
- Perl 5.10 (Active-) 10.4 sec

[Linux 2.6.23, Pentium4,@2660MHz]
- gcc 4.3, -O2, Boost 1.33.1 13.2 sec
- Perl 5.8.8 8.2 sec

[Linux 2.6.23, Core2/Q6600,@3240MHz]
- gcc 4.3, -O2, Boost 1.33.1 6.3 sec
- Perl 5.8.8 (i586, use64bitint=undef) 3.2 sec

[Linux 2.6.24, Core2/Q9300,@3338MHz]
- gcc 4.3, -O2, Boost 1.34.1 'std::runtime_error' (??)
- Perl 5.10 (i586, use64bitint=undef) 10.4 sec

The latter system is not installed completely
(it's a test w/SuSE 11 Release Candidate),
so the results may get better soon there


Code, C++:
==>
#include <boost/regex.hpp>
#include <fstream>
#include <iostream>

int number_count(const char*block, size_t len)
{
boost::match_flag_type flags = boost::match_default;
boost::regex reg("\\b\\d{2,}\\b");
boost::cmatch m;

const char *from = block, *to = block+len;
int n = 0;
while( boost::regex_search(from, to, m, reg, flags) ) {
from = m[0].second, ++n;
}
return n;
}

int main ()
{
std::ifstream in("nietzsche8.txt"); // this is a 112 MB file,
// it's 8 x the Nietzsche
if(in) { // fulltext in plain ASCII
in.seekg(0, std::ios::end); // get to EOF
unsigned int len = in.tellg(); // read file pointer
in.seekg(0, std::ios::beg); // back to pos 0

char *block = new char [len+1]; // don't be stingy
in.read(block, len); // slurp the file
int n = number_count(block, len); // process data
std::cout << "The text (" << len/1024 << "KB) has "
<< n << " numbers >= 10!" << std::endl;
delete [] block; // play fair
}
return 0;
}
<==

Code, Perl:

==>
open my $fh, '<', 'nietzsche8.txt' or die "what? $!";
my $block;
do { local $/; $block = <$fh> };
close $fh;

my $n;
++$n while $block =~ /\b\d{2,}\b/g; # process data
print "The text (" . int(length($block)/1024) ."KB) has $n numbers >= 10!\n";
<==

Regards

Mirco
 
Reply With Quote
 
peter koch
Guest
Posts: n/a
 
      06-09-2008
On 8 Jun., 18:32, brad <(E-Mail Removed)> wrote:
> Still learning C++. I'm writing some regex using boost. It works great.
> Only thing is... this code seems slow to me compared to equivelent Perl
> and Python. I'm sure I'm doing something incorrect. Any tips?
>
> #include <boost/regex.hpp>
> #include <iostream>
>
> // g++ numbers.cpp -o numbers -I/usr/local/include/boost-1_35
> /usr/local/lib/libboost_regex-gcc41-mt-s.a
> // g++ numbers.cpp -o numbers.exe
> -Ic://Boost/include/boost-1_35://Boost/lib/libboost_regex-mgw34-mt-s.lib
>
> void number_search(const std::string& portion)
> * *{
>
> * * *static const boost::regex Numbers("\\b\\d{9}\\b");
> * * *static const boost::regex& rNumbers = Numbers;
> * * *boost::smatch matches;
>
> * * *std::string::const_iterator Start = portion.begin();
> * * *std::string::const_iterator End = portion.end();
>
> * * *while (boost::regex_search(Start, End, matches, rNumbers))
> * * * *{
> * * * *std::cout << matches.str() << std::endl;
> * * * *Start = matches[0].second;
> * * * *}
> * *}
>
> int main ()
> * *{
> * *std::string portion;
> * *while (std::getline(std::cin, portion))
> * * * *{
> * * * *number_search(portion);
> * * * *}
> * *return 0;
> * *}


As others have pointed out, there are probably two factors here:

- you might not be optimising your code. This can easily cause a
factor of 5-10.
- you might be measuring other parts of the library. I/O is the
obvious answer, and if you are using Microsofts newer C++ compilers
you might also be caught by the secure stl-code that is only disabled
when you add a special define to your build.

I would not expect this kind of code to be fast compared to e.g. Perl.
Perl is sort of built with regex in mind, and that part probably is
heavily optimised - maybe even written (partly) in assembly.

/Peter
 
Reply With Quote
 
Mirco Wahab
Guest
Posts: n/a
 
      06-10-2008
Razii wrote:
> On Mon, 9 Jun 2008 14:36:52 -0700 (PDT), peter koch
> <(E-Mail Removed)> wrote:
>> Perl is sort of built with regex in mind, and that part probably is
>> heavily optimised - maybe even written (partly) in assembly.

>
> Perl regex apparently is much slower than Tcl.


This is like saying: a rocket is much faster than an
airplaine. It is true sometimes but means nothing.

From my own experience, P5-REs are much more ver-
satile compared to TCL-RE (P5-REs are not 'regular'
anymore) and in the hands of an experienced pro-
grammer, this difference (which might be notable some-
times if many alternations are involved) approaches zero.

For example - there used to be an algorithm oriented language
implementation comparision (http://shootout.alioth.debian.org)
where you may find all sorts of results. In a reverse-DNA dump
test (http://shootout.alioth.debian.org/gp...vcomp&lang=all)
Perl completes in 2 seconds, TCL in 11 seconds. In another Regex-
heavy test (http://shootout.alioth.debian.org/gp...xdna&lang=all),
TCL runs in 3.3 seconds, whereas the first (allowed) Perl
impelentation comes in in 12 seconds. But, using a more
Perl-like approach (not allowed in this contest), the Perl
program (Perl #3, Perl #6 on the bottom) will complete in
1.2 seconds.

Regards

Mirco
 
Reply With Quote
 
Mirco Wahab
Guest
Posts: n/a
 
      06-10-2008
Mirco Wahab wrote:

I modified the expression:

> ...
> boost::regex reg("\\b\\d{2,}\\b");
> ...


to:
...
boost::regex reg("\\b\\d\\d+\\b");
...

with tremendeous improvements:

> [Windows XP-32, Athlon-64/3200+,@2290MHz]
> - Visual Studio 2008 + Boost 1.35.0 9.3 sec
> - Perl 5.10 (Active-) 10.4 sec


[Windows XP(32bit), Athlon-64/3200+ @2290MHz]
Visual Studio 2008 + Boost 1.35.0 1.8 sec
Perl 5.10.003 (AP, use64bitint=undef) 9.5 sec

> [Linux 2.6.23, Pentium4,@2660MHz]
> - gcc 4.3, -O2, Boost 1.33.1 13.2 sec
> - Perl 5.8.8 8.2 sec


[Linux 2.6.23(32bit), Pentium4/NW @2660MHz]
gcc 4.3.1 -O2, Boost 1.33.1 1.2 sec (user)
Perl 5.8.8 (32bit, use64bitint=undef) 6.2 sec (user)

> [Linux 2.6.23, Core2/Q6600,@3240MHz]
> - gcc 4.3, -O2, Boost 1.33.1 6.3 sec
> - Perl 5.8.8 (i586, use64bitint=undef) 3.2 sec


[Linux 2.6.23(32bit), Core2/Q6600,@3240MHz]
gcc 4.3.1 -O2, Boost 1.33.1 0.55sec (user)
Perl 5.8.8 (32bit, use64bitint=undef) 2.4 sec (user)

> [Linux 2.6.24, Core2/Q9300,@3338MHz]
> - gcc 4.3, -O2, Boost 1.34.1 'std::runtime_error' (??)
> - Perl 5.10 (i586, use64bitint=undef) 10.4 sec


[Linux 2.6.25(32bit), Core2/Q9300,@3338MHz]
gcc 4.3.1, -O3, Boost 1.34.1 0.42sec (user)[*]
Perl 5.10.0 (32bit, use64bitint=undef) 4.0 sec (user)
[*] => after kernel update & gcc update,
g++ -O3 -c boostrg.cxx -o boostrg.o
works now


modified Code, C++:
==>
#include <boost/regex.hpp>
#include <fstream>
#include <iostream>


int number_count(const char *block, unsigned int len)
{
boost::match_flag_type flags = boost::match_default;
boost::regex reg("\\b\\d\\d+\\b");
boost::cmatch what;

const char *from = block, *to = block+len;
int n = 0;
while( boost::regex_search(from, to, what, reg, flags) ) {
from = what[0].second;
++n;
}
return n;
}

int main ()
{
std::ifstream in("nietzsche8.txt"); // this is a 112 MB file,
// it's 8 x the Nietzsche
if(in) { // fulltext in plain ASCII
in.seekg(0, std::ios::end); // get to EOF
unsigned int len = in.tellg(); // read file pointer
in.seekg(0, std::ios::beg); // back to pos 0

char *block = new char [len+1]; // don't be stingy
in.read(block, len); // slurp the file
int n = number_count(block, len); // process data
std::cout << "The text (" << len/1024 << "KB) has "
<< n << " numbers >= 10!" << std::endl;
delete [] block; // play fair
}
return 0;
}
<==

modified Code, Perl:
==>

open my $fh, '<', 'nietzsche8.txt' or die "what? $!";
my $block;
do { local $/; $block = <$fh> };
close $fh;

my $n;
++$n while $block =~ /\b\d\d+\b/g; # process data
print "The text (" . int(length($block)/1024) ."KB) has $n numbers >= 10!\n";

<==


At least for me, a very interesting difference.
Boost::Regex gives Perl a significant margin.

Regards

Mirco
 
Reply With Quote
 
Mirco Wahab
Guest
Posts: n/a
 
      06-10-2008
Razii wrote:
> How do you know that Tcl won't speed up and remain faster than Perl if
> it's allowed to split the regex at |


It may or it may not. But the difference
will most probably approach zero, as I
tried to say.

Regards

Mirco
 
Reply With Quote
 
brad
Guest
Posts: n/a
 
      06-10-2008
Mirco Wahab wrote:
> Mirco Wahab wrote:
>
> I modified the expression:
>
>> ...
>> boost::regex reg("\\b\\d{2,}\\b");
>> ...

>
> to:
> ...
> boost::regex reg("\\b\\d\\d+\\b");


Wow... I changed my RE to use \\d nine times instead of \\d{9} and it's
now twice as fast. Amazing. I never would have thought of something as
simple as this. Thanks for the idea.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: slow slow slow! Expert lino fitter Computer Support 5 12-12-2008 04:00 PM
Re: slow slow slow! chuckcar Computer Support 0 12-10-2008 11:25 PM
Re: slow slow slow! Beauregard T. Shagnasty Computer Support 2 12-10-2008 09:03 PM
Re: slow slow slow! Expert lino fitter Computer Support 0 12-10-2008 02:33 PM
How make regex that means "contains regex#1 but NOT regex#2" ?? seberino@spawar.navy.mil Python 3 07-01-2008 03:06 PM



Advertisments