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

Show HN: Nevod is easier and faster than RegExp

nevod.nezaboodka.com

Post reply on HN
Print view View original

61–70 of 82 posts

Re: Show HN: Nevod is easier and faster than RegExp

#61

Post by burntsushi »

ychetyrko wrote: post #48

First of all, thanks everyone for the valuable feedback, critics, suggestions, etc. Truly appreciate that! And thanks for patience to all people who are playing with the Nevod right now and getting errors. We have an unexpectedly high interest and number of visitors is very high in our playground. Meanwhile, it's a preview of the technology, please keep in mind. Let me clarify few things. The speed of Nevod is based…

> Nevod matches MULTIPLE patterns against document in ONE PASS.

Any non-backtracking regex implementation will do the same.

> So, at a RULE DECK of 1000 patterns, we got 300 times improvement comparing to RegExp.

There is no generic "regex." There are many implementations of regex. So which regex implementation are you comparing it with?

Re: Show HN: Nevod is easier and faster than RegExp

#62

Post by glangdale »

ychetyrko wrote: post #48

First of all, thanks everyone for the valuable feedback, critics, suggestions, etc. Truly appreciate that! And thanks for patience to all people who are playing with the Nevod right now and getting errors. We have an unexpectedly high interest and number of visitors is very high in our playground. Meanwhile, it's a preview of the technology, please keep in mind. Let me clarify few things. The speed of Nevod is based…

> 2. Nevod matches MULTIPLE patterns against document in ONE PASS. Patters/expressions are indexed by state machine and filtered effectively during matching.

This is a good idea. It's such a good idea that we did it in 2006, sold a company to Intel based around in in 2013 and open-sourced the resulting library (https://github.com/intel/hyperscan) in 2015.

All multi-pattern systems get a huge improvement over one-at-a-time regex. It would be embarrassing if they did not. Our rule of thumb for Hyperscan was that it should be about 5-10x faster than libpcre on single patterns and the gap should get progressively bigger.

I don't doubt that there is quite a bit of interesting work (entirely outside of regex - the word-based focus looks interesting) going on in this project, but the fact that you couldn't be bothered to Google around for a sensible baseline is not encouraging.

Also, which bit of your system do you think is novel enough to patent? You may find considerable prior art out there, which you don't really seem to be aware of based on how much emphasis you're placing on the not-entirely-novel idea of using a state machine.

Re: Show HN: Nevod is easier and faster than RegExp

#63

Post by glangdale »

Cu3PO42 wrote: post #27
jasode wrote: post #25

Like the other sibling comments mentioned, I too was confused about "100x faster than regex" and what the actual product was about. After digging around their website, I found this blog post which explains it better: https://blog.nezaboodka.com/post/2019/594-using-nevod-for-te... So my summary would be: 1) it works "faster" than regex in a specific scenario of treating text as entities in natural language . (E.g. hig…

That sounds very much like what Rust's RegEx engine does. I understand it extracts longer literals (when available) to find a starting point for where a match might be according to [1]. [1] https://blog.burntsushi.net/ripgrep/#literal-optimizations

This is not a new technique with the Rust regex engine. We had a considerably more comprehensive literal 'factoring' approach in Hyperscan about a decade earlier (which also satisfied a lifelong ambition of mine; specifically misusing the netflow algorithm in a graph for something).

The multiple literal implementation in that matcher is also a partial lift from Hyperscan's "Teddy" small group literal matcher (not salty about that as "burntsushi" has been very clear about inspiration). I do wish they'd pull in the rest of the algorithm at some point - the bits that allow merging of Teddy literals into buckets to reduce false positive rates...

Re: Show HN: Nevod is easier and faster than RegExp

#64

Post by glangdale »

It looks like there are some interesting things in this project beyond regex, but the way that it skates over the fact that there are already automata-based multiple pattern matchers is pretty rank.

When we started developing automata-based pattern matching s/w in 2006 - 2006! - we were well aware that it wasn't really a new thing. 12 years of work on Hyperscan (https://github.com/intel/hyperscan), 1 acquisition and 1 open source release later - as well as multiple other projects doing similar things (re2, Rust regex, Parabix, icgrep, Rosie Pattern Language, ...) has only added to this crowded field. All this has taught me many things, but the thing that I keep returning to is that "a lot of people apparently don't know about prior art, or assiduously pretend not to". It will be interesting to see what they try to patent.

Re: Show HN: Nevod is easier and faster than RegExp

#65

Post by theamk »

ilaksh wrote: post #60
ychetyrko wrote: post #48

First of all, thanks everyone for the valuable feedback, critics, suggestions, etc. Truly appreciate that! And thanks for patience to all people who are playing with the Nevod right now and getting errors. We have an unexpectedly high interest and number of visitors is very high in our playground. Meanwhile, it's a preview of the technology, please keep in mind. Let me clarify few things. The speed of Nevod is based…

I see a lot of criticism but not a lot of praise. For me creating something so comprehensive and also easy to use is an achievement. And in my opinion this is much better than Regex for most cases because of the ease of use and readability. I think the main pushback you are seeing is just because people are invested in Regex.

Um.. no? He is seeing pushback because one of his main claims (100x faster) is very likely factually wrong. And also because he is not even acknowledging all other prior art in this space.

Re: Show HN: Nevod is easier and faster than RegExp

#67

Post by nostrademons »

glangdale wrote: post #62
ychetyrko wrote: post #48

First of all, thanks everyone for the valuable feedback, critics, suggestions, etc. Truly appreciate that! And thanks for patience to all people who are playing with the Nevod right now and getting errors. We have an unexpectedly high interest and number of visitors is very high in our playground. Meanwhile, it's a preview of the technology, please keep in mind. Let me clarify few things. The speed of Nevod is based…

> 2. Nevod matches MULTIPLE patterns against document in ONE PASS. Patters/expressions are indexed by state machine and filtered effectively during matching. This is a good idea. It's such a good idea that we did it in 2006, sold a company to Intel based around in in 2013 and open-sourced the resulting library ( https://github.com/intel/hyperscan ) in 2015. All multi-pattern systems get a huge improvement over one-at…

Isn't this basically what regexp-based lexer generators (eg. lex, 1975) do? Stdlib regexps need to run multiple passes because the library itself has no idea whether it's being used with one pattern or multiple patterns, but any lexer generator that has all the patterns at once (i.e. all of them) can merge the DFAs generated and match the input in a single pass.

Hell, I've been known to do quick & dirty versions of this technique by concatenating all the patterns together with "|" before passing them to Pattern.compile. It takes all of one line of code. Backtracking regexp engines don't really benefit from this, but DFA-based regexp engines like RE2 can get massive speedups.

Re: Show HN: Nevod is easier and faster than RegExp

#69

Post by glangdale »

nostrademons wrote: post #67
glangdale wrote: post #62

Earlier quoted context omitted.

> 2. Nevod matches MULTIPLE patterns against document in ONE PASS. Patters/expressions are indexed by state machine and filtered effectively during matching. This is a good idea. It's such a good idea that we did it in 2006, sold a company to Intel based around in in 2013 and open-sourced the resulting library ( https://github.com/intel/hyperscan ) in 2015. All multi-pattern systems get a huge improvement over one-at…

Isn't this basically what regexp-based lexer generators (eg. lex, 1975) do? Stdlib regexps need to run multiple passes because the library itself has no idea whether it's being used with one pattern or multiple patterns, but any lexer generator that has all the patterns at once (i.e. all of them) can merge the DFAs generated and match the input in a single pass. Hell, I've been known to do quick & dirty versions of t…

The idea of compiling everything together into a single DFA is very old. However, this doesn't always work - it will result in a combinatorial explosion in many cases (informally, if the patterns contain a lot of states that overlap with other potential states you might be in from other patterns or elsewhere in that pattern). So DFA merging is a dark art and many people spend whole careers taping things to the side of the basic DFA algorithm to handle this.

This doesn't seem to come up with most lexers because the idea of using some crazy overlapping tokens doesn't sound great - i.e. you're probably not going to want to allow your tokens to overlap that much. So it's not a problem for lex, but it might be a problem if you're scanning 10,000 text analytics patterns simultaneously.

Concatenating patterns is fine for RE2 - and RE2 can survive this - to a point. However, RE2 just falls back to a 'survivable' Thompson NFA regex when determinization fails and has no other strategies.

For backtracking engines, concatenating patterns with "|" is equivalent to just trying one pattern, then the next, etc.

Re: Show HN: Nevod is easier and faster than RegExp

#70

Post by burntsushi »

glangdale wrote: post #63
Cu3PO42 wrote: post #27

Earlier quoted context omitted.

That sounds very much like what Rust's RegEx engine does. I understand it extracts longer literals (when available) to find a starting point for where a match might be according to [1]. [1] https://blog.burntsushi.net/ripgrep/#literal-optimizations

This is not a new technique with the Rust regex engine. We had a considerably more comprehensive literal 'factoring' approach in Hyperscan about a decade earlier (which also satisfied a lifelong ambition of mine; specifically misusing the netflow algorithm in a graph for something). The multiple literal implementation in that matcher is also a partial lift from Hyperscan's "Teddy" small group literal matcher (not sal…

While we're wishing for things, I'd love to see you write up how some of the algorithms (like Teddy) work. Hyperscan is clearly a treasure trove of them, but the effort required to extract its secrets is quite large! For example, I've spent quite a bit of time perusing its code (and your excellent mailing list posts), and I still don't think I could describe its execution flow at a high level.

As far as literals go, I was doing that well before I heard about Hyperscan. I got the idea from hints in the literature. (On mobile or else I'd provide a link.)

Post reply on HN