GNU logs - #24689, boring messages

Message sent to bug-grep@HIDDEN:

Subject: bug#24689: Multithreaded grep Available
Resent-From: Aaron Zhou Qian <aaronzhouqian@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-grep@HIDDEN
Resent-Date: Fri, 14 Oct 2016 15:36:02 +0000
Resent-Message-ID: <handler.24689.B.147645931616418 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 24689 <at> debbugs.gnu.org
MIME-Version: 1.0
From: Aaron Zhou Qian <aaronzhouqian@HIDDEN>
Date: Fri, 14 Oct 2016 08:14:42 -0700
Message-ID: <CANbv7+w+_MSTUePP8HDBvHXYd03saEOrC2SOxjTtmas1UEDtxA@HIDDEN>
Content-Type: multipart/alternative; boundary=94eb2c0b6d6a939f89053ed4afb0
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

--94eb2c0b6d6a939f89053ed4afb0
Content-Type: text/plain; charset=UTF-8

Hi,

I've multithreaded the grep at the file granularity when used with -r or -R
on directories. The four files that I changed i.e. grep.c dosbuff.c
dfasearch.c search.h under src/ is in this repository:

https://github.com/AaronZhouQian/grep

Please take a look at the README there.


The default number of threads is the number of cores online in the system.

To specify a custom number of threads use -p or --parallel followed by the
number of threads.

Currently multithreading does not support context i.e. -A -B -C


I'd like to invite everyone to test this patch.


Thank you,

Aaron

--94eb2c0b6d6a939f89053ed4afb0
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><font face=3D"arial, helvetica, sans-serif">Hi,</font><div=
><font face=3D"arial, helvetica, sans-serif"><br></font></div><div><font fa=
ce=3D"arial, helvetica, sans-serif">I&#39;ve multithreaded the grep at the =
file granularity when used with -r or -R on directories. The four files tha=
t I changed i.e.=C2=A0<span style=3D"color:rgb(51,51,51)"><font size=3D"3">=
grep.c dosbuff.c dfasearch.c search.h </font>under src/<font size=3D"3">=C2=
=A0</font></span>is in this repository:=C2=A0</font></div><div><font face=
=3D"arial, helvetica, sans-serif"><br></font></div><div><font face=3D"arial=
, helvetica, sans-serif" size=3D"4"><a href=3D"https://github.com/AaronZhou=
Qian/grep">https://github.com/AaronZhouQian/grep</a></font></div><div><font=
 face=3D"arial, helvetica, sans-serif"><br></font></div><div><font face=3D"=
arial, helvetica, sans-serif">Please take a look at the README there.=C2=A0=
</font></div><div><p style=3D"box-sizing:border-box;margin-top:0px;margin-b=
ottom:16px;color:rgb(51,51,51)"><br></p><p style=3D"box-sizing:border-box;m=
argin-top:0px;margin-bottom:16px;color:rgb(51,51,51)">The d<span style=3D"f=
ont-family:arial,helvetica,sans-serif">efault number of threads is the numb=
er of cores online in the system.</span><br></p><p style=3D"box-sizing:bord=
er-box;margin-top:0px;margin-bottom:16px;color:rgb(51,51,51)"><font face=3D=
"arial, helvetica, sans-serif">To specify a custom number of threads use -p=
 or --parallel followed by the number of threads.</font></p><p style=3D"box=
-sizing:border-box;margin-top:0px;color:rgb(51,51,51);margin-bottom:0px"><f=
ont face=3D"arial, helvetica, sans-serif">Currently multithreading does not=
 support context i.e. -A -B -C</font></p><p style=3D"box-sizing:border-box;=
margin-top:0px;color:rgb(51,51,51);margin-bottom:0px"><font face=3D"arial, =
helvetica, sans-serif"><br></font></p><p style=3D"box-sizing:border-box;mar=
gin-top:0px;color:rgb(51,51,51);margin-bottom:0px"><font face=3D"arial, hel=
vetica, sans-serif">I&#39;d like to invite everyone to test this patch.</fo=
nt></p><p style=3D"box-sizing:border-box;margin-top:0px;color:rgb(51,51,51)=
;margin-bottom:0px"><font face=3D"arial, helvetica, sans-serif"><br></font>=
</p><p style=3D"box-sizing:border-box;margin-top:0px;color:rgb(51,51,51);ma=
rgin-bottom:0px"><font face=3D"arial, helvetica, sans-serif">Thank you,</fo=
nt></p><p style=3D"box-sizing:border-box;margin-top:0px;color:rgb(51,51,51)=
;margin-bottom:0px"><font face=3D"arial, helvetica, sans-serif">Aaron</font=
></p></div></div>

--94eb2c0b6d6a939f89053ed4afb0--

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.505 (Entity 5.505)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Aaron Zhou Qian <aaronzhouqian@HIDDEN>
Subject: bug#24689: Acknowledgement (Multithreaded grep Available)
Message-ID: <handler.24689.B.147645931616418.ack <at> debbugs.gnu.org>
References: <CANbv7+w+_MSTUePP8HDBvHXYd03saEOrC2SOxjTtmas1UEDtxA@HIDDEN>
X-Gnu-PR-Message: ack 24689
X-Gnu-PR-Package: grep
Reply-To: 24689 <at> debbugs.gnu.org
Date: Fri, 14 Oct 2016 15:36:02 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-grep@HIDDEN

If you wish to submit further information on this problem, please
send it to 24689 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
24689: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D24689
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-grep@HIDDEN:

Subject: bug#24689: Multithreaded grep Available
Resent-From: Jim Meyering <jim@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-grep@HIDDEN
Resent-Date: Sat, 15 Oct 2016 05:05:01 +0000
Resent-Message-ID: <handler.24689.B24689.147650786131718 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Aaron Zhou Qian <aaronzhouqian@HIDDEN>, Zev Weiss <zev@HIDDEN>
Cc: 24689 <at> debbugs.gnu.org
MIME-Version: 1.0
In-Reply-To: <CANbv7+w+_MSTUePP8HDBvHXYd03saEOrC2SOxjTtmas1UEDtxA@HIDDEN>
References: <CANbv7+w+_MSTUePP8HDBvHXYd03saEOrC2SOxjTtmas1UEDtxA@HIDDEN>
From: Jim Meyering <jim@HIDDEN>
Date: Fri, 14 Oct 2016 22:03:52 -0700
Message-ID: <CA+8g5KFqZTphGWwMrRx=sfV_OH3wZsGc224v-_dtHoXsxg-Mfg@HIDDEN>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

On Fri, Oct 14, 2016 at 8:14 AM, Aaron Zhou Qian <aaronzhouqian@HIDDEN> wrote:
> Hi,
>
> I've multithreaded the grep at the file granularity when used with -r or -R
> on directories. The four files that I changed i.e. grep.c dosbuff.c
> dfasearch.c search.h under src/ is in this repository:
>
> https://github.com/AaronZhouQian/grep
>
> Please take a look at the README there.
>
>
> The default number of threads is the number of cores online in the system.
>
> To specify a custom number of threads use -p or --parallel followed by the
> number of threads.
>
> Currently multithreading does not support context i.e. -A -B -C
>
>
> I'd like to invite everyone to test this patch.

Thank you for working on that.
Before even looking at your patch, I have to ask whether you have
filed copyright assignment papers with the FSF. If not, I can get you
started.

Secondly, did you know that Zev Weiss has submitted some patches to
make grep multithreaded? He also helped to make dfa.c (now in gnulib)
multithread safe recently. It's been a while, and I don't know the
status of his patch set. At a minimum, please tell us how your
approach compares to his. https://github.com/zevweiss/grep

Message sent to bug-grep@HIDDEN:

Subject: bug#24689: Fwd: bug#22239: New Project
Resent-From: Paul Eggert <eggert@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-grep@HIDDEN
Resent-Date: Tue, 10 Jan 2017 00:47:02 +0000
Resent-Message-ID: <handler.24689.B24689.148400920019970 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Aaron Zhou Qian <aaronzhouqian@HIDDEN>
Cc: 24689 <at> debbugs.gnu.org
References: <CANbv7+zL0vyktnnuLZ9MHwFV1M9xSDR69MaWda1hfHS4Ug_myw@HIDDEN>
From: Paul Eggert <eggert@HIDDEN>
Organization: UCLA Computer Science Department
Message-ID: <b2b43a3b-1aea-35f3-8ff2-0cdd106bb93d@HIDDEN>
Date: Mon, 9 Jan 2017 16:46:30 -0800
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
 Thunderbird/45.6.0
MIME-Version: 1.0
In-Reply-To: <CANbv7+zL0vyktnnuLZ9MHwFV1M9xSDR69MaWda1hfHS4Ug_myw@HIDDEN>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

Oops, sorry, I gave you the wrong bug number. I am forwarding this to
Bug#24689, which is what I should have told you in the first place.

-------- Forwarded Message --------
Subject: 	bug#22239: New Project
Resent-Date: 	Sun, 08 Jan 2017 06:05:02 +0000
Resent-From: 	Aaron Zhou Qian <aaronzhouqian@HIDDEN>
Resent-CC: 	bug-grep@HIDDEN
Date: 	Sat, 7 Jan 2017 22:04:00 -0800
From: 	Aaron Zhou Qian <aaronzhouqian@HIDDEN>
To: 	Paul Eggert <eggert@HIDDEN>, 22239 <at> debbugs.gnu.org

On Sat, Jan 7, 2017 at 9:29 AM, Paul Eggert <eggert@HIDDEN> wrote:
>
> Could you remind us about the latest status of your proposal compared to
> Zev Weiss's? Does <http://bugs.gnu.org/24689> contain the latest thing
> you have? Zev Weiss's latest version is at <https://github.com/zevweiss/g
> rep>. Comparing the two was the thing Jim Meyering asked for at <
> http://bugs.gnu.org/22239#8>, and you can follow up by sending email to
> 22239 <at> debbugs.gnu.org.

Yes that github link is the latest version. I haven't made any changes to
that since last year September.

Basically the main thread traverses the file tree and assign the file to be
searched to each thread. There is also a dynamic buffer so that the output
is identical to the original grep program.

I tested the program on a server. On a directory containing 4 files, grep -r
on that directory is 4 times faster. On a directory containing 8 files, grep -r
is 6 times faster. On a directory containing 12 files, grep -r is 8.5 times
faster.

I think using multithreading is essentially different from not using
multithreading, and we also don't use multithreading all the time for grep.
When we're not using multithreading, i.e. when we pass in other options for
grep, more functions  would call those functions whose function signatures
we changed. This is hard to keep track of, because the program is fairly
complicated.

If we had overloading in C++ I would overload those functions. But since we
don't, I made it very clear in the code which functions are the
counterparts of the original versions. I did this to contain any potential
problems so that if there are any problems with multithreading it would not
affect the sequential program, whereas if we interleave the two scenarios
we might lose track of what's going on. At least this is what I initially
thought.

I saw that there were some recent commits by Zev together with Jim, for
example:

in

commit 9365ed6536d4fabf42ec17fef1bbe5d78884f950

* src/grep.c (compile_fp_t): Now returns an opaque pointer (the
compiled pattern).
(execute_fp_t): Now passed the pointer returned by a compile_fp_t.
All call sites updated accordingly.
(compiled_pattern): New static variable.
* src/dfasearch.c (GEAcompile): Return a void pointer (dummy NULL).
(EGexecute): Receive a void pointer argument (unused).
* src/kwsearch.c (Fcompile): Return a void pointer (dummy NULL).
(Fexecute): Receive a void pointer argument (unused).
* src/pcresearch.c (Pcompile): Return a void pointer (dummy NULL).
(Pexecute): Receive a void pointer argument (unused).
* src/search.h: Update compile/execute function prototypes.

So we have different approaches. They are trying to add extra pointer
arguments for the multithreading case. The pointer argument would be
NULL in the case multithreading is not in effect.  Whereas my approach
is to replicate the functions so the counterparts of the original
functions are used in the multithreading scenario. This was done in an
attempt to reduce the complexity of each of the functions and make the
program less monolithic. I leave you guys to decide.

Last modified: Mon, 25 Nov 2019 12:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.