8 ms·
CUDA Grep
- User23 7y agoOne reason that Perl regex is relatively slow is because it isn't actually regular: it can't be implemented using DFAs or NFAs.
- gigatexal 7y agoDFA/NFAs?
- supergauntlet 7y agohttps://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa... Said another way: a state machine. True regular languages can be defined by a simple state machine, which is relatively much faster than the extended regular-like language that perl exposes.
- hexspeaker 7y agoDeterministic Finite Automaton. It's a concept from automata theory which is a concept from theory of computation. Implementations of DFA's are how libraries like google's re2 or golang's regex are implemented. They're not as powerful as regex libs built with a non-regular language model but that's by design. Fun trivia: DFAs and NFAs are computationally equivalent. Any NFA can be converted into an equivalent DFA. https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton
- JoelMcCracken 7y agoI always found the algorithm to convert a NFA to an equivalent DFA to be pretty cool.
- hinkley 7y agoHold up. I've seen this conversation play out probably half a dozen times over the last few years and it just occurred to me... If you can convert a nondeterministic automata to a deterministic one, doesn't that mean they are all deterministic?
- kazinator 7y ago"Nondeterministic" in automata is a very specialized word that doesn't refer to anything like a random process in a stochastic universe. It's a representation for state machines in which state transitions are apparently ambiguous: a given state in the NFA can, for exactly the same input, go into multiple other states. This is a very convenient representation for pattern matching. The way the ambiguity resolves itself is not through randomness, but by the understanding that the machine is in all of the possible states at the same time. Then, in a concrete implementation in a programming language, we represent that situation by using a set of states as the run-time state. E.g. when the input symbol b is received, some NFA machine goes from state { 0, 3, 5 } to { 1, 3, 7, 8 }; i.e. it is in NFA states 0, 3 and 5, which transition to 1, 3, 7, 8 when b is seen. NFA graphs can be executed directly by an NFA simulator which calculates these transitions on the fly. We can also statically figure out all the state sets there can be and their transitions.Then we re-label these sets as the simple states of a deterministic automaton. E.g. { 0, 3, 5 } is dubbed S0, { 1, 3, 7, 8} is dubbed S1. There is a transition from S0 to S1 on b. We can work through all the possible transitions, ferret out all the subsets and their transitions to build a simple machine. That is the "subset construction".
- hexspeaker 7y agoYes for regular languages but not for higher level ones. For example, deterministic context-free is a subset of context-free. For languages that are turing complete, the question is less about ability to compute and more about the speed at which something can be computed. This is an unsolved problem known as P vs. NP. https://en.wikipedia.org/wiki/P_versus_NP_problem https://en.wikipedia.org/wiki/P_versus_NP_problem
- crispyambulance 7y ago> ...not as powerful as regex libs built with a non-regular language... I've wondered about that, but I can't think of a realistic example where that would really matter. Is there something that perl regex's can do, in non-crazy everyday use-cases, that can't be done by something like re2?
- blaisio 7y agoBackreferences and look around. I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.
- Drup 7y agoActually, it's been proved for ... longer than PERL exists ? The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens. Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions. Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.
- setr 7y ago>Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete. Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA. I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)
- hinkley 7y agoThey are powerful in the sense that they are specialized to a task and perform it much better.
- fwip 7y agoHere is some further reading on the topic that I found useful. https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- apetresc 7y agoSure, but it must be relatively simple to identify, pre-compilation, if the regex is regular or not; there's only certain constructions that break regularity. Why couldn't Perl's engine fall back to a more optimized regular-language-only implementation for those cases, if it has such a big impact on performance?
- ben509 7y agoTheoretically, a regular expression can be expressed in constant space, and that's profoundly limiting, so anything that requires so much as a stack is not a regex. That includes basic things like capture groups. That doesn't mean you can't use automata in a regex-plus implementation, though. I can't find the paper, but I think there is a hybrid engine that tries to get the best of both worlds; constant space where possible and using additional space to provide more features.
- chaosite 7y agoYou can implement capture groups with no problem using automata (see re2). You might have meant to say that you can't use backreferences.
- rurban 7y agoIt can, and it's one of my explicit goals to do so. But the biggest problem is perl's horrible code in regcomp and regexec. (based on Henry Spencer's old code). It mostly does state transitions via goto or setjmp/longjmp. The initial regex scanner did 2 passes, so it would have been trivial to detect NFA illegal backtracking with zero cost. With a cleanly written codebase it would be much easier. my re::engine::PCRE2 replacement is much faster, can do everything and even has less bugs than perl5 regex updates. But it's still not production ready, and full replacement would still be huge work. Now it's just via hooks. Which are slow, because most of the work is done twice.
- chaosfox 7y agosee also, Perl Regular Expression Matching is NP-Hard: https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
- joosters 7y agoIt's also possible that they might be including perl's startup time in that measurement? Their comments about 'parallelising' 'by using ampersand' make me concerned about the methodology involved.
- sjf 7y agoThey ignored a key detail in their benchmark. They did not include the time it took to transfer the input file from memory to the GPU, (the GPU cores can only operate on graphics memory). This is easily going to be the most time consuming part. They also didn't include any IO operations in their timing, so instead of a 10x speedup, it is more likely to be a couple of percent faster as grep is going to be IO bound. This is a neat project, but there is a reason we are not using the GPU for regex matching.
- cma 7y agoSome GPUs have integrated memory with the CPU and don't need to do the transfer, it could still speed things up there couldn't it? Also, they didn't ignore the key detail, they mention it: "This is without taking into account the overhead of transferring data to the GPU."
- alfalfasprout 7y agoYeah, but integrated GPUs wouldn't be usable with CUDA.
- cma 7y agoNvidia makes several with integrated memory. Nintendo Switch is based on one etc.
- Athas 7y agoI have not been able to inspect the code (dead links), but from the description of their approach, they do not depend on anything particularly fancy from CUDA. An OpenCL implementation seems just as feasible.
- 2a96eb7d685a49c 7y agoDo Nvidia Tegra SOCs work in that way?
- justinmeiners 7y agoPerhaps on PCs, but plenty of mobile and consoles use a shared memory architecture.
- peterburkimsher 7y agoPrevious discussion: https://news.ycombinator.com/item?id=5803943 https://news.ycombinator.com/item?id=5803943
- bkase 7y agoOne of the authors here: Happy to answer any questions. Keep in mind this was a school project from 2012 (Kayvon's 15-418 at CMU, a wonderful class), so it's been a while.
- Athas 7y agoIs the code available? The links are dead.
- bkase 7y agoHmm I'll take a look at that. Yes code is here: https://github.com/bkase/CUDA-grep https://github.com/bkase/CUDA-grep
- carlmr 7y agoCan you run your benchmarks against ripgrep and report back?
- ltc5505 7y agoThe references on the project site lead to 404. Are they CMU internal links?
- bkase 7y agoWhich links specifically are broken?
- xvilka 7y agoWould be awesome if they use proper open source software stack, like OpenCL, not that NVIDIA proprietary crap. Using anything from NVIDIA harms open source, because until they bankrupt there won't be FOSS drivers and software for their GPUs.
- tasty_freeze 7y agoIf you hate nvidia so much, why do you want open source drivers for their crap products? You might be an OSS purist, but most people are trying to solve problems, and cuda is apparently more useful than opencl. Nothing is stopping you from enhancing opencl as a language, building useful libraries, writing documentation, holding conferences to build an ecosystem around opencl, and evangelizing the technology, just like nvidia did for cuda.
- privateSFacct 7y agoCUDA is not crap. At the time this paper was written it had been out for a number of years, had good multi-platform support, and had good support for nvidia GPUs. If they had used opencl they may have been using an immature product, that might really have been apple only at the time (or apple and IBM?). I don't know thie history but 8-9 years ago (when the research work may have started) nvidia was tpushing the cuda idea (almost entirely alone - AMD still playing catchup).
- wyldfire 7y ago
- michaelmior 7y agoI'm surprised to see no comparison with ripgrep[0] or The Silver Searcher[1], both of which claim to be faster alternatives to grep. [0] https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep [1] https://github.com/ggreer/the_silver_searcher https://github.com/ggreer/the_silver_searcher
- nixpulvis 7y agoI too am curious. Both of these other tools don't make use of the GPU unless I'm mistaken, so this would be an interesting comparison.
- ianhowson 7y agoPerhaps more appropriate would be Hyperscan: https://www.hyperscan.io/ https://www.hyperscan.io/ Even though it's now an Intel project targeting CPUs, it grew out of a startup trying run regex matching on parallel hardware.
- acuozzo 7y agoFWIW, I ported Hyperscan to ARM using SIMDe.
- eesmith 7y ago"this was a school project from 2012" as one of the authors here already commented before your comment. The first commit to ag - README.md - was in Nov. 2011; https://github.com/ggreer/the_silver_searcher/commit/0121e6b94a79155ba0e0048019330c9ee9cae005 https://github.com/ggreer/the_silver_searcher/commit/0121e6b... . The earliest versioned commit tag was 0.3 in March 2012 - https://github.com/ggreer/the_silver_searcher/tree/0.3 https://github.com/ggreer/the_silver_searcher/tree/0.3 . I think that lack of comparison is okay. The first commit to ripgrip was in 2016. https://github.com/BurntSushi/ripgrep/commit/9d1e619ff359b6e609b02f01e36952e603104bc6 https://github.com/BurntSushi/ripgrep/commit/9d1e619ff359b6e...
- michaelmior 7y agoI missed that comment. Of course then it's unfair for me to expect a comparison. That said, I would still be interested to see one now :)
- nixpulvis 7y agoGithub link on this page is broken, otherwise this is looking awesome. I'm excited to try it out.
- figitaki 7y agoThe correct link is https://github.com/bkase/CUDA-grep https://github.com/bkase/CUDA-grep I think he's working on fixing the broken link.
- UK-AL 7y agoIf anyone is slightly interested in a different approach. https://github.com/vqd8a/iNFAnt2 https://github.com/vqd8a/iNFAnt2. I think its designed around executing incredibly large regex sets
- ngcc_hk 7y agoNone of the links work. Any source and log on say github?
- yzh 7y agoI remember several years ago I saw this IOCCC winning entry on regex and thought "maybe we should write a parallel version" And it's good to see someone has it implemented now! https://www.ioccc.org/2012/hou/hint.html https://www.ioccc.org/2012/hou/hint.html