Questions on GSoC 2019 Ideas

Questions on GSoC 2019 Ideas

[Matheus Tavares Bernardino]

Hi, everyone

I've been in the mailing list for a couple weeks now, mainly working
on my gsoc micro-project[1] and in other patches that derived from it.
I also have been contributing to the Linux Kernel for half an year,
but am now mainly just supporting other students here at USP.

I have read the ideas page for the GSoC 2019 and many of them interest
me. Also, looking around git-dev materials on the web, I got to the
GSoC 2012 ideas page. And this one got my attention:
https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands

I'm interested in parallel computing and that has been my research
topic for about an year now. So I would like to ask what's the status
of this GSoC idea. I've read git-grep and saw that it is already
parallel, but I was wondering if there is any other section in git in
which it was already considered to bring parallelism, seeking to
achieve greater performance. And also, if this could, perhaps, be a
GSoC project.

I'm also interested in the 'convert script to builtin' task, and I was
wondering if 'git-bisect' would be a good candidate for that.

Thanks,
Matheus Tavares

[1]: https://public-inbox.org/git/20190226051804.10631-1-matheus.bernardino@usp.br/

Re: Questions on GSoC 2019 Ideas

[Christian Couder]

Hi Matheus,

On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino
<matheus.bernardino@usp.br> wrote:
>
> I've been in the mailing list for a couple weeks now, mainly working
> on my gsoc micro-project[1] and in other patches that derived from it.
> I also have been contributing to the Linux Kernel for half an year,
> but am now mainly just supporting other students here at USP.
>
> I have read the ideas page for the GSoC 2019 and many of them interest
> me. Also, looking around git-dev materials on the web, I got to the
> GSoC 2012 ideas page. And this one got my attention:
> https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands
>
> I'm interested in parallel computing and that has been my research
> topic for about an year now. So I would like to ask what's the status
> of this GSoC idea. I've read git-grep and saw that it is already
> parallel, but I was wondering if there is any other section in git in
> which it was already considered to bring parallelism, seeking to
> achieve greater performance. And also, if this could, perhaps, be a
> GSoC project.

I vaguely remember that we thought at one point that all the low
hanging fruits had already been taken in this area but I might be
wrong.

> I'm also interested in the 'convert script to builtin' task, and I was
> wondering if 'git-bisect' would be a good candidate for that.

There is an ongoing work on that by Tanushree Tumane, an Outreachy
intern. The end of the internship is March 5, but it seems to me that
there is not a lot of work left on the project, and hopefully
Tanushree or her mentors will take care of that.

Best,
Christian.

> Thanks,
> Matheus Tavares
>
> [1]: https://public-inbox.org/git/20190226051804.10631-1-matheus.bernardino@usp.br/

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Fri, Mar 1, 2019 at 5:20 AM Christian Couder
<christian.couder@gmail.com> wrote:
>
> Hi Matheus,
>
> On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino
> <matheus.bernardino@usp.br> wrote:
> >
> > I've been in the mailing list for a couple weeks now, mainly working
> > on my gsoc micro-project[1] and in other patches that derived from it.
> > I also have been contributing to the Linux Kernel for half an year,
> > but am now mainly just supporting other students here at USP.
> >
> > I have read the ideas page for the GSoC 2019 and many of them interest
> > me. Also, looking around git-dev materials on the web, I got to the
> > GSoC 2012 ideas page. And this one got my attention:
> > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands
> >
> > I'm interested in parallel computing and that has been my research
> > topic for about an year now. So I would like to ask what's the status
> > of this GSoC idea. I've read git-grep and saw that it is already
> > parallel, but I was wondering if there is any other section in git in
> > which it was already considered to bring parallelism, seeking to
> > achieve greater performance. And also, if this could, perhaps, be a
> > GSoC project.
>
> I vaguely remember that we thought at one point that all the low
> hanging fruits had already been taken in this area but I might be
> wrong.

We still have to remove some global variables, which is quite easy to
do, before one could actually add mutexes and stuff to allow multiple
pack access. I don't know though if the removing global variables is
that exciting for GSoC, or if both tasks could fit in one GSoC. The
adding parallel access is not that hard, I think, once you know
packfile.c and sha1-file.c relatively well. It's mostly dealing with
caches and all the sliding access windows safely.
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Johannes Schindelin]

Hi Chris,

On Thu, 28 Feb 2019, Christian Couder wrote:

> On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino
> <matheus.bernardino@usp.br> wrote:
> >
> > I'm also interested in the 'convert script to builtin' task, and I was
> > wondering if 'git-bisect' would be a good candidate for that.
> 
> There is an ongoing work on that by Tanushree Tumane, an Outreachy
> intern. The end of the internship is March 5, but it seems to me that
> there is not a lot of work left on the project, and hopefully
> Tanushree or her mentors will take care of that.

By "or their mentors" you are referring to yourself and to myself.

And indeed, there won'y be much to be done to convert the script to a full
built-in. But there were a couple of things that Tanushree also had on
their radar: Fix how git bisect handle many merge bases.

I think that could still be a Google Summer of Code project.

Ciao,
Johannes

> 
> Best,
> Christian.
> 
> > Thanks,
> > Matheus Tavares
> >
> > [1]: https://public-inbox.org/git/20190226051804.10631-1-matheus.bernardino@usp.br/
> 

Re: Questions on GSoC 2019 Ideas

[Thomas Gummerer]

On 03/01, Duy Nguyen wrote:
> On Fri, Mar 1, 2019 at 5:20 AM Christian Couder
> <christian.couder@gmail.com> wrote:
> >
> > Hi Matheus,
> >
> > On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino
> > <matheus.bernardino@usp.br> wrote:
> > >
> > > I've been in the mailing list for a couple weeks now, mainly working
> > > on my gsoc micro-project[1] and in other patches that derived from it.
> > > I also have been contributing to the Linux Kernel for half an year,
> > > but am now mainly just supporting other students here at USP.
> > >
> > > I have read the ideas page for the GSoC 2019 and many of them interest
> > > me. Also, looking around git-dev materials on the web, I got to the
> > > GSoC 2012 ideas page. And this one got my attention:
> > > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands
> > >
> > > I'm interested in parallel computing and that has been my research
> > > topic for about an year now. So I would like to ask what's the status
> > > of this GSoC idea. I've read git-grep and saw that it is already
> > > parallel, but I was wondering if there is any other section in git in
> > > which it was already considered to bring parallelism, seeking to
> > > achieve greater performance. And also, if this could, perhaps, be a
> > > GSoC project.
> >
> > I vaguely remember that we thought at one point that all the low
> > hanging fruits had already been taken in this area but I might be
> > wrong.
> 
> We still have to remove some global variables, which is quite easy to
> do, before one could actually add mutexes and stuff to allow multiple
> pack access. I don't know though if the removing global variables is
> that exciting for GSoC, or if both tasks could fit in one GSoC. The
> adding parallel access is not that hard, I think, once you know
> packfile.c and sha1-file.c relatively well. It's mostly dealing with
> caches and all the sliding access windows safely.

I'm not very familiar with what's required here, but reading the above
makes me think it's likely too much for a GSoC project.  I think I'd
be happy with a project that declares removing the global variables as
the main goal, and adding parallelism as a potential bonus.

I'm a bit wary of a too large proposal here, as we've historically
overestimated what kind of project is achievable over a summer (I've
been there myself, as my GSoC project was also more than I was able to
do in a summer :)).  I'd rather have a project whose goal is rather
small and can be expanded later, than having something that could
potentially take more than 3 months, where the student (or their
mentors) have to finish it after GSoC.

> -- 
> Duy

Re: Questions on GSoC 2019 Ideas

[Christian Couder]

On Sat, Mar 2, 2019 at 4:09 PM Thomas Gummerer <t.gummerer@gmail.com> wrote:
>
> On 03/01, Duy Nguyen wrote:
> > On Fri, Mar 1, 2019 at 5:20 AM Christian Couder
> > <christian.couder@gmail.com> wrote:
> > >
> > > Hi Matheus,
> > >
> > > On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino
> > > <matheus.bernardino@usp.br> wrote:
> > > >
> > > > I've been in the mailing list for a couple weeks now, mainly working
> > > > on my gsoc micro-project[1] and in other patches that derived from it.
> > > > I also have been contributing to the Linux Kernel for half an year,
> > > > but am now mainly just supporting other students here at USP.
> > > >
> > > > I have read the ideas page for the GSoC 2019 and many of them interest
> > > > me. Also, looking around git-dev materials on the web, I got to the
> > > > GSoC 2012 ideas page. And this one got my attention:
> > > > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands
> > > >
> > > > I'm interested in parallel computing and that has been my research
> > > > topic for about an year now. So I would like to ask what's the status
> > > > of this GSoC idea. I've read git-grep and saw that it is already
> > > > parallel, but I was wondering if there is any other section in git in
> > > > which it was already considered to bring parallelism, seeking to
> > > > achieve greater performance. And also, if this could, perhaps, be a
> > > > GSoC project.
> > >
> > > I vaguely remember that we thought at one point that all the low
> > > hanging fruits had already been taken in this area but I might be
> > > wrong.
> >
> > We still have to remove some global variables, which is quite easy to
> > do, before one could actually add mutexes and stuff to allow multiple
> > pack access. I don't know though if the removing global variables is
> > that exciting for GSoC, or if both tasks could fit in one GSoC. The
> > adding parallel access is not that hard, I think, once you know
> > packfile.c and sha1-file.c relatively well. It's mostly dealing with
> > caches and all the sliding access windows safely.
>
> I'm not very familiar with what's required here, but reading the above
> makes me think it's likely too much for a GSoC project.  I think I'd
> be happy with a project that declares removing the global variables as
> the main goal, and adding parallelism as a potential bonus.

Yeah, I think that the main issue, now that Duy found something that
could be a GSoC project, is that the potential mentors are not
familiar with the pack access code. It means that Matheus would
probably not get a lot of help from his mentors when he would work on
adding parallelism.

That may not be too big a problem though if Matheus is ok to ask many
technical questions on the mailing list. It seems to me that he could
succeed.

> I'm a bit wary of a too large proposal here, as we've historically
> overestimated what kind of project is achievable over a summer (I've
> been there myself, as my GSoC project was also more than I was able to
> do in a summer :)).  I'd rather have a project whose goal is rather
> small and can be expanded later, than having something that could
> potentially take more than 3 months, where the student (or their
> mentors) have to finish it after GSoC.

Yeah, I agree with your suggestion about a project that declares
removing the global variables as the main goal, and adding parallelism
as a potential bonus.

One thing I am still worried about is if we are sure that adding
parallelism is likely to get us a significant performance improvement
or not. If the performance of this code is bounded by disk or memory
access, then adding parallelism might not bring any benefit. (It could
perhaps decrease performance if memory locality gets worse.) So I'd
like some confirmation either by running some tests or by experienced
Git developers that it is likely to be a win.

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Sat, Mar 2, 2019 at 10:09 PM Thomas Gummerer <t.gummerer@gmail.com> wrote:
>
> On 03/01, Duy Nguyen wrote:
> > On Fri, Mar 1, 2019 at 5:20 AM Christian Couder
> > <christian.couder@gmail.com> wrote:
> > >
> > > Hi Matheus,
> > >
> > > On Thu, Feb 28, 2019 at 10:46 PM Matheus Tavares Bernardino
> > > <matheus.bernardino@usp.br> wrote:
> > > >
> > > > I've been in the mailing list for a couple weeks now, mainly working
> > > > on my gsoc micro-project[1] and in other patches that derived from it.
> > > > I also have been contributing to the Linux Kernel for half an year,
> > > > but am now mainly just supporting other students here at USP.
> > > >
> > > > I have read the ideas page for the GSoC 2019 and many of them interest
> > > > me. Also, looking around git-dev materials on the web, I got to the
> > > > GSoC 2012 ideas page. And this one got my attention:
> > > > https://github.com/peff/git/wiki/SoC-2012-Ideas#improving-parallelism-in-various-commands
> > > >
> > > > I'm interested in parallel computing and that has been my research
> > > > topic for about an year now. So I would like to ask what's the status
> > > > of this GSoC idea. I've read git-grep and saw that it is already
> > > > parallel, but I was wondering if there is any other section in git in
> > > > which it was already considered to bring parallelism, seeking to
> > > > achieve greater performance. And also, if this could, perhaps, be a
> > > > GSoC project.
> > >
> > > I vaguely remember that we thought at one point that all the low
> > > hanging fruits had already been taken in this area but I might be
> > > wrong.
> >
> > We still have to remove some global variables, which is quite easy to
> > do, before one could actually add mutexes and stuff to allow multiple
> > pack access. I don't know though if the removing global variables is
> > that exciting for GSoC, or if both tasks could fit in one GSoC. The
> > adding parallel access is not that hard, I think, once you know
> > packfile.c and sha1-file.c relatively well. It's mostly dealing with
> > caches and all the sliding access windows safely.
>
> I'm not very familiar with what's required here, but reading the above
> makes me think it's likely too much for a GSoC project.  I think I'd
> be happy with a project that declares removing the global variables as
> the main goal, and adding parallelism as a potential bonus.
>
> I'm a bit wary of a too large proposal here, as we've historically
> overestimated what kind of project is achievable over a summer (I've
> been there myself, as my GSoC project was also more than I was able to
> do in a summer :)).  I'd rather have a project whose goal is rather
> small and can be expanded later, than having something that could
> potentially take more than 3 months, where the student (or their
> mentors) have to finish it after GSoC.

This is why I'm not involved in GSoC. I often mis-estimate the size of
work (and yes I would still like your tree-based index format in,
can't remember why it never made it).

So yeah if you find removing global variables (which essentially
identifies shared states, a prerequisite for any parallel work)
reasonable for GSoC, I'd say go for it.

Be also aware that this kind of refactoring work could result in lots
of patches and it takes time to get them merged, if your GSoC goal is
to get merged.
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Sun, Mar 3, 2019 at 2:18 PM Christian Couder
<christian.couder@gmail.com> wrote:
> One thing I am still worried about is if we are sure that adding
> parallelism is likely to get us a significant performance improvement
> or not. If the performance of this code is bounded by disk or memory
> access, then adding parallelism might not bring any benefit. (It could
> perhaps decrease performance if memory locality gets worse.) So I'd
> like some confirmation either by running some tests or by experienced
> Git developers that it is likely to be a win.

This is a good point. My guess is the pack access consists of two
parts: deflate zlib, resolve delta objects (which is just another form
of compression) and actual I/O. The former is CPU bound and may take
advantage of multiple cores. However, the cache we have kinda helps
reduce CPU work load already, so perhaps the actual gain is not that
much (or maybe we could just improve this cache to be more efficient).
I'm adding Jeff, maybe he has done some experiments on parallel pack
access, who knows.

The second good thing from parallel pack access is not about utilizing
processing power from multiple cores, but about _not_ blocking. I
think one example use case here is parallel checkout. While one thread
is blocked by pack access code for whatever reason, the others can
still continue doing other stuff (e.g. write the checked out file to
disk) or even access the pack again to check more things out.
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Sun, Mar 3, 2019 at 5:12 PM Duy Nguyen <pclouds@gmail.com> wrote:
> This is a good point. My guess is the pack access consists of two
> parts: deflate zlib, resolve delta objects (which is just another form

s/deflate/inflate/ (i keep making this mistake)
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Thomas Gummerer]

On 03/03, Duy Nguyen wrote:
> On Sat, Mar 2, 2019 at 10:09 PM Thomas Gummerer <t.gummerer@gmail.com> wrote:
> > I'm not very familiar with what's required here, but reading the above
> > makes me think it's likely too much for a GSoC project.  I think I'd
> > be happy with a project that declares removing the global variables as
> > the main goal, and adding parallelism as a potential bonus.
> >
> > I'm a bit wary of a too large proposal here, as we've historically
> > overestimated what kind of project is achievable over a summer (I've
> > been there myself, as my GSoC project was also more than I was able to
> > do in a summer :)).  I'd rather have a project whose goal is rather
> > small and can be expanded later, than having something that could
> > potentially take more than 3 months, where the student (or their
> > mentors) have to finish it after GSoC.
> 
> This is why I'm not involved in GSoC. I often mis-estimate the size of
> work (and yes I would still like your tree-based index format in,
> can't remember why it never made it).

So do I, and that's why I'd like to err on the side of having smaller
projects :)

I think the main reason the tree-based index format never made it is
that the in-core APIs were not set up to make use of the new index
format.  I'm also still interested in getting it in, but I haven't
found the time for looking at making the index code pluggable yet.  It
would probably take a similar refactoring as with the refs code to get
this done.

All that said, GSoC was still a great experience for me, and I got to
learn a ton over the summer.  But I did feel like I let the people
that invested a lot of time in the project as well down a bit, by not
being able to finishing the project.  And having the feeling of
accomplishment of actually finishing a project would definitely have
been nice to have as well.  So for those reasons I think it would be
better for students to take on smaller projects.

> So yeah if you find removing global variables (which essentially
> identifies shared states, a prerequisite for any parallel work)
> reasonable for GSoC, I'd say go for it.
> 
> Be also aware that this kind of refactoring work could result in lots
> of patches and it takes time to get them merged, if your GSoC goal is
> to get merged.
> -- 
> Duy

Re: Questions on GSoC 2019 Ideas

[Jeff King]

On Sun, Mar 03, 2019 at 05:12:59PM +0700, Duy Nguyen wrote:

> On Sun, Mar 3, 2019 at 2:18 PM Christian Couder
> <christian.couder@gmail.com> wrote:
> > One thing I am still worried about is if we are sure that adding
> > parallelism is likely to get us a significant performance improvement
> > or not. If the performance of this code is bounded by disk or memory
> > access, then adding parallelism might not bring any benefit. (It could
> > perhaps decrease performance if memory locality gets worse.) So I'd
> > like some confirmation either by running some tests or by experienced
> > Git developers that it is likely to be a win.
> 
> This is a good point. My guess is the pack access consists of two
> parts: deflate zlib, resolve delta objects (which is just another form
> of compression) and actual I/O. The former is CPU bound and may take
> advantage of multiple cores. However, the cache we have kinda helps
> reduce CPU work load already, so perhaps the actual gain is not that
> much (or maybe we could just improve this cache to be more efficient).
> I'm adding Jeff, maybe he has done some experiments on parallel pack
> access, who knows.

Sorry, I don't have anything intelligent to add here. I do know that
`index-pack` doesn't scale well with more cores. I don't think I've ever
looked at adding parallel access to the packs themselves. I suspect it
would be tricky due to a few global variables (the pack windows, the
delta cache, etc).

> The second good thing from parallel pack access is not about utilizing
> processing power from multiple cores, but about _not_ blocking. I
> think one example use case here is parallel checkout. While one thread
> is blocked by pack access code for whatever reason, the others can
> still continue doing other stuff (e.g. write the checked out file to
> disk) or even access the pack again to check more things out.

I'm not sure if it would help much for packs, because they're organized
to have pretty good cold-cache read-ahead behavior. But who knows until
we measure it.

I do suspect that inflating (and delta reconstruction) done in parallel
could be a win for git-grep, especially if you have a really simple
regex that is quick to search.

-Peff

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Tue, Mar 5, 2019 at 11:51 AM Jeff King <peff@peff.net> wrote:
> > processing power from multiple cores, but about _not_ blocking. I
> > think one example use case here is parallel checkout. While one thread
> > is blocked by pack access code for whatever reason, the others can
> > still continue doing other stuff (e.g. write the checked out file to
> > disk) or even access the pack again to check more things out.
>
> I'm not sure if it would help much for packs, because they're organized
> to have pretty good cold-cache read-ahead behavior. But who knows until
> we measure it.
>
> I do suspect that inflating (and delta reconstruction) done in parallel
> could be a win for git-grep, especially if you have a really simple
> regex that is quick to search.

Maybe git-blame too. But this is based purely on me watching CPU
utilization of one command with hot cache. For git-blame though, diff
code as to be thread safe too but that's another story.
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Matheus Tavares Bernardino]

First of all, I must apologize for not replying during these last
days. I'm traveling and I rarely get a connection here. But I'll be
back March 11th.

On Sun, Mar 3, 2019 at 4:18 AM Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Sat, Mar 2, 2019 at 4:09 PM Thomas Gummerer <t.gummerer@gmail.com> wrote:
> >
> > I'm a bit wary of a too large proposal here, as we've historically
> > overestimated what kind of project is achievable over a summer (I've
> > been there myself, as my GSoC project was also more than I was able to
> > do in a summer :)).  I'd rather have a project whose goal is rather
> > small and can be expanded later, than having something that could
> > potentially take more than 3 months, where the student (or their
> > mentors) have to finish it after GSoC.
>

I totally understand the concern.

> Yeah, I agree with your suggestion about a project that declares
> removing the global variables as the main goal, and adding parallelism
> as a potential bonus.
>

Talking about a delimited scope for GSoC and a potential bonus after,
a potential idea comes to my mind: I'm still trying to define the
subject for my undergraduate thesis (which must be in HPC and/or
parallelism on CPU/GPU). And the idea of bringing more parallelism to
git seems to be too big for a GSoC project. So, perhaps, if we manage
to identify wether parallelism would indeed bring a good performance
gain to git, I could propose that to my advisor professor as my
undergraduate thesis and I could work on that during this whole year.
It is still an idea to be matured, but do you think it would be
feasible?

Re: Questions on GSoC 2019 Ideas

[Matheus Tavares Bernardino]

This exercise of estimating a good spot to gain performance with
parallelism at git seems more difficult than I thought, firstly. Also,
I'm not that familiar yet with git packing (neither with the sections
of it that could benefit from parallelism). So could anyone point me
some good references on this, where I could study and maybe come back
with more valuable suggestions?

On Tue, Mar 5, 2019 at 9:57 AM Duy Nguyen <pclouds@gmail.com> wrote:
>
> On Tue, Mar 5, 2019 at 11:51 AM Jeff King <peff@peff.net> wrote:
> > > processing power from multiple cores, but about _not_ blocking. I
> > > think one example use case here is parallel checkout. While one thread
> > > is blocked by pack access code for whatever reason, the others can
> > > still continue doing other stuff (e.g. write the checked out file to
> > > disk) or even access the pack again to check more things out.
> >

Hmm, you mean distributing the process of inflating, reconstructing
deltas and checking out files between the threads? (having each one
doing the process for a different file?)

> > I'm not sure if it would help much for packs, because they're organized
> > to have pretty good cold-cache read-ahead behavior. But who knows until
> > we measure it.
> >
> > I do suspect that inflating (and delta reconstruction) done in parallel
> > could be a win for git-grep, especially if you have a really simple
> > regex that is quick to search.
>
> Maybe git-blame too. But this is based purely on me watching CPU
> utilization of one command with hot cache. For git-blame though, diff
> code as to be thread safe too but that's another story.

I don't know if this relates to parallelizing pack access, but I
thought that sharing this with you all could perhaps bring some new
insights (maybe even on parallelizing some other git section): I asked
my friends who contribute to the Linux Kernel what git commands seems
to take longer during their kernel work, and the answers were:
- git log and git status, sometimes
- using pager's search at git log
- checking out to an old commit
- git log --oneline --decorate --graph

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Wed, Mar 6, 2019 at 6:47 AM Matheus Tavares Bernardino
<matheus.bernardino@usp.br> wrote:
>
> This exercise of estimating a good spot to gain performance with
> parallelism at git seems more difficult than I thought, firstly. Also,
> I'm not that familiar yet with git packing (neither with the sections
> of it that could benefit from parallelism). So could anyone point me
> some good references on this, where I could study and maybe come back
> with more valuable suggestions?

I think you should skim through
Documentation/technical/pack-format.txt to have an idea what we're
talking about here (inflation, delta cache...).

The short (and slightly inaccurate) version is, in order to give the
content of a SHA-1, we need to

1. locate that "object" in the pack file (I'm ignoring loose objects)

2. assume (worst case) that this object is a delta object, it contains
only modification of another object, so you would need to get the
content of the other object first, then apply these modification ("the
delta") to get the content. This could repeat many times

3. once you get full content, it's actually zlib compressed, so you
need to uncompress/inflate it.

Step 2 would be super slow if you have to uncompress that "another
object" every single time. So there's a "delta cache" which stores the
content of these "other objects". Next time you see a delta object on
top of one of these in the cache, you can just apply the delta and be
done with it. Much faster. This delta cache is of course global and
not thread safe.

Step 3 can also be slow when dealing with large blobs.

Another global state that Jeff mentions is pack windows I think is a
bit harder to explain quickly. But basically we have many "windows" to
see the raw content of a pack file, these windows are global (per pack
actually) and are also not thread safe.

So all these steps are not thread safe. When a command with multiple
thread support accesses the pack, all those steps are protected by a
single mutex (it's grep_mutex in builtin/grep.c or read_lock() in
builtin/pack-objects.c). As you can see steps here are CPU-bound (step
3 is obvious, step 2 will have to inflate the other objects), so if
you use a more fine-grained mutex, chances are the inflation step can
be done in parallel.

I think the good spots to gain performance are the commands that
already have multiple thread support. I mentioned git-grep and
git-pack-objects.c above. git-index-pack is the third one but it's
special and I think does not use general pack access code.

I think if we could somehow measure lock contention of those big locks
above we can guesstimate how much gain there is. If threads in
git-grep for example often have to wait for grep_mutex, then in the
best case scenario when you make pack access thread safe, lock
contention goes down to near zero.

> On Tue, Mar 5, 2019 at 9:57 AM Duy Nguyen <pclouds@gmail.com> wrote:
> >
> > On Tue, Mar 5, 2019 at 11:51 AM Jeff King <peff@peff.net> wrote:
> > > > processing power from multiple cores, but about _not_ blocking. I
> > > > think one example use case here is parallel checkout. While one thread
> > > > is blocked by pack access code for whatever reason, the others can
> > > > still continue doing other stuff (e.g. write the checked out file to
> > > > disk) or even access the pack again to check more things out.
> > >
>
> Hmm, you mean distributing the process of inflating, reconstructing
> deltas and checking out files between the threads? (having each one
> doing the process for a different file?)

Yes. So if one thread hits a giant file (and spends lot of time
inflating), the other threads can still go on inflate smaller files
and writing them to disk.

> > > I'm not sure if it would help much for packs, because they're organized
> > > to have pretty good cold-cache read-ahead behavior. But who knows until
> > > we measure it.
> > >
> > > I do suspect that inflating (and delta reconstruction) done in parallel
> > > could be a win for git-grep, especially if you have a really simple
> > > regex that is quick to search.
> >
> > Maybe git-blame too. But this is based purely on me watching CPU
> > utilization of one command with hot cache. For git-blame though, diff
> > code as to be thread safe too but that's another story.
>
> I don't know if this relates to parallelizing pack access, but I
> thought that sharing this with you all could perhaps bring some new
> insights (maybe even on parallelizing some other git section): I asked
> my friends who contribute to the Linux Kernel what git commands seems
> to take longer during their kernel work, and the answers were:
> - git log and git status, sometimes
> - using pager's search at git log
> - checking out to an old commit
> - git log --oneline --decorate --graph

Sometimes the slowness is not because of serialized pack access. I'm
sure git-status is not that much impacted by slow pack access.

The pager search case may be sped up (git-log has to look at lots of
blobs and trees) but you also need to parallelize diff code as well
and that I think is way too big to consider.

The checking out old commit, I think could also be sped up with
parallel checkout. Again this is really out of scope. But of course it
can't be done until pack access is thread safe. Or can be done but not
as pretty [1]. [1] suggests 30% speedup. That's the share-nothing best
possible case, I think. But that code is no way optimized so real
speedup could be higher.

[1] https://public-inbox.org/git/20160415095139.GA3985@lanh/
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Thomas Gummerer]

On 03/05, Matheus Tavares Bernardino wrote:
> First of all, I must apologize for not replying during these last
> days. I'm traveling and I rarely get a connection here. But I'll be
> back March 11th.
> 
> On Sun, Mar 3, 2019 at 4:18 AM Christian Couder
> <christian.couder@gmail.com> wrote:
> >
> > On Sat, Mar 2, 2019 at 4:09 PM Thomas Gummerer <t.gummerer@gmail.com> wrote:
> > >
> > > I'm a bit wary of a too large proposal here, as we've historically
> > > overestimated what kind of project is achievable over a summer (I've
> > > been there myself, as my GSoC project was also more than I was able to
> > > do in a summer :)).  I'd rather have a project whose goal is rather
> > > small and can be expanded later, than having something that could
> > > potentially take more than 3 months, where the student (or their
> > > mentors) have to finish it after GSoC.
> >
> 
> I totally understand the concern.
> 
> > Yeah, I agree with your suggestion about a project that declares
> > removing the global variables as the main goal, and adding parallelism
> > as a potential bonus.
> >
> 
> Talking about a delimited scope for GSoC and a potential bonus after,
> a potential idea comes to my mind: I'm still trying to define the
> subject for my undergraduate thesis (which must be in HPC and/or
> parallelism on CPU/GPU). And the idea of bringing more parallelism to
> git seems to be too big for a GSoC project. So, perhaps, if we manage
> to identify wether parallelism would indeed bring a good performance
> gain to git, I could propose that to my advisor professor as my
> undergraduate thesis and I could work on that during this whole year.
> It is still an idea to be matured, but do you think it would be
> feasible?

I think this idea is generally fine, but your project proposal should
only be about the parts that are going to be included in your GSoC
project.  Of course we love to see GSoC students that are still
actively participating in the project after GSoC.  However that should
not be part of the sponsored program.  Mentors may also be less
available outside of the program, as mentoring can take quite some
time commitment.

Another slight concern here is that the mentors may be less familiar
with this project than others (I for one am not very familiar, and
Christian mentioned similar concerns), so it may be harder to give you
good advice.

All that said, if you are still excited about this project, think
about how to address these concerns in your proposal.  And feel free
to discuss the proposal on the mailing list as well, before actually
submitting it.

Re: Questions on GSoC 2019 Ideas

[Matheus Tavares Bernardino]

On Wed, Mar 6, 2019 at 7:17 AM Duy Nguyen <pclouds@gmail.com> wrote:
>
> On Wed, Mar 6, 2019 at 6:47 AM Matheus Tavares Bernardino
> <matheus.bernardino@usp.br> wrote:
> >
> > This exercise of estimating a good spot to gain performance with
> > parallelism at git seems more difficult than I thought, firstly. Also,
> > I'm not that familiar yet with git packing (neither with the sections
> > of it that could benefit from parallelism). So could anyone point me
> > some good references on this, where I could study and maybe come back
> > with more valuable suggestions?
>
> I think you should skim through
> Documentation/technical/pack-format.txt to have an idea what we're
> talking about here (inflation, delta cache...).

Thanks for the recommendation. It was a very explanatory reading.

> The short (and slightly inaccurate) version is, in order to give the
> content of a SHA-1, we need to
>
> 1. locate that "object" in the pack file (I'm ignoring loose objects)
>
> 2. assume (worst case) that this object is a delta object, it contains
> only modification of another object, so you would need to get the
> content of the other object first, then apply these modification ("the
> delta") to get the content. This could repeat many times
>
> 3. once you get full content, it's actually zlib compressed, so you
> need to uncompress/inflate it.
>
> Step 2 would be super slow if you have to uncompress that "another
> object" every single time. So there's a "delta cache" which stores the
> content of these "other objects". Next time you see a delta object on
> top of one of these in the cache, you can just apply the delta and be
> done with it. Much faster. This delta cache is of course global and
> not thread safe.
>
> Step 3 can also be slow when dealing with large blobs.

Thanks for the explanation.

> Another global state that Jeff mentions is pack windows I think is a
> bit harder to explain quickly. But basically we have many "windows" to
> see the raw content of a pack file, these windows are global (per pack
> actually) and are also not thread safe.
>
> So all these steps are not thread safe. When a command with multiple
> thread support accesses the pack, all those steps are protected by a
> single mutex (it's grep_mutex in builtin/grep.c or read_lock() in
> builtin/pack-objects.c). As you can see steps here are CPU-bound (step
> 3 is obvious, step 2 will have to inflate the other objects), so if
> you use a more fine-grained mutex, chances are the inflation step can
> be done in parallel.
>
> I think the good spots to gain performance are the commands that
> already have multiple thread support. I mentioned git-grep and
> git-pack-objects.c above. git-index-pack is the third one but it's
> special and I think does not use general pack access code.
>
> I think if we could somehow measure lock contention of those big locks
> above we can guesstimate how much gain there is. If threads in
> git-grep for example often have to wait for grep_mutex, then in the
> best case scenario when you make pack access thread safe, lock
> contention goes down to near zero.

I've been thinking on how I could implement a test to estimate the
lock contention but had no success until now. I wanted to try
mutrace[2] but couldn't install it; I tried valgrind's drd but it
didn't seem to report a contention time estimation; And I tried
measuring the time of "pthread_mutex_lock(&grep_mutex)" but I don't
know how much significative this value is, since we can't directly
compare it (the time of many threads at lock) with the overall
execution time. Do you have an idea on how we could measure the lock
contention here?

Another thing that is occurring to me right now is whether git-grep,
as it is implemented today, would really benefit from thread-safe pack
access. I may have to study the code more, but it seems to me that
just the producer thread uses pack access.

[2] http://0pointer.de/blog/projects/mutrace.html

> > On Tue, Mar 5, 2019 at 9:57 AM Duy Nguyen <pclouds@gmail.com> wrote:
> > >
> > > On Tue, Mar 5, 2019 at 11:51 AM Jeff King <peff@peff.net> wrote:
> > > > > processing power from multiple cores, but about _not_ blocking. I
> > > > > think one example use case here is parallel checkout. While one thread
> > > > > is blocked by pack access code for whatever reason, the others can
> > > > > still continue doing other stuff (e.g. write the checked out file to
> > > > > disk) or even access the pack again to check more things out.
> > > >
> >
> > Hmm, you mean distributing the process of inflating, reconstructing
> > deltas and checking out files between the threads? (having each one
> > doing the process for a different file?)
>
> Yes. So if one thread hits a giant file (and spends lot of time
> inflating), the other threads can still go on inflate smaller files
> and writing them to disk.
>
> > > > I'm not sure if it would help much for packs, because they're organized
> > > > to have pretty good cold-cache read-ahead behavior. But who knows until
> > > > we measure it.
> > > >
> > > > I do suspect that inflating (and delta reconstruction) done in parallel
> > > > could be a win for git-grep, especially if you have a really simple
> > > > regex that is quick to search.
> > >
> > > Maybe git-blame too. But this is based purely on me watching CPU
> > > utilization of one command with hot cache. For git-blame though, diff
> > > code as to be thread safe too but that's another story.
> >
> > I don't know if this relates to parallelizing pack access, but I
> > thought that sharing this with you all could perhaps bring some new
> > insights (maybe even on parallelizing some other git section): I asked
> > my friends who contribute to the Linux Kernel what git commands seems
> > to take longer during their kernel work, and the answers were:
> > - git log and git status, sometimes
> > - using pager's search at git log
> > - checking out to an old commit
> > - git log --oneline --decorate --graph
>
> Sometimes the slowness is not because of serialized pack access. I'm
> sure git-status is not that much impacted by slow pack access.
>
> The pager search case may be sped up (git-log has to look at lots of
> blobs and trees) but you also need to parallelize diff code as well
> and that I think is way too big to consider.
>
> The checking out old commit, I think could also be sped up with
> parallel checkout. Again this is really out of scope. But of course it
> can't be done until pack access is thread safe. Or can be done but not
> as pretty [1]. [1] suggests 30% speedup. That's the share-nothing best
> possible case, I think. But that code is no way optimized so real
> speedup could be higher.
>
> [1] https://public-inbox.org/git/20160415095139.GA3985@lanh/

So, although it would be out of scope for GSoC, checkout, diff and log
(and maybe others) could all benefit from a thread-safe/parallel pack
access, right? If so, it is very motivating the impact this project
could, in theory, have :)

> --
> Duy

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Mon, Mar 11, 2019 at 09:18:47PM -0300, Matheus Tavares Bernardino wrote:
> I've been thinking on how I could implement a test to estimate the
> lock contention but had no success until now. I wanted to try
> mutrace[2] but couldn't install it; I tried valgrind's drd but it
> didn't seem to report a contention time estimation; And I tried
> measuring the time of "pthread_mutex_lock(&grep_mutex)" but I don't
> know how much significative this value is, since we can't directly
> compare it (the time of many threads at lock) with the overall
> execution time. Do you have an idea on how we could measure the lock
> contention here?

(I'm supposed to be doing something else, but this is more fun :D)

Yeah lock contention is probably hard to measure. But at least we can
measure how much time is blocked by mutex. Something like this [1]
gives me

    $ time ~/w/git/temp/git grep --threads=8 abc HEAD >/dev/null
    warning: let's have some fun
    block_time = 20ms
    block_count = 10725
    
    real    0m0,379s
    user    0m0,425s
    sys     0m0,073s

From this I know "git grep" took 379ms and at least 20ms (probably
including measurement overhead) is wasted on pthread_mutex_lock(). It
does not look that significant, I admit.

> Another thing that is occurring to me right now is whether git-grep,
> as it is implemented today, would really benefit from thread-safe pack
> access. I may have to study the code more, but it seems to me that
> just the producer thread uses pack access.

That producer I think is just handing out assignments to worker
threads. The real work is still done by worker threads.

The entry point to pack access in this code is protected by
grep_read_lock(). I believe the multithread one is in this deep call
chain (I found it out by gdb)

[main thread] grep_oid() -> add_work() ->
[worker thread] grep_source() -> grep_source_1() ->
grep_source_is_binary() -> grep_source_load() ->
grep_source_load_oid() -> read_object_file()

Note that there's another source of pack access, the
lock_and_read_oid_file() in grep_tree(). This is where we unpack tree
objects and traverse to get blob SHA-1.

This code is currently on the main thread (maybe this is what you
found?) so it does not really benefit from multi thread. We could
still add some sort of lookahead queue to inflate tree objects in
advance in parallel, but I don't know how much gain that will be.

One thing I didn't notice is we currently force no threads in the case
we need pack access, e.g. "git grep <regex> <commit>" or "git grep
--cached <regex>". So if you need to experiment, you need to hack it
and remove that restriction. That's the "let's have some fun" code in
[1].

So, assuming this is CPU bottleneck, let's have a look at how CPU is used.

    perf record git grep --threads=1 abc HEAD >/dev/null
    perf report

shows me the top CPU consumers are

  51,16%  git      libz.so.1.2.11      [.] inflate_fast
  19,55%  git      git                 [.] bmexec

You need to do some guessing here. But I believe the top call is from
inflating objects (either from packs or from loose objects). The
second one is from regular expression engine.

Since the regex here is very short (I deliberately try Jeff's case
where object access dominates), the CPU is mostly used up for object
inflation. That suggests that if we could spread it out across cores,
the gain could be quite good. There aren't many dependencies in grep
tasks so if we spread the workload on 8 cores, execution time should
be reduced by 7 or 8 times.

For fun, I hacked up a horrible, horrible "thread safe" version [2]
that probably broke 99% of git and made helgrind extremely unhappy, so
these numbers are at best guidelines, but..

    $ time ./git grep --threads=1 abc HEAD >/dev/null
    
    real    0m0,253s
    user    0m0,225s
    sys     0m0,029s
    
    $ time ./git grep --threads=8 abc HEAD >/dev/null
    warning: let's have some fun!
    
    real    0m0,157s
    user    0m0,312s
    sys     0m0,089s

You can see the "real" rows show quite good time reduction. Not 8
times reduction, mind you, but that's where serious people dig in and
really speed it up ;-)

[1] https://gitlab.com/snippets/1834609
[2] https://gitlab.com/snippets/1834613

> So, although it would be out of scope for GSoC, checkout, diff and log
> (and maybe others) could all benefit from a thread-safe/parallel pack
> access, right? If so, it is very motivating the impact this project
> could, in theory, have :)

We have to analyze case by case. It may turn out that there are many
opportunity to utilize multi threads. I think checkout is definitely a
good candidate. For "git diff" and "git log" maybe you can try "perf"
to see how much workload is locked in pack access (mostly inflation,
because it's easier to spot from the profile report)
--
Duy

Re: Questions on GSoC 2019 Ideas

[Duy Nguyen]

On Tue, Mar 12, 2019 at 5:02 PM Duy Nguyen <pclouds@gmail.com> wrote:
> We have to analyze case by case. It may turn out that there are many

s/are/aren't/

> opportunity to utilize multi threads. I think checkout is definitely a
> good candidate. For "git diff" and "git log" maybe you can try "perf"
> to see how much workload is locked in pack access (mostly inflation,
> because it's easier to spot from the profile report)
-- 
Duy

Re: Questions on GSoC 2019 Ideas

[Matheus Tavares Bernardino]

Hi,

I've been studying the codebase and looking for older emails in the ML
that discussed what I want to propose as my GSoC project. In
particular, I found a thread about slow git commands on chromium, so I
reached them out at chromium's ML to ask if it's still an issue. I got
the following answer:

On Wed, Apr 3, 2019 at 1:41 PM Erik Chen <erikchen@chromium.org> wrote:
> Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]
> On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(

I don't really know if treading would help stash and status, but I
think it could help blame. By the little I've read of blame's code so
far, my guess is that the priority queue used for the commits could be
an interface for a producer-consumer mechanism and that way,
assign_blame's main loop could be done in parallel. And as we can se
at [4], that is 90% of the command's time. Does this makes sense?

But as Duy pointed out, if I recall correctly, for git blame to be
parallel, pack access and diff code would have to be thread-safe
first. And also, it seems, by what we've talked earlier, that this
much wouldn't fit all together in a single GSoC. So, would it be a
nice GSoC proposal to try "making code used by blame thread-safe",
targeting a future parallelism on blame to be done after GSoC? And if
so, could you please point me out which files should I be studying to
write the planning for this proposal? (Unfortunately I wasn't able to
study pack access and diff code yet. I got carried on looking for
performance hostposts and now I'm a bit behind schedule :(

Also, an implementation for fuzzy blame is being developer right
now[5] and Jeff (CC-ed) suggested recently another performance
improvement that could be done in blame[6]. So I would like to know
wether you think it is worthy putting efforts trying to parallelize
it.

Thanks again for all the support.
Matheus Tavares

[1] https://bugs.chromium.org/p/git/issues/detail?id=18&q=
[2] https://bugs.chromium.org/p/git/issues/detail?id=17&q=
[3] https://bugs.chromium.org/p/git/issues/detail?id=16&q=
[4] https://i.imgur.com/XmyJMuE.png
[5] https://public-inbox.org/git/20190403160207.149174-1-brho@google.com/T/#mb772910506e99e00337e4606f8377f95ef41c8c6
[6] https://public-inbox.org/git/87ftqz5osx.fsf@fencepost.gnu.org/T/#m9caa63d35d39de8d2b7c5c6852f331dc2328e1ea

Re: Questions on GSoC 2019 Ideas

[Christian Couder]

Hi,

On Thu, Apr 4, 2019 at 3:15 AM Matheus Tavares Bernardino
<matheus.bernardino@usp.br> wrote:
>
> I've been studying the codebase and looking for older emails in the ML
> that discussed what I want to propose as my GSoC project. In
> particular, I found a thread about slow git commands on chromium, so I
> reached them out at chromium's ML to ask if it's still an issue. I got
> the following answer:
>
> On Wed, Apr 3, 2019 at 1:41 PM Erik Chen <erikchen@chromium.org> wrote:
> > Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]
> > On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(

Nice investigation. About git status I wonder though if they have
tried the possible optimizations, like untracked cache or
core.fsmonitor.

> I don't really know if treading would help stash and status, but I
> think it could help blame. By the little I've read of blame's code so
> far, my guess is that the priority queue used for the commits could be
> an interface for a producer-consumer mechanism and that way,
> assign_blame's main loop could be done in parallel. And as we can se
> at [4], that is 90% of the command's time. Does this makes sense?

I can't really tell as I haven't studied this, but from the links in
your email I think it kind of makes sense.

Instead of doing assign_blame()'s main loop in parallel though, if my
focus was only making git blame faster, I think I would first try to
cache xdl_hash_record() results and then if possible to compute
xdl_hash_record() in parallel as it seems to be a big bottleneck and a
quite low hanging fruit.

> But as Duy pointed out, if I recall correctly, for git blame to be
> parallel, pack access and diff code would have to be thread-safe
> first. And also, it seems, by what we've talked earlier, that this
> much wouldn't fit all together in a single GSoC. So, would it be a
> nice GSoC proposal to try "making code used by blame thread-safe",
> targeting a future parallelism on blame to be done after GSoC?

Yeah, I think it would be a nice proposal, even though it doesn't seem
to be the most straightforward way to make git blame faster.

Back in 2008 when we proposed a GSoC about creating a sequencer, it
wasn't something that would easily fit in a GSoC, and in fact it
didn't, but over the long run it has been very fruitful as the
sequencer is now used by cherry-pick and rebase -i, and there are
plans to use it even more. So unless people think it's not a good idea
for some reason, which hasn't been the case yet, I am ok with a GSoC
project like this.

> And if
> so, could you please point me out which files should I be studying to
> write the planning for this proposal? (Unfortunately I wasn't able to
> study pack access and diff code yet. I got carried on looking for
> performance hostposts and now I'm a bit behind schedule :(

I don't think you need to study everything yet, and I think you
already did a lot of studying, so I would suggest you first try to
send soon a proposal with the information you have right now, and then
depending on the feedback you get and the time left (likely not
much!!!), you might study some parts of the code a bit more later.

> Also, an implementation for fuzzy blame is being developer right
> now[5] and Jeff (CC-ed) suggested recently another performance
> improvement that could be done in blame[6]. So I would like to know
> wether you think it is worthy putting efforts trying to parallelize
> it.

What you would do seems compatible to me with the fuzzy blame effort
and an effort to cache xdl_hash_record() results.

Thanks,
Christian.

Re: Questions on GSoC 2019 Ideas

[Mike Hommey]

On Thu, Apr 04, 2019 at 09:56:35AM +0200, Christian Couder wrote:
> Hi,
> 
> On Thu, Apr 4, 2019 at 3:15 AM Matheus Tavares Bernardino
> <matheus.bernardino@usp.br> wrote:
> >
> > I've been studying the codebase and looking for older emails in the ML
> > that discussed what I want to propose as my GSoC project. In
> > particular, I found a thread about slow git commands on chromium, so I
> > reached them out at chromium's ML to ask if it's still an issue. I got
> > the following answer:
> >
> > On Wed, Apr 3, 2019 at 1:41 PM Erik Chen <erikchen@chromium.org> wrote:
> > > Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]
> > > On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(
> 
> Nice investigation. About git status I wonder though if they have
> tried the possible optimizations, like untracked cache or
> core.fsmonitor.

Note that one known issue on macOS specifically on large repos is that
the number of files explodes the inode cache in the kernel, and lstat
becomes slow.

e.g. https://groups.google.com/a/chromium.org/forum/#!topic/chromium-dev/p9U4jqz8kxo

Mike

Re: Questions on GSoC 2019 Ideas

[Matheus Tavares Bernardino]

On Thu, Apr 4, 2019 at 4:56 AM Christian Couder
<christian.couder@gmail.com> wrote:
>
> Hi,
>
> On Thu, Apr 4, 2019 at 3:15 AM Matheus Tavares Bernardino
> <matheus.bernardino@usp.br> wrote:
> >
> > I've been studying the codebase and looking for older emails in the ML
> > that discussed what I want to propose as my GSoC project. In
> > particular, I found a thread about slow git commands on chromium, so I
> > reached them out at chromium's ML to ask if it's still an issue. I got
> > the following answer:
> >
> > On Wed, Apr 3, 2019 at 1:41 PM Erik Chen <erikchen@chromium.org> wrote:
> > > Yes, this is absolutely still a problem for Chrome. I filed some bugs for common operations that are slow for Chrome: git blame [1], git stash [2], git status [3]
> > > On Linux, blame is the only operation that is really problematic. On macOS and Windows ... it's hard to find a git operation that isn't slow. :(
>
> Nice investigation. About git status I wonder though if they have
> tried the possible optimizations, like untracked cache or
> core.fsmonitor.

I don't know if they did, but I suggested them to check
core.commitGraph, pack.useBitmaps and core.untrackedCache (which Duy
suggested me in another thread).

> > I don't really know if treading would help stash and status, but I
> > think it could help blame. By the little I've read of blame's code so
> > far, my guess is that the priority queue used for the commits could be
> > an interface for a producer-consumer mechanism and that way,
> > assign_blame's main loop could be done in parallel. And as we can se
> > at [4], that is 90% of the command's time. Does this makes sense?
>
> I can't really tell as I haven't studied this, but from the links in
> your email I think it kind of makes sense.
>
> Instead of doing assign_blame()'s main loop in parallel though, if my
> focus was only making git blame faster, I think I would first try to
> cache xdl_hash_record() results and then if possible to compute
> xdl_hash_record() in parallel as it seems to be a big bottleneck and a
> quite low hanging fruit.

Hm, I see. But although it would take more effort to add threading at
assign_blame(), wouldn't it be better because more work could be done
in parallel? I think it could be implemented in the same fashion git
grep does.

> > But as Duy pointed out, if I recall correctly, for git blame to be
> > parallel, pack access and diff code would have to be thread-safe
> > first. And also, it seems, by what we've talked earlier, that this
> > much wouldn't fit all together in a single GSoC. So, would it be a
> > nice GSoC proposal to try "making code used by blame thread-safe",
> > targeting a future parallelism on blame to be done after GSoC?
>
> Yeah, I think it would be a nice proposal, even though it doesn't seem
> to be the most straightforward way to make git blame faster.
>
> Back in 2008 when we proposed a GSoC about creating a sequencer, it
> wasn't something that would easily fit in a GSoC, and in fact it
> didn't, but over the long run it has been very fruitful as the
> sequencer is now used by cherry-pick and rebase -i, and there are
> plans to use it even more. So unless people think it's not a good idea
> for some reason, which hasn't been the case yet, I am ok with a GSoC
> project like this.
>
> > And if
> > so, could you please point me out which files should I be studying to
> > write the planning for this proposal? (Unfortunately I wasn't able to
> > study pack access and diff code yet. I got carried on looking for
> > performance hostposts and now I'm a bit behind schedule :(
>
> I don't think you need to study everything yet, and I think you
> already did a lot of studying, so I would suggest you first try to
> send soon a proposal with the information you have right now, and then
> depending on the feedback you get and the time left (likely not
> much!!!), you might study some parts of the code a bit more later.

Thanks a lot, Christian. I'm writing my proposal and will try to send it today.

> > Also, an implementation for fuzzy blame is being developer right
> > now[5] and Jeff (CC-ed) suggested recently another performance
> > improvement that could be done in blame[6]. So I would like to know
> > wether you think it is worthy putting efforts trying to parallelize
> > it.
>
> What you would do seems compatible to me with the fuzzy blame effort
> and an effort to cache xdl_hash_record() results.
>
> Thanks,
> Christian.

Re: Questions on GSoC 2019 Ideas

[Christian Couder]

On Fri, Apr 5, 2019 at 6:29 PM Matheus Tavares Bernardino
<matheus.bernardino@usp.br> wrote:
>
> On Thu, Apr 4, 2019 at 4:56 AM Christian Couder
> <christian.couder@gmail.com> wrote:
> >
> > Nice investigation. About git status I wonder though if they have
> > tried the possible optimizations, like untracked cache or
> > core.fsmonitor.
>
> I don't know if they did, but I suggested them to check
> core.commitGraph, pack.useBitmaps and core.untrackedCache (which Duy
> suggested me in another thread).

Thanks! It would be nice to know if it has improved things for them.

> > I can't really tell as I haven't studied this, but from the links in
> > your email I think it kind of makes sense.
> >
> > Instead of doing assign_blame()'s main loop in parallel though, if my
> > focus was only making git blame faster, I think I would first try to
> > cache xdl_hash_record() results and then if possible to compute
> > xdl_hash_record() in parallel as it seems to be a big bottleneck and a
> > quite low hanging fruit.
>
> Hm, I see. But although it would take more effort to add threading at
> assign_blame(), wouldn't it be better because more work could be done
> in parallel? I think it could be implemented in the same fashion git
> grep does.

Yeah, I agree that it seems to be worth the effort.

> > I don't think you need to study everything yet, and I think you
> > already did a lot of studying, so I would suggest you first try to
> > send soon a proposal with the information you have right now, and then
> > depending on the feedback you get and the time left (likely not
> > much!!!), you might study some parts of the code a bit more later.
>
> Thanks a lot, Christian. I'm writing my proposal and will try to send it today.

Great!