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

71–80 of 82 posts

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

#71

Post by speedplane »

Higher level text searching has been around for decades. In fact lawyers use this all the time. For example:

motion w/3 (denied or deny!)

This will match any sentence with the word "motion" within three words of the word "denied" or any other word that starts with "deny" (e.g., "denying"). Often, these systems use regex underneath with fancy libraries built on top to determine word separation, sentence separation, etc.

The truth is that regex is really great for character level searching, but if you commonly do word or sentence level searching there are a variety of solutions already available.

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

#72

Post by MaxBarraclough »

Cu3PO42 wrote: post #17

The claims seem dubious to me as well. What exactly does faster mean here? Since a speedup of two orders of magnitude is mentioned I'm assuming it refers to matching speed. Is it faster than PCRE? Is it faster than some other engine or is the claim that it's faster than any available RegEx engine? I had a quick look at the reference and this looks like it will accept context-free languages (since recursion is allowed…

> Once compiled to a DFA, the pattern only has negligible influence on the matching time.

With the right optimisations, certain longer patterns can be much faster to scan for, on account of the Boyer-Moore approach.

If I asked you to search through a book for 10 consecutive pages of the letter 'Q', you wouldn't need to check every page. The same optimisation can be applied to regex. (Not that most regex implementations bother to do it, though.)

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

#73

Post by Cu3PO42 »

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…

I didn't mean to insinuate that it was. The Rust RegEx engine was simply the first that came to mind for me. What I did intend to say that if this is indeed the optimisation that Nevod claims it has, it is not the first to do it.

However I did take the time to read up on Hyperscan and would like to thank you for contributing to what looks like an excellent tool.

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

#74

Post by Cu3PO42 »

MaxBarraclough wrote: post #72
Cu3PO42 wrote: post #17

The claims seem dubious to me as well. What exactly does faster mean here? Since a speedup of two orders of magnitude is mentioned I'm assuming it refers to matching speed. Is it faster than PCRE? Is it faster than some other engine or is the claim that it's faster than any available RegEx engine? I had a quick look at the reference and this looks like it will accept context-free languages (since recursion is allowed…

> Once compiled to a DFA, the pattern only has negligible influence on the matching time. With the right optimisations, certain longer patterns can be much faster to scan for, on account of the Boyer-Moore approach. If I asked you to search through a book for 10 consecutive pages of the letter 'Q', you wouldn't need to check every page. The same optimisation can be applied to regex. (Not that most regex implementatio…

You're right. What I meant to say is that for any (formal) regular expression, we can compile it to a DFA and then match any strings in time linear in the length of the string.

Certainly the pattern length matters both for pre-processing (compiling to DFA) and the runtime in a Boyer-Moore approach. However, as you mentioned in the Boyer-Moore average case of Θ(n/m) a longer pattern is faster, rather than slower as the page on Nevod seems to imply.

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

#75

Post by stevefan1999 »

Sigh. https://swtch.com/~rsc/regexp/regexp1.html

Sadly, RegEx has evolved far away from the original regular expression we learnt in school, and it is certainly less NFA like. This make it harder to execute a faster speed, e.g. backtracing makes it more context sensitive etc.

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

#76

Post by ychetyrko »

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…

Geoff, for me it's real honor that you, well-known creator of Hyperscan, paid attention to what we are doing. We truly respect all the prior work in this field (Hyperscan, RE2, Rust, etc), so different benchmarks will be available.

However, we all need to keep in mind that Nevod operates on words, not characters, and Nevod targets large rule decks (1000-100000 patterns). So, we don't compete in the field of individual pattern matching or streaming matching (to some extent, goals of Hyperscan and Nevod are different). In other words, a lot of things depend on target goals, which usually are reflected in the kind of patterns and in their number.

Regarding patent. Sorry, for legal reasons I can't expose details at the moment.

Thank you for your valuable comments.

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

#77

Post by glangdale »

ychetyrko wrote: post #76
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…

Geoff, for me it's real honor that you, well-known creator of Hyperscan, paid attention to what we are doing. We truly respect all the prior work in this field (Hyperscan, RE2, Rust, etc), so different benchmarks will be available. However, we all need to keep in mind that Nevod operates on words, not characters, and Nevod targets large rule decks (1000-100000 patterns). So, we don't compete in the field of individua…

I don't think I'm all that well-known. :-)

Staying away from streaming is a good idea for a lot of designs. We all lost a lot of our hair making streaming work in Hyperscan, and it was often the thing suppressing easier optimizations. Or at least we would have to have a separate approach for streaming and block mode; not exactly great s/w engineering.

Word-based approaches are interesting. So is large scale. Hyperscan does embarrassingly badly on natural language stuff at scale due to some baked in assumptions about relative frequencies of literal factors and the literal matchers tend to fall apart on really huge literal sets in this domain. So there's definitely an opportunity here.

I would strongly encourage you to produce some repeatable benchmarks (at least, things where we can see what the task is for something like RE2 or Hyperscan). We spent many years in stealth mode with a lot of superlatives and NDA-only Powerpoint decks and I don't think it did ourselves any favors. It means that you wind up being the only guardian of your own honesty, which is ... tricky ("What the hell is a medium-complexity pattern, anyhow?").

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

#78

Post by glangdale »

burntsushi wrote: post #70
glangdale wrote: post #63

Earlier quoted context omitted.

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,…

We have a paper accepted to NSDI, so this will hopefully shed some light on things. A conference paper is, sadly, too small to fit more than a few subsystems so a writeup of Teddy isn't included.

As I don't work for Intel any more, it's unlikely that I will put in the effort for anything significantly more comprehensive. I am considering another building another regex matcher but it wouldn't be the encyclopedic list of optimizations approach. Paul Terra refers to Hyperscan as the "Dwarf Fortress of regular expression matchers". I have some new ideas I'd like to try out, in any case.

I wasn't suggesting that your use of literal factoring comes from Hyperscan, only the Teddy matcher. Literal factoring seems an old technique and I don't know the genuinely first cite of that.

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

#79

Post by burntsushi »

glangdale wrote: post #78
burntsushi wrote: post #70

Earlier quoted context omitted.

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,…

We have a paper accepted to NSDI, so this will hopefully shed some light on things. A conference paper is, sadly, too small to fit more than a few subsystems so a writeup of Teddy isn't included. As I don't work for Intel any more, it's unlikely that I will put in the effort for anything significantly more comprehensive. I am considering another building another regex matcher but it wouldn't be the encyclopedic list…

Gotya. Thanks for the clarification! I look forward to reading your paper! I'll hold out hope for the folks working on Hyperscan at Intel to do some more in depth write ups.
Post reply on HN