No, it is specific thing for processing strings.
It is performance of algorithm, language play second role here.

@Vitaliy_Kiselev

Are you thinking of building a search engine from scratch?

Seriously, nobody* does full-pattern matches. Web servers employ an indexing method like Swish-E which reduce the stack of text Grep needs to look through by n(-100).

Then, of course, PV's current implementation of Google's Big Table database and search algorythms is working well, thanks. It's making free use of the Google Dance of indexing the world's data while we sleep.

*Hackers probably make use of fast pattern-matching.

@stonebat No, only that PV's search box now does a Google site search. I've worked in companies and departments where if you want to find out what your own job is it's lots easier to google the department's website than to use your in-house search engine!

There are a few downsides to using Google search in house but it's free and a bit of a no-brainer for most mortals.

Seriously, nobody* does full-pattern matches.

Hackers probably make use of fast pattern-matching.

[Edit: silly me] As I type I'm watching Saturday Night's Antenne 2 Week-end TV news where big corporations are using fast pattern matching to search all employees' emails. Talk about serendipity!

Come to think of it, Echelon probably does something pretty similar :-(

Seriously, nobody* does full-pattern matches. Web servers employ an indexing method like Swish-E which reduce the stack of text Grep needs to look through by n(-100).

I fail to understand that you mean and how web servers and grep are related here.

Article and chart is about regular expression performance, and believe me, tons of them are used in almost every web framework, CMS, forum, etc.

I have installed lot of web search engines from simple Open Source like Joomla and Drupal through to enterprise itranet/internet CMS using MySource Matrix and Squiz. All of them rely heavily on indexing and use grep-derived libraries, despite their perceived slowness, to search through normalised (therefore indexed)SQL tables.

No one it talking about search engines here.

Again, it is just article about regular expressions and application and scripts use ton of this, believe me, I saw many on them inside.

As for site search engines, most of them are just horrible from my personal expirience.

@goanna

I have big trouble understanding all this search engine stuff you constantly bring up.

I did not mentioned any search engines, and did not even thinked about it, they are not related here.

Can you please explain how you'd like to make use of the faster algorithms? Do you mean something other than searching per se? A smarter image compression algorythm?

I do not like to "make use of the faster algorithms". I just found interesting article I'd like to share, so many people will understand why sometimes their PHP scripts struggle badly, it is especially the case for systems using on the fly formatting.

@balazer

It is wrong view. It is about how regular expressions are implemented.

It is also useful to understand that most formatters are made using regular expressions (that by itself is not fast, plus they in their turn have flaws in implementation as shown in paper), and not as state machines. This things you are using every day hundreds of times (but do not know about it).

The chart shows the time to match the regular expression a?^na^n against certain text n characters long using a few different matching algorithms. The whole point of the paper is that for this weird class of regular expression with certain text input, some of the algorithms are ridiculously slow compared to some other algorithms. It takes more than 10 seconds to match the regular expression against text 25 characters long, and the time grows exponentially with n. Think about that for a second. It would be impossible to match a regular expression against even a single page of text. The processing would never finish.

If these pathological regular expressions were common, Perl and Ruby and Python would have switched to one of the faster algorithms a long time ago. But these regular expressions are exceedingly uncommon, so it's just not that big of a deal. Once in a while you run into one of those pathological cases. It causes the processing to be ridiculously slow or to not finish at all, you find the problem, and then you rewrite the regular expression to avoid the problem.

The author's stance is that Perl should be able to detect and avoid the pathological cases, and he's certainly got a point there. But none of what he's talking about - absolutely none of it - generalizes to the performance of regular expression matching algorithms for anything but these weird pathological cases.

This from another article from link I provided in last post

Speed of searching for ABCDEFGHIJKLMNOPQRSTUVWXYZ$ in random text. (Mac Pro):

Speed of searching for and matching (\d{3}-|(\d{3}\)\s+)(\d{3}-\d{4}) in random text ending wtih (650) 253-0001. (Mac Pro) :

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

The benchmarks you just linked show the backtracking algorithm having better performance than finite state automata on most of that sampled real-world input.

LOL.

According to table most consistent result showed by RE2. With one of expressions giving almost 20x advantage compared to fastest backtracking (that performed good for others).

And author in first link specially mentioned that he used only short lines from big text.

Second link talk about longer text.

Small addition.

PCRE is also good implementation. And if you need to run matches for long texts, and also with certain regexps (mostly with many ORs as I understood it) it is always good to check FSA implementations.