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

Regexes: The Bad, the Better, and the Best

loggly.com

Post reply on HN
Print view View original

11–20 of 37 posts

Re: Regexes: The Bad, the Better, and the Best

#11

Post by Mithaldu »

tptacek wrote: post #10
Mithaldu wrote: post #9

Earlier quoted context omitted.

That is actually a damn good question. I didn't decide on the word by way or a rational chain of logic, but merely by having hindbrain pattern matching trigger on your behavior, based on what i've seen called that on other forums, and what i've seen you doing on here from time to time. If i had to put it in words, it would probably be something like "tell other people how to use HN without contributing significantly…

I'm doing a lot of things at once. I'm fixing a buggy register allocator, and I'm not that smart, so I can do real work for about 15 minutes before my brain overheats. I bounce to the HN front page: there's a story about regexes, and a recent trend of stories about how there are alternatives to standard regex libraries. I think, maybe this will be one of those stories. Click. Nope, it isn't. I wonder, did anyone writ…

> Thanks for motivating me to improve it.

Cheers, that's all i'm hoping for. :)

Re: Regexes: The Bad, the Better, and the Best

#12

Post by taco_emoji »

> In General, the Longer Regex Is the Better Regex

I'd rather word this as "more specific is better". Like say for a U.S. phone number (minus area code for simplicity),

    \d{3}-?\d{4}
is better than

    .*-?.*
because it's more specific.

"Longer is better" is only useful for helping identify which regex is better, not for helping write better regexes.

Re: Regexes: The Bad, the Better, and the Best

#13

Post by edwintorok »

"Awk and grep use the Thompson NFA algorithm which is in fact significantly faster in almost every way but supports a more limited set of features."

AFAIK the only feature of regexes that require backtracking are back-references, as long as your regex doesn't use it why doesn't PCRE switch to the more efficient algorithm, and use the backtracking algorithm only if you actually need the feature that requires backtracking?

Re: Regexes: The Bad, the Better, and the Best

#15

Post by SerpentJoe »

edwintorok wrote: post #13

"Awk and grep use the Thompson NFA algorithm which is in fact significantly faster in almost every way but supports a more limited set of features." AFAIK the only feature of regexes that require backtracking are back-references, as long as your regex doesn't use it why doesn't PCRE switch to the more efficient algorithm, and use the backtracking algorithm only if you actually need the feature that requires backtrack…

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.

Re: Regexes: The Bad, the Better, and the Best

#16

Post by pimlottc »

Where "Best" = "Most performant". Of course, there's other ways to judge a regex - readability, specificity, robustness...

In most places I used regexes, efficiency is the least of my concerns, though for a company whose product is focused around parsing massive amounts of logs, focusing on performance does make sense.

Re: Regexes: The Bad, the Better, and the Best

#17

Post by leeoniya »

taco_emoji wrote: post #12

> In General, the Longer Regex Is the Better Regex I'd rather word this as "more specific is better". Like say for a U.S. phone number (minus area code for simplicity), \d{3}-?\d{4} is better than .*-?.* because it's more specific. "Longer is better" is only useful for helping identify which regex is better, not for helping write better regexes.

and [0-9] is more specific than \d

"In most flavors that support Unicode, \d includes all digits from all scripts." [1]

EDIT: But I guess for the majority of use cases it doesn't matter [2] since PCRE is the norm almost everywhere.

[1] http://www.regular-expressions.info/shorthand.html

[2] "Notable exceptions are Java, JavaScript, and PCRE. These Unicode flavors match only ASCII digits with \d"

Re: Regexes: The Bad, the Better, and the Best

#18

Post by edwintorok »

SerpentJoe wrote: post #15
edwintorok wrote: post #13

"Awk and grep use the Thompson NFA algorithm which is in fact significantly faster in almost every way but supports a more limited set of features." AFAIK the only feature of regexes that require backtracking are back-references, as long as your regex doesn't use it why doesn't PCRE switch to the more efficient algorithm, and use the backtracking algorithm only if you actually need the feature that requires backtrack…

Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.

that can be compiled to a state machine where a decision to switch states is taken based on current character only, and when all input is consumed you are either in an accepting or rejecting state. In your case I think it only needs 2 states: state 0 moves to state 1 when it sees an A, and state 1 moves to state 0 when it sees either A or B. For your string it'll be in state 0 when it sees a B and thus rejects it.

Re: Regexes: The Bad, the Better, and the Best

#19

Post by oftenwrong »

taco_emoji wrote: post #12

> In General, the Longer Regex Is the Better Regex I'd rather word this as "more specific is better". Like say for a U.S. phone number (minus area code for simplicity), \d{3}-?\d{4} is better than .*-?.* because it's more specific. "Longer is better" is only useful for helping identify which regex is better, not for helping write better regexes.

In many environments,

   [0-9]{3}-?[0-9]{4}
is even more specific (and faster) because \d would match other digit characters outside of [0-9].

Re: Regexes: The Bad, the Better, and the Best

#20

Post by carapace »

Okay but think:

If you are searching a very large file for a very few occurrences of the expected match then this optimization is not so bad.

If you are running line-by-line through a very large log file to extract just those two pieces of information per line, then throw away the first N characters in each line (where N is the hopefully-constant length of your timestamps plus that space char) and start the regex engine at the beginning of the expected match. Then it doesn't have to waste any time passing over those chars.

Even if the exact details above aren't quite right the principal is (and is well-known): Avoid premature optimization! (And the corollary: Measure it. Profile your code, don't guess, you're probably wrong.)

Post reply on HN