CUDA Grep

https://www.cs.cmu.edu/afs/cs/academic/class/15418-s12/www/competition/bkase.github.com/CUDA-grep/finalreport.html

by usgroup • 7 years ago

160 77 7 years ago

cs.cmu.edu

User23• 7 years ago

One reason that Perl regex is relatively slow is because it isn't actually regular: it can't be implemented using DFAs or NFAs.

gigatexal• 7 years ago

DFA/NFAs?

supergauntlet• 7 years ago

https://en.wikipedia.org/wiki/Deterministic_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.

hexspeaker2• 7 years ago

Deterministic 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

fwip• 7 years ago

Here is some further reading on the topic that I found useful.

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

apetresc• 7 years ago

Sure, 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?

ben5092• 7 years ago

Theoretically, 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.

rurban• 7 years ago

It 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• 7 years ago

see also, Perl Regular Expression Matching is NP-Hard: https://perl.plover.com/NPC/

joosters• 7 years ago

It'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• 7 years ago

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

cma2• 7 years ago

Some 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• 7 years ago

Yeah, but integrated GPUs wouldn't be usable with CUDA.

bkase6• 7 years ago

Oh good, I'm glad we did mention this!

ben5092• 7 years ago

They did not include the time it took to transfer the input file from memory to the GPU

Fair point, it's more support for this HN post[2] making the case for memory-mapping files to GPU.

This is a neat project, but there is a reason we are not using the GPU for regex matching.

I think it's more interesting that it's a general facility for running automata on a GPU, as it's opening up the universe of things that can be accelerated by a GPU. For instance, Numba[1] is a library to run arbitrary math code, and it has a feature for generating code to run on the GPU.

[1] http://numba.pydata.org/numba-doc/latest/cuda/index.html

[2] https://news.ycombinator.com/item?id=11892030

shaklee32• 7 years ago

CUDA already has this built in (for many years) using UVM. That won't take away the bottleneck of the transfer, but it does make it transparent to the user by handling all the paging/copies.

bkase6• 7 years ago

One of the authors here:

Yes you are right, you should not replace grep for one off regexes due to the latency of the io operations. As far as I recall, memory throughput however is much higher on house than on CPUs (or at least this was true in 2012). Our intended use cases for this sort of a grep were cases where you are finding many needles in enormous haystacks such as: Looking for malicious machine code in executables that you download off of the internet (virus scanning), or searching for certain genetic sequences in DNA code. I believe we discussed this in our final presentation, but perhaps we left it out of the written report.

Yes we probably should have included the numbers to show why you wouldn't want to use this instead of grep for simple tasks. I am sorry we missed it.

jldugger• 7 years ago

But getting any of that data off disk will typically be the bottleneck.

(Also, you'd want BLAST for DNA instead of grep, but perhaps this was an intentional simplification)

hinkley3• 7 years ago

I know in pretty nearly all the domains I've worked, discrete packets of data will use regexp directly.

If we are using something more 'grep'-like, it's for large quantities of data, and in many cases we could treat these as a stream. So as long as the bandwidth to the GPU is sufficient, a little stall at the beginning would represent an undue hardship, if the results come back faster.

zeusk• 7 years ago

I'm quite certain Windows Defender uses (or used, at some point) GPUs in the machine to accelerate malware pattern matching. I remember a coworker talking about a funny bug as a consequence when the graphics driver executable itself was infected.

stochastic_monk• 7 years ago

I’ve run into this for simple tasks on a GPU, like merging sorted lists. The massive parallelism can’t make up for the transfer costs unless the operations performed are expensive enough. The “roofline” model is usually the perspective used for this kind of accelerator application.

dr_zoidberg• 7 years ago

Reminded me of a 12 year old paper on file carving by Marziale, Richard and Roussev[0].

[0] https://www.dfrws.org/sites/default/files/session-files/pres...

lmeyerov• 7 years ago

Or you can flip your assumptions and run 10X faster... everywhere. It was a tough investment, but we went GPU-first via Apache Arrow & Nvidia RAPIDS. (In this case, I'd look at RAPIDS / NVStrings before this.)

randyrand• 7 years ago

Totally disagree. Moving memory to the GPU can be parallelized while doing the computation. For larger files that can fully saturate the gpu's bandwidth, it's completely negligible. "Easily the most time consuming part", no. Not even close.

Also, IO bound? Again, no. My consumer MBP can read at 3.2GB/s. Good luck doing regex on that in real time on a CPU. This is a CPU bound operation for a typical high end configuration.

Does this make sense for a 1MB file? probably not. But anything well beyond that it will be way faster.

Here's a great talk about how you should think about GPU performance: https://www.nvidia.com/content/GTC-2010/pdfs/2238_GTC2010.pd...

ejbs• 7 years ago

They did not include the time it took to transfer the input file from memory to the GPU

To give some context: PCIe 3.0 x16 achieves about 11-12 GB/s. So, transfers for benchmarked 53MB file would add ~4.8 ms (per direction, assuming pinned host memory)

Now, they could also pursue a streaming approach, processing in "micro-batches". I.e., pipelining input transfers (HOST->GPU), GPU-based processing, and transfer of results (GPU->HOST), as pursued by [1] (disclaimer: I'm a co-author). This lower's processing latency. Since the interconnect is full-duplex, it would just limit the processing rate to about ~11 GB/s (i.e., 5 ms for mentioned 53MB). To be fair, though, input has to be sufficiently large, such that there are (a) enough micro-batches to overlap transfer and compute and (b) the micro-batches can be chosen to be still large enough to exploit full parallelism of the GPU.

[1] https://arxiv.org/pdf/1905.13415.pdf

peterburkimsher• 7 years ago

Previous discussion: https://news.ycombinator.com/item?id=5803943

bkase6• 7 years ago

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

Athas2• 7 years ago

Is the code available? The links are dead.

bkase6• 7 years ago

Hmm I'll take a look at that. Yes code is here: https://github.com/bkase/CUDA-grep

carlmr2• 7 years ago

Can you run your benchmarks against ripgrep and report back?

bkase6• 7 years ago

Unfortunately, I don't actually have access to NVidia hardware anymore -- but I would be happy to accept a PR from someone who can get this to run!

ltc55052• 7 years ago

The references on the project site lead to 404. Are they CMU internal links?

bkase6• 7 years ago

Which links specifically are broken?

qznc• 7 years ago

Did grep treat the input file as ASCII or UTF8?

I remember another story where someone claimed to be faster than grep. Turned out the comparison was unfair because if this distinction. I believe LANG=C is enough to turn grep into ASCII mode.

xvilka3• 7 years ago

Would 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• 7 years ago

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

xvilka3• 7 years ago

I already work on open source a lot, just in other areas.

privateSFacct• 7 years ago

CUDA 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• 7 years ago

OCL was pretty mature then. CUDA is not crap but it is lock-in and IMO its best features were captured by OCL.

yingw787• 7 years ago

There's open-source graphics drivers that use NVIDIA like 'nouveau', which in my experience are much better than the proprietary nvidia graphics drivers on linux. Otherwise, I believe CUDA exists and remains proprietary because ISAs change by GPU generation, and because NVIDIA has a habit of patching graphics bugs outside its API for gaming customers, both of which lead to tight coupling between client libraries and the underlying hardware.

xvilka3• 7 years ago

I know about nouveau and respect its developers so much. Trying to make it work despite an active resistance from NVIDIA itself - it requires some patience and rigor. The stance on providing firmwares to the project is ridiculous. I believe, NVIDIA invented the whole signing feature just to undermine nouveau efforts, using security just as a pretext (as many vendors do).

michaelmior2• 7 years ago

I'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 [1] https://github.com/ggreer/the_silver_searcher

nixpulvis2• 7 years ago

I 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• 7 years ago

Perhaps more appropriate would be Hyperscan: 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• 7 years ago

FWIW, I ported Hyperscan to ARM using SIMDe.

eesmith• 7 years 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/0121e6b... . The earliest versioned commit tag was 0.3 in March 2012 - 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/9d1e619ff359b6e...

michaelmior2• 7 years ago

I 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 :)

nixpulvis2• 7 years ago

Github link on this page is broken, otherwise this is looking awesome. I'm excited to try it out.

figitaki• 7 years ago

The correct link is https://github.com/bkase/CUDA-grep I think he's working on fixing the broken link.

UK-AL• 7 years ago

If anyone is slightly interested in a different approach. https://github.com/vqd8a/iNFAnt2. I think its designed around executing incredibly large regex sets

ngcc_hk• 7 years ago

None of the links work. Any source and log on say github?

yzh• 7 years ago

I 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

CUDA Grep

Related Stories