Possibly inacurate speedup measures

[matheustavares]

The standard grep uses regex as a pattern, while ParallelGrep uses a fixed string (substring search), which is much less computationally expensive than regex execution. So if grep's "-F" option wasn't used when measuring the time for the speedup calculations at README, the results may not be accurate. (Note: "-F" makes grep use fixed string instead of the default regex)

For example, running both versions in my i7-7700HQ (4 cores w/ hyper-threading) at the Linux Kernel src directory and searching for "int static" I'm getting this:

grep:         0m3.834s
grep -F:      0m1.735s
ParallelGrep: 0m1.519s

So I think you could more explicitly say, at README, that this is a simpler version of grep that works with fixed strings only. Or you could upgrade your version to use <regex.h>. But unfortunately, making this change it performed 0m17.885s, in the same previous test. Which means a slowdown against default grep :( Also, if the tests were indeed performed without grep's "-F" option, I think you should re-run them taking that into account and update the README information.

Don't get me wrong, it's a nice work :) And it seems really hard to get speedup in a parallel grep version... (I tried it myself previously and failed) But I hope you get it in an upcoming version :)

[PatricZhao]

Thanks for your testing.

Did you consider the file cache in the system?

As below, you can see the first time search is very slow but following grep is really faster since the file is already cached by the system.

$ time ../ParallelGrep/pgrep -r mkldnn * >& /dev/null

real 0m2.687s
user 0m1.097s
sys 0m2.594s

$ time ../ParallelGrep/pgrep -r mkldnn * >& /dev/null

real 0m0.439s
user 0m0.726s
sys 0m1.364s

The similar situation can be seen for grep.

$ time grep -r -F mkldnn * >& /dev/null

real 0m3.297s
user 0m0.237s
sys 0m0.568s

$ time grep -r -F mkldnn * >& /dev/null

real 0m1.507s
user 0m0.296s
sys 0m0.782s

My search base: git clone --recursive https://github.com/apache/incubator-mxnet

[PatricZhao]

Another test for big file. BTW, you can set thread num to 4 in the source code for your computer.
I am using 8 threads for all tests.

$wget https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-abstract.xml.gz
$ gunzip enwiki-latest-abstract.xml.gz
$ time grep -F "deep learning" enwiki-latest-abstract.xml >& /dev/null

real 0m3.094s
user 0m2.089s
sys 0m1.005s
$ time ./pgrep "deep learning" enwiki-latest-abstract.xml > /dev/null

real 0m1.173s
user 0m7.814s
sys 0m1.326s

[matheustavares]

I repeated the same test here (enwiki-lastest-abstract.xml) running twice to take advantage of cache:

time grep -F "deep learning" enwiki-latest-abstract.xml >/dev/null

real 0m0,259s
user 0m0,123s
sys 0m0,136s

time pgrep "deep learning" enwiki-latest-abstract.xml >/dev/null

real 0m1,358s
user 0m8,422s
sys 0m1,837s

Could you be, perhaps, running an older version of grep? I'm running grep (GNU grep) 3.3

PS: I'm running with 8 threads in order to take maximum advantage of my CPU (i7-7700HQ).

[PatricZhao]

You're right. I am using a default one in the machine grep (GNU grep) 2.20.

Let me update the grep and try again :)

[PatricZhao]

Exactly, the new version of grep is really faster than the older one.
My repo is a demo to show how to leverage parallel algorithm to accelerate the pattern search.
Looks like I have to update the algorithm or sth else to catch up :)

@MatheusBernardino Do you have interests to improve the speed? If so, we can figure out where to start.

$  time ./pgrep "deep learning" enwiki-latest-abstract.xml >& /dev/null

real    0m0.929s
user    0m5.995s
sys     0m1.083s

$ time ./grep/bin/grep -F "deep learning" enwiki-latest-abstract.xml >& /dev/null

real    0m0.143s
user    0m0.102s
sys     0m0.040s

[matheustavares]

I like the subject, but unfortunately, I don't have the time now :(

But even not reaching the original grep performance, your code is a good example of work distribution in parallel applications :)

Until you figure it out how to improve speed, maybe you could just update the README with the updated grep test and make it cleaner that this version uses fixed string, not regex. What do you think?

[PatricZhao]

Thanks for the interests for the demo.
Since this is the code written by several years ago and I don't have the plan to do further improvements.

Closing now and welcome to the contributions from the community.