Hacker News Reader

Hacker News

Comment by austincheney | Hacker News Reader

Parent Full thread

austincheney

Isn't this the very kind of thing Regular Expressions were created to solve?

* Remove spaces - myString.replace(/\u0020+/g, "");

* Remove common line terminators - myString.replace(/(\r|\n)+/g, "");

* Remove all white space - myString.replace(/\s+/g, "");

View on HN

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

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

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.

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/li...

Awesome, thank you!

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

Time to break out the HDL then...

http://www.braketlogic.com/

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.

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/

I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)

Indeed. Rust's regex engine is descended from RE2. rsc's blog posts were my guide when I first wrote it.

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.

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

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.

I am responding to your claim. I'm saying that not all regex implementations are created equal. Some can be just as fast as what you might write by hand.

Regular expressions can be Unicode aware, right? You should be able to use a shortcut specifier that's equivalent of calling something like IsWhitespace.

Yes. It is people's ability to write good UNICODE regular expressions that is at issue.

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.

That's not at all true. See: https://news.ycombinator.com/item?id=13448318

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).

Regular expressions were created to do this, but your general string replace function with your general regular expression library might not be the fastest way, which is what this post is about.

Reply on news.ycombinator.com