Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regular expression matching can be simple and fast (2007)

swtch.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Regular expression matching can be simple and fast (2007)

#11

Post by chx »

> As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.)

It really needs to be noted how NP-complete and an algorithm efficient in practice have nothing to do with each other. If an algorithm takes C * 1.000...eighty zeroes...1^n time it is exponential but for any n you will encounter in real life the time it takes will be indistinguishable from C.

Re: Regular expression matching can be simple and fast (2007)

#12

Post by cies »

adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

Or write a parser!

In most cases the parser will not be shorter (code) than the regex, but it will most certainly be simpler (cognitively; it's hard to understand all that regexes do, they're close to magic) and more testable (you can test the parts of the parser, like the number parser or the string parser, individually), and often faster too.

Re: Regular expression matching can be simple and fast (2007)

#13

Post by cies »

cies wrote: post #12
adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

Or write a parser! In most cases the parser will not be shorter (code) than the regex, but it will most certainly be simpler (cognitively; it's hard to understand all that regexes do, they're close to magic) and more testable (you can test the parts of the parser, like the number parser or the string parser, individually), and often faster too.

https://stackoverflow.com/questions/11905506/regular-express...

Re: Regular expression matching can be simple and fast (2007)

#14

Post by bubblyworld »

chx wrote: post #11

> As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.) It really needs to be noted how NP-complete and an algorithm efficie…

There's a fun list of problems like this here: https://cstheory.stackexchange.com/questions/6660/polynomial...

On the other hand, it's remarkable that so many algorithms _do_ have reasonable constants/exponents. So the concept works pretty well.

Re: Regular expression matching can be simple and fast (2007)

#15

Post by ablob »

banish-m4 wrote: post #6
kqr wrote: post #5

Earlier quoted context omitted.

And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.

NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.

There exist algorithms that deal with state blow-up. In fact, these algorithms project any given DFA into an equivalent DFA of minimal size - guaranteeing a minimal automaton for the language that is accepted by it. In essence, you build equivalence classes between states with respect to possible paths they can take into other equivalence classes for further input. State machines for LR-Grammars are vastly more complex in comparison to NFA automata, so for most (if not all) applications, a computer that can deal with LR-Grammars will be able to handle a NFA conversion with a subsequent minimization.

Re: Regular expression matching can be simple and fast (2007)

#16

Post by hyperpape »

adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

There's pretty wide variety in the performance of regular expressions between different languages, and efficient implementations will often recognize when your regular expression has a literal suffix/prefix, and optimize accordingly.

That doesn't help you if you're stuck using a library that doesn't perform those optimizations, but it means you need to be careful about importing your assumptions about regex performance from one language to another.

See also: https://github.com/burntSushi/rebar

Re: Regular expression matching can be simple and fast (2007)

#17

Post by zeckalpha »

adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

Re: Regular expression matching can be simple and fast (2007)

#18

Post by adrianN »

zeckalpha wrote: post #17
adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

It’s re2…

Re: Regular expression matching can be simple and fast (2007)

#19

Post by mikhailfranco »

banish-m4 wrote: post #6
kqr wrote: post #5

Earlier quoted context omitted.

And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.

NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.

It is possible to implement NFAs directly, in parallel:

https://github.com/mike-french/myrex

Just fan-out messages to all downstream states. Let a fair runtime system evaluate all progress, then tally results along all paths, for example:

https://github.com/mike-french/myrex?tab=readme-ov-file#exec...

The approach can also be adapted to captures and their many, many possible ambiguities. There is an example that generalizes a highly ambiguous match given in Cox: regex (a?){m}(a*){m} against a string of a{m}. The case m=9 gives 864k possible solutions (traversals), you may optionally ask for all of them to be returned:

https://github.com/mike-french/myrex?tab=readme-ov-file#ambi...

The processes share nothing, all state is in the messages, so a single network can process multiple input strings simultaneously. It can also generate Monte-Carlo strings that match the regex, and those may also proceed simultaneously.

Re: Regular expression matching can be simple and fast (2007)

#20

Post by burntsushi »

zeckalpha wrote: post #17
adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

The GP doesn't really provide enough details to tell the difference between 1) the programmer did something wrong, or 2) the regex engine is missing optimizations or 3) the GP has a use case that is actually difficult to optimize for in the generality of the regex engine. Any one of these 3 things could be true. It's possible more than one is true simultaneously!

> a linear find should be equivalent to a well implemented regex search for a specific string of characters

This is only true theoretically. If your regex engine is just a DFA scan that does char-at-a-time matching, then any "well implemented" substring search algorithm is going to blow it out of the water because it likely uses SIMD. Of course, many regex engines (including RE2), detect literals in the regex and use SIMD to scan for it. So while "DFA scan that does char-a-time matching" is a fine semantic model to have (to a first approximation) for a finite automata based regex engine, the model breaks down pretty quickly for reasoning about performance in general.

Post reply on HN