7 ms·

the post is not so much about most convenient way to remove spaces, but about efficiency of such an operation.

by SonicSoul 10y ago

austincheney 10y ago
Is regex execution considered efficient? I have always been impressed with its speed.
- throwanem 10y ago
  Simple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential with a large exponent.
  - deleted 10y ago
    [deleted]
  - pjscott 10y ago
    If you want to guarantee that this will never happen, RE2 and similar regular expression engines are guaranteed to run in O(n) time, where n is the length of the target string. https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)
    - burntsushi 10y ago
      Indeed. Rust's regex engine is descended from RE2. rsc's blog posts were my guide when I first wrote it.
- stefs 10y ago
  i'm sure using a fully featured regular expression engine would be several magnitudes slower than a handcrafted 128bit routine. those engines too trade power for speed.
  - burntsushi 10y ago
    That's not at all true. See: https://news.ycombinator.com/item?id=13448318 https://news.ycombinator.com/item?id=13448318
- Sharlin 10y ago
  Even if the regex library compiled the expression down to the very simplest state machine possible, it would still be at most as efficient as the first handwritten code in the article, handling one byte at a time. I'm fairly sure no regex engine in existence is able to detect "simple enough" regexes and optimize them into code that handles 64 or 128 bit blocks at a time.
  - anowell 10y ago
    You might checkout the literal optimizations that ripgrep does. IIRC, the underlying regex lib is optimizing a few classes of "simple" regexes with SIMD to achieve better perf than the first handwritten code in that article. http://blog.burntsushi.net/ripgrep/#literal-optimizations http://blog.burntsushi.net/ripgrep/#literal-optimizations
  - GregBuchholz 10y ago
    Time to break out the HDL then... http://www.braketlogic.com/ http://www.braketlogic.com/
  - burntsushi 10y ago
    They exist. In fact, if you hand Rust's regex engine the pattern ` |\r|\n`, then it will compile it down to a very simple alternation of three literal bytes. It will never touch the actual regex engine at all. Once the regex engine knows its a simple alternation of three bytes, it will actually use a variant of memchr called memchr3[1], which looks almost exactly like the OP's "portable" approach. So it's not quite the fastest possible because it doesn't use SIMD, but this is mostly because we don't have good explicit SIMD support on stable Rust yet. Once we do, this immediately becomes a strong candidate to optimize to something like the OP's fastest version (and also probably generalizing to AVX2 instructions as well). N.B. My sibling comment linked to my blog post on ripgrep, which uses Rust's regex engine. ;-) [1] - https://github.com/BurntSushi/rust-memchr/blob/master/src/lib.rs#L347 https://github.com/BurntSushi/rust-memchr/blob/master/src/li...
    - Sharlin 10y ago
      Awesome, thank you!
- UnoriginalGuy 10y ago
  For this? No, it is not considered performant. Regular Expressions are efficient in that one line of code can save you writing hundreds of lines. But they're normally slower (even pre-compiled) than thoughtful hand written code simply due to the overhead. Generally the simpler the objective the worse Regular Expressions are. They're better for complex operations. Plus people write regular expressions REALLY poorly, doubly so for UNICODE. Ideally you should use the standard library for this. For example C# has Char.IsWhiteSpace() which supports tons of UNICODE whitespace and can be updated with whitespace which doesn't even exist today.
  - MichaelGG 10y ago
    Regular expressions can be Unicode aware, right? You should be able to use a shortcut specifier that's equivalent of calling something like IsWhitespace.
    - UnoriginalGuy 10y ago
      Yes. It is people's ability to write good UNICODE regular expressions that is at issue.
  - burntsushi 10y ago
    This isn't true. Regular expressions can be fast even when supporting Unicode by building finite state machines that recognize UTF-8 directly. This particular benchmark explains a bit: http://blog.burntsushi.net/ripgrep/#linux-unicode-word http://blog.burntsushi.net/ripgrep/#linux-unicode-word
    - UnoriginalGuy 10y ago
      What isn't true? I never said that regular expressions cannot support UNICODE fast. I said that regular expressions are slower than code due to the overhead in all scenarios. You're responding to a point never made.
      - burntsushi 10y ago
- jnordwick 10y ago
  You wouldn't be using a finite state recognize (regular expression) but a finite state transducer (regular expression that emits characters instead of just recognizing).

the post is not so much about most convenient way to remove spaces, but about efficiency of such an operation.

austincheney 10y ago

Is regex execution considered efficient? I have always been impressed with its speed.

throwanem 10y ago
Simple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential with a large exponent.
- deleted 10y ago
  [deleted]
- pjscott 10y ago
  If you want to guarantee that this will never happen, RE2 and similar regular expression engines are guaranteed to run in O(n) time, where n is the length of the target string. https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)
  - burntsushi 10y ago
    Indeed. Rust's regex engine is descended from RE2. rsc's blog posts were my guide when I first wrote it.
stefs 10y ago
i'm sure using a fully featured regular expression engine would be several magnitudes slower than a handcrafted 128bit routine. those engines too trade power for speed.
- burntsushi 10y ago
  That's not at all true. See: https://news.ycombinator.com/item?id=13448318 https://news.ycombinator.com/item?id=13448318
Sharlin 10y ago
Even if the regex library compiled the expression down to the very simplest state machine possible, it would still be at most as efficient as the first handwritten code in the article, handling one byte at a time. I'm fairly sure no regex engine in existence is able to detect "simple enough" regexes and optimize them into code that handles 64 or 128 bit blocks at a time.
- anowell 10y ago
  You might checkout the literal optimizations that ripgrep does. IIRC, the underlying regex lib is optimizing a few classes of "simple" regexes with SIMD to achieve better perf than the first handwritten code in that article. http://blog.burntsushi.net/ripgrep/#literal-optimizations http://blog.burntsushi.net/ripgrep/#literal-optimizations
- GregBuchholz 10y ago
  Time to break out the HDL then... http://www.braketlogic.com/ http://www.braketlogic.com/
- burntsushi 10y ago
  They exist. In fact, if you hand Rust's regex engine the pattern ` |\r|\n`, then it will compile it down to a very simple alternation of three literal bytes. It will never touch the actual regex engine at all. Once the regex engine knows its a simple alternation of three bytes, it will actually use a variant of memchr called memchr3[1], which looks almost exactly like the OP's "portable" approach. So it's not quite the fastest possible because it doesn't use SIMD, but this is mostly because we don't have good explicit SIMD support on stable Rust yet. Once we do, this immediately becomes a strong candidate to optimize to something like the OP's fastest version (and also probably generalizing to AVX2 instructions as well). N.B. My sibling comment linked to my blog post on ripgrep, which uses Rust's regex engine. ;-) [1] - https://github.com/BurntSushi/rust-memchr/blob/master/src/lib.rs#L347 https://github.com/BurntSushi/rust-memchr/blob/master/src/li...
  - Sharlin 10y ago
    Awesome, thank you!
UnoriginalGuy 10y ago
For this? No, it is not considered performant. Regular Expressions are efficient in that one line of code can save you writing hundreds of lines. But they're normally slower (even pre-compiled) than thoughtful hand written code simply due to the overhead. Generally the simpler the objective the worse Regular Expressions are. They're better for complex operations. Plus people write regular expressions REALLY poorly, doubly so for UNICODE. Ideally you should use the standard library for this. For example C# has Char.IsWhiteSpace() which supports tons of UNICODE whitespace and can be updated with whitespace which doesn't even exist today.
- MichaelGG 10y ago
  Regular expressions can be Unicode aware, right? You should be able to use a shortcut specifier that's equivalent of calling something like IsWhitespace.
  - UnoriginalGuy 10y ago
    Yes. It is people's ability to write good UNICODE regular expressions that is at issue.
- burntsushi 10y ago
  This isn't true. Regular expressions can be fast even when supporting Unicode by building finite state machines that recognize UTF-8 directly. This particular benchmark explains a bit: http://blog.burntsushi.net/ripgrep/#linux-unicode-word http://blog.burntsushi.net/ripgrep/#linux-unicode-word
  - UnoriginalGuy 10y ago
    What isn't true? I never said that regular expressions cannot support UNICODE fast. I said that regular expressions are slower than code due to the overhead in all scenarios. You're responding to a point never made.
    - burntsushi 10y ago
jnordwick 10y ago
You wouldn't be using a finite state recognize (regular expression) but a finite state transducer (regular expression that emits characters instead of just recognizing).