4 ms·

About 17 years ago, I had to solve the same problem, but since I used regexes, I had two problems at the end of it - memory usage and performance. /* RFC239

by gopalv 5y ago

About 17 years ago, I had to solve the same problem, but since I used regexes, I had two problems at the end of it - memory usage and performance. /* RFC2396 : Appendix B As described in Section 4.3, the generic URI syntax is not sufficient to disambiguate the components of some forms of URI. Since the "greedy algorithm" described in that section is identical to the disambiguation method used by POSIX regular expressions, it is natural and commonplace to use a regular expression for parsing ^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))? 12 3 4 5 6 7 8 9 (Modified to support mailto: syntax as well) */ But at least it wasn't the problem I started with.

the-dude 5y ago
Regular Expressions: Now You Have Two Problems https://blog.codinghorror.com/regular-expressions-now-you-have-two-problems/ https://blog.codinghorror.com/regular-expressions-now-you-ha...
SavantIdiot 5y ago
That is a nightmare of a regex, IETF be damned. Splitting regexess up into smaller chunks helps readability, support, memory usage -and- performance. I suspect that example was provided as a definition and not actually intended to be implemented. Although there are better forms for representing construction, like BNF.
- nerdponx 5y ago
  How can you split this up into chunks? I would love "composable regex" but I'm not aware of such a thing in the wild.
  - SavantIdiot 5y ago
    TL;DR: Naive string splitting on reserved/fragment characters followed by expected string comparisons in a search tree for known tokens (e.g., http, https, ftp, rtsp, mail). It is a tradeoff between what you are asking the regex engine to do and what you can code in a small filter. A regex engine is a general-purpose tokenizer, which while having been optimized over the multiple decades since they were proposed will never be as fast as a parser that uses knowledge of grammar. You can tokenize and parse simultaneous which IMHO is a more future-thinking strategy from a support standpoint. I suspect the person who rote Appendix B was favoring compactness: https://tools.ietf.org/html/rfc2396#appendix-B https://tools.ietf.org/html/rfc2396#appendix-B I've encountered regex's this nasty in the wild, and while they may be compact, try going back and debugging this in 6 months, a year, two years, etc. Even harder if you didn't write it. There could be a page of comments explaining it (like the entire RFC). OR, the programmer could have been a bit more "naive", which in many cases pays off because it forces more verbosity which leaves clues if the comments suck. Putting aside the mental gymnastics needed to identify if these sub expressions collide, in terms of performance, you can immediately see that almost the entire regex is optional: almost every level-1 subexpression is optional (except /([^?#])/), including the final match all .!. Regex's aren't even, but huge ones like this with multiple rewinds, compound subexpressions, and optional subexpressions can severely degrade performance. Yes, I'm ranting, because I've had to fix the consequences of opaque code like this in the wild. :)
    - nerdponx 5y ago
      Ah, the answer is to just use less regex :) I do sometimes build regexes by concatenating strings, or using the "verbose" mode in Python which lets you add free whitespace and comments. Maybe my mind has just been poisoned by too much regex, but I didn't think the example was that bad...

by gopalv 5y ago

the-dude 5y ago

Regular Expressions: Now You Have Two Problems https://blog.codinghorror.com/regular-expressions-now-you-have-two-problems/ https://blog.codinghorror.com/regular-expressions-now-you-ha...

SavantIdiot 5y ago

That is a nightmare of a regex, IETF be damned. Splitting regexess up into smaller chunks helps readability, support, memory usage -and- performance. I suspect that example was provided as a definition and not actually intended to be implemented. Although there are better forms for representing construction, like BNF.

nerdponx 5y ago
How can you split this up into chunks? I would love "composable regex" but I'm not aware of such a thing in the wild.
- SavantIdiot 5y ago
  TL;DR: Naive string splitting on reserved/fragment characters followed by expected string comparisons in a search tree for known tokens (e.g., http, https, ftp, rtsp, mail). It is a tradeoff between what you are asking the regex engine to do and what you can code in a small filter. A regex engine is a general-purpose tokenizer, which while having been optimized over the multiple decades since they were proposed will never be as fast as a parser that uses knowledge of grammar. You can tokenize and parse simultaneous which IMHO is a more future-thinking strategy from a support standpoint. I suspect the person who rote Appendix B was favoring compactness: https://tools.ietf.org/html/rfc2396#appendix-B https://tools.ietf.org/html/rfc2396#appendix-B I've encountered regex's this nasty in the wild, and while they may be compact, try going back and debugging this in 6 months, a year, two years, etc. Even harder if you didn't write it. There could be a page of comments explaining it (like the entire RFC). OR, the programmer could have been a bit more "naive", which in many cases pays off because it forces more verbosity which leaves clues if the comments suck. Putting aside the mental gymnastics needed to identify if these sub expressions collide, in terms of performance, you can immediately see that almost the entire regex is optional: almost every level-1 subexpression is optional (except /([^?#])/), including the final match all .!. Regex's aren't even, but huge ones like this with multiple rewinds, compound subexpressions, and optional subexpressions can severely degrade performance. Yes, I'm ranting, because I've had to fix the consequences of opaque code like this in the wild. :)
  - nerdponx 5y ago
    Ah, the answer is to just use less regex :) I do sometimes build regexes by concatenating strings, or using the "verbose" mode in Python which lets you add free whitespace and comments. Maybe my mind has just been poisoned by too much regex, but I didn't think the example was that bad...