[GSoC] Git Blog 12

[GSoC] Git Blog 12

[ZheNing Hu]

My twelfth week blog finished:
The web version is here:
https://adlternative.github.io/GSOC-Git-Blog-12/

## Week12 Avoid repetitive parsing

After we brought around `10%` optimization to `git cat-file --batch`
through skip
parse_object_buffer(), let's take a look at the result of gprof again:

```
  %
 time     calls(before)       calls(after)     name
  1.24               0              349756     format_ref_array_item
  1.24               0              349756     get_object
  0.83         4184784             4534690     do_xmalloc
  0.83               0             1399028     parse_ref_filter_atom
  0.41         4184936             5932565     memory_limit_check
  0.41          701711             1400412     strbuf_add
  0.41               0             1399024     append_atom
  0.41               0             1399024     quote_formatting
  0.41              14              349770     strbuf_init
  0.41               0              349756     populate_value
  0.00         2100807             2449753     strbuf_grow
  0.00         1973422             1973568     xmallocz
  0.00               0             1399024     get_ref_atom_value
  0.00               0             1399024     grab_values
  0.00              77              699589     xstrdup
  0.00              46              699558     xcalloc
```

gprof tells us that cat-file --batch will make a lot of copies by
`xstrdup()`, `strbuf_add()`... after
using the logic of ref-filter. But at present, the overhead of these
copies cannot be easily avoided
due to the inherent logic of ref-filter. So there are no good
optimization points in ref-filter ? We must
re-observe the whole problem from a macro perspective.

`oid_object_info_extended()` can get some metadata of the object, e.g.
`size`, `type`, `deltabase`,
then we can use `grab_common_values()` to grab them. And those data in
the content of the object
like commits' `tree-oid`, `parent-oid` or tags' `deref-oid`, which are
parsed by `parse_object_buffer()`,
then in `grab_tag_values()` or `grab_commit_values()`, we can grab
them. But many attributes of
commit and tag are not obtained through `parse_object_buffer()`, such
as `author-info` ,`commiter-info`,
`tagger-info` etc.

We need to call grab_sub_body_contents(), grab_person() to rescan the
buffer and extract the data.
What if we can combine these multiple scanning and parsing into one completion?
At least intuitively, this has an opportunity to improve performance.
So I check the implementation
details of `parse_commit_buffer()` and `parse_tag_buffer()`, maybe we
can pass some "hook pointer"
to these parsing functions like `oid_object_info_extended()` does to
extract only the information we need?
The commit-slab caught my attention. It can be used to get some
specified data content from the object.
I am thinking about whether it is possible to design a `struct
object_view` (temporarily called
`struct commit_view`) to store the offset of the parsed data in the
object content. `parse_commit_buffer()`
will check whether we need something for in-depth parsing. Like this:

```c
struct commit_view {
int need_tree : 1;
int need_parents : 1;

int need_author : 1;
int need_author_name : 1;
int need_author_email : 1;
int need_author_date : 1;

int need_committer : 1;
int need_committer_name : 1;
int need_committer_email : 1;
int need_committer_date : 1;

int tree_offset;
int tree_length;

int parents_nr;
int *parents_offset;
int *parents_length;

int author_offset;
int author_length;

int author_name_offset;
int author_name_length;
int author_email_offset;
int author_email_length;
int author_date_offset;
int author_date_length;

int committer_offset;
int committer_length;

int committer_name_offset;
int committer_name_length;
int committer_email_offset;
int committer_email_length;
int committer_date_offset;
int committer_date_length;
};

define_commit_slab(commit_view_slab, struct commit_view);
static struct commit_view_slab view_slab = COMMIT_SLAB_INIT(1, view_slab);

int parse_commit_buffer()
{
...
if (view->need_author) {
view->author_offset = bufptr - head;
view->author_length = ident_len;
}
if (view->need_author_name || view->need_author_email ||
    view->need_author_date) {
if (split_ident_line(&ident, ident_line, ident_len) ||
!ident.date_begin || !ident.date_end)
return error("bad author line in commit %s",
     oid_to_hex(&item->object.oid));
if (view->need_author_name) {
view->author_name_offset = ident.name_begin - head;
view->author_name_length = ident.name_end - ident.name_begin;
}
if (view->need_author_email) {
view->author_email_offset = ident.mail_begin - head + 1;
view->author_email_length = ident.mail_end - ident.mail_begin + 2;
}
if (view->need_author_date) {
view->author_date_offset = ident.date_begin - head;
view->author_date_length = ident.date_end - ident.date_begin;
}
}
...
}

```

It's still in WIP, hope it can bring some help!

There seems to be no tag-slab similar to commit-slab, do we need to invent it?

It seems that GSOC has only the last few weeks left, I'm not sure how
far this patch series is from
being merged by the master branch. Performance optimization may have
no end. By the way,
is there a chance to avoid a large number of copies in the ref-filter?
This may be another direction.

Thanks.
--
ZheNing Hu

Re: [GSoC] Git Blog 12

[Christian Couder]

On Mon, Aug 9, 2021 at 7:56 AM ZheNing Hu <adlternative@gmail.com> wrote:
>
> My twelfth week blog finished:
> The web version is here:
> https://adlternative.github.io/GSOC-Git-Blog-12/

Thanks!

> ## Week12 Avoid repetitive parsing
>
> After we brought around `10%` optimization to `git cat-file --batch`
> through skip

s/skip/skipping/

> parse_object_buffer(), let's take a look at the result of gprof again:
>
> ```
>   %
>  time     calls(before)       calls(after)     name
>   1.24               0              349756     format_ref_array_item
>   1.24               0              349756     get_object
>   0.83         4184784             4534690     do_xmalloc
>   0.83               0             1399028     parse_ref_filter_atom
>   0.41         4184936             5932565     memory_limit_check
>   0.41          701711             1400412     strbuf_add
>   0.41               0             1399024     append_atom
>   0.41               0             1399024     quote_formatting
>   0.41              14              349770     strbuf_init
>   0.41               0              349756     populate_value
>   0.00         2100807             2449753     strbuf_grow
>   0.00         1973422             1973568     xmallocz
>   0.00               0             1399024     get_ref_atom_value
>   0.00               0             1399024     grab_values
>   0.00              77              699589     xstrdup
>   0.00              46              699558     xcalloc
> ```
>
> gprof tells us that cat-file --batch will make a lot of copies by
> `xstrdup()`, `strbuf_add()`... after
> using the logic of ref-filter. But at present, the overhead of these
> copies cannot be easily avoided
> due to the inherent logic of ref-filter. So there are no good
> optimization points in ref-filter ? We must
> re-observe the whole problem from a macro perspective.
>
> `oid_object_info_extended()` can get some metadata of the object, e.g.
> `size`, `type`, `deltabase`,
> then we can use `grab_common_values()` to grab them. And those data in
> the content of the object
> like commits' `tree-oid`, `parent-oid` or tags' `deref-oid`, which are
> parsed by `parse_object_buffer()`,
> then in `grab_tag_values()` or `grab_commit_values()`, we can grab
> them. But many attributes of
> commit and tag are not obtained through `parse_object_buffer()`, such
> as `author-info` ,`commiter-info`,
> `tagger-info` etc.
>
> We need to call grab_sub_body_contents(), grab_person() to rescan the
> buffer and extract the data.
> What if we can combine these multiple scanning and parsing into one completion?
> At least intuitively, this has an opportunity to improve performance.

Yeah, but is there a way to check that we indeed scan or parse the
same objects multiple times? This way we might get an idea about how
much scanning and parsing we could save.

> So I check the implementation
> details of `parse_commit_buffer()` and `parse_tag_buffer()`, maybe we
> can pass some "hook pointer"
> to these parsing functions like `oid_object_info_extended()` does to
> extract only the information we need?

Would this also avoid scanning and parsing the same object many times?

> The commit-slab caught my attention. It can be used to get some
> specified data content from the object.

I thought it was for storing commit data in an efficient way.

> I am thinking about whether it is possible to design a `struct
> object_view` (temporarily called
> `struct commit_view`) to store the offset of the parsed data in the
> object content. `parse_commit_buffer()`
> will check whether we need something for in-depth parsing. Like this:
>
> ```c
> struct commit_view {
> int need_tree : 1;
> int need_parents : 1;
>
> int need_author : 1;
> int need_author_name : 1;
> int need_author_email : 1;
> int need_author_date : 1;
>
> int need_committer : 1;
> int need_committer_name : 1;
> int need_committer_email : 1;
> int need_committer_date : 1;

Is the above info specific for each commit? Or will the above be the
same for all the commits we are processing?

> int tree_offset;
> int tree_length;
>
> int parents_nr;
> int *parents_offset;
> int *parents_length;
>
> int author_offset;
> int author_length;
>
> int author_name_offset;
> int author_name_length;
> int author_email_offset;
> int author_email_length;
> int author_date_offset;
> int author_date_length;
>
> int committer_offset;
> int committer_length;
>
> int committer_name_offset;
> int committer_name_length;
> int committer_email_offset;
> int committer_email_length;
> int committer_date_offset;
> int committer_date_length;
> };
>
> define_commit_slab(commit_view_slab, struct commit_view);

Ok, so the idea is to use the commit slab feature to store the struct
commit_view instances. That seems reasonable to me.

> static struct commit_view_slab view_slab = COMMIT_SLAB_INIT(1, view_slab);
>
> int parse_commit_buffer()
> {
> ...
> if (view->need_author) {
> view->author_offset = bufptr - head;
> view->author_length = ident_len;
> }
> if (view->need_author_name || view->need_author_email ||
>     view->need_author_date) {
> if (split_ident_line(&ident, ident_line, ident_len) ||
> !ident.date_begin || !ident.date_end)
> return error("bad author line in commit %s",
>      oid_to_hex(&item->object.oid));
> if (view->need_author_name) {
> view->author_name_offset = ident.name_begin - head;
> view->author_name_length = ident.name_end - ident.name_begin;
> }
> if (view->need_author_email) {
> view->author_email_offset = ident.mail_begin - head + 1;
> view->author_email_length = ident.mail_end - ident.mail_begin + 2;
> }
> if (view->need_author_date) {
> view->author_date_offset = ident.date_begin - head;
> view->author_date_length = ident.date_end - ident.date_begin;
> }
> }
> ...
> }
>
> ```
>
> It's still in WIP, hope it can bring some help!
>
> There seems to be no tag-slab similar to commit-slab, do we need to invent it?

Let's first see if it helps when doing this for commits only. I also
think that usually the number of tags is much smaller than the number
of commits.

> It seems that GSOC has only the last few weeks left, I'm not sure how
> far this patch series is from
> being merged by the master branch. Performance optimization may have
> no end.

Yeah, but the idea for now is just to make using the ref-filter code
as fast as the current code.

> By the way,
> is there a chance to avoid a large number of copies in the ref-filter?
> This may be another direction.

Yeah, but I think it's less promising than reducing the number of
times objects are scanned or parsed. The first step though should be
to show that it can indeed be reduced further (after the 10%
optimization you made by skipping parse_object_buffer() when
possible).

Re: [GSoC] Git Blog 12

[ZheNing Hu]

Christian Couder <christian.couder@gmail.com> 于2021年8月10日周二 下午4:04写道：

> > parse_object_buffer(), let's take a look at the result of gprof again:
> >
> > We need to call grab_sub_body_contents(), grab_person() to rescan the
> > buffer and extract the data.
> > What if we can combine these multiple scanning and parsing into one completion?
> > At least intuitively, this has an opportunity to improve performance.
>
> Yeah, but is there a way to check that we indeed scan or parse the
> same objects multiple times? This way we might get an idea about how
> much scanning and parsing we could save.
>

I think find_subpos() called by grab_sub_body_contents() and find_wholine()
called by grab_person() are evidences that we are repeating iteratively.
But the proportion of time they occupy is too small. 0.0142% and 0.0109%

Sorry, but my attempts over the past two days have not gone well, the changes
here will make the program very complicated, the optimization here is not worth
doing.

> > So I check the implementation
> > details of `parse_commit_buffer()` and `parse_tag_buffer()`, maybe we
> > can pass some "hook pointer"
> > to these parsing functions like `oid_object_info_extended()` does to
> > extract only the information we need?
>
> Would this also avoid scanning and parsing the same object many times?
>

oid_object_info_extended()? I think it can set the pointer and extract
the required
value. Well, the problem it solves may be a little different from here.

> > The commit-slab caught my attention. It can be used to get some
> > specified data content from the object.
>
> I thought it was for storing commit data in an efficient way.
>

Yeah.

> > I am thinking about whether it is possible to design a `struct
> > object_view` (temporarily called
> > `struct commit_view`) to store the offset of the parsed data in the
> > object content. `parse_commit_buffer()`
> > will check whether we need something for in-depth parsing. Like this:
> >
> > ```c
> > struct commit_view {
> > int need_tree : 1;
> > int need_parents : 1;
> >
> > int need_author : 1;
> > int need_author_name : 1;
> > int need_author_email : 1;
> > int need_author_date : 1;
> >
> > int need_committer : 1;
> > int need_committer_name : 1;
> > int need_committer_email : 1;
> > int need_committer_date : 1;
>
> Is the above info specific for each commit? Or will the above be the
> same for all the commits we are processing?
>

According to the my previous thoughts, I think it is same for all commits.

>
> Ok, so the idea is to use the commit slab feature to store the struct
> commit_view instances. That seems reasonable to me.
>

It's a pity that it may not bring much optimization in real situations.

> > It seems that GSOC has only the last few weeks left, I'm not sure how
> > far this patch series is from
> > being merged by the master branch. Performance optimization may have
> > no end.
>
> Yeah, but the idea for now is just to make using the ref-filter code
> as fast as the current code.
>

It seems difficult to achieve consistent performance. As we discussed
before, the
previous `git cat-file --batch` can only provide a few kinds of
metadata that does not
need to be parsed, and after using ref-filter logic allows cat-file to
use more structured
information about git objects. But this means it needs a harder path,
It requires many
traversals and many copies, If we really use the logic in ref-filter,
we can only do partial
optimization, we can't expect it to be as fast as the old function.
Unless we have the
opportunity to not use the logic in ref-filter, but use the new atoms
in ref-filter, this may
has a chance to escape the copy in the ref-filter. I don't know what
your opinion are...


Thanks.
--
ZheNing Hu

Re: [GSoC] Git Blog 12

[ZheNing Hu]

ZheNing Hu <adlternative@gmail.com> 于2021年8月10日周二 下午10:20写道：
>
> Christian Couder <christian.couder@gmail.com> 于2021年8月10日周二 下午4:04写道：
>
> > > parse_object_buffer(), let's take a look at the result of gprof again:
> > >
> > > We need to call grab_sub_body_contents(), grab_person() to rescan the
> > > buffer and extract the data.
> > > What if we can combine these multiple scanning and parsing into one completion?
> > > At least intuitively, this has an opportunity to improve performance.
> >
> > Yeah, but is there a way to check that we indeed scan or parse the
> > same objects multiple times? This way we might get an idea about how
> > much scanning and parsing we could save.
> >
>
> I think find_subpos() called by grab_sub_body_contents() and find_wholine()
> called by grab_person() are evidences that we are repeating iteratively.
> But the proportion of time they occupy is too small. 0.0142% and 0.0109%
>

Using such a method may reduce some unnecessary scans [1]
But it can do very little optimization... 1.6%.
On the other hand, our optimization should focus on the default format of
`git cat-file --batch`.

My new idea is to need a fast path: when we use the default format,
let us directly execute get_object() to avoid unnecessary traversal
and checking.

Thanks,
--
ZheNing Hu

[1]: https://github.com/adlternative/git/commit/7d274971d2b5e1d4e6061d1e29e4a0b2c6a10ea5

Re: [GSoC] Git Blog 12

[Christian Couder]

On Tue, Aug 10, 2021 at 4:20 PM ZheNing Hu <adlternative@gmail.com> wrote:
>
> Christian Couder <christian.couder@gmail.com> 于2021年8月10日周二 下午4:04写道：
>
> > > parse_object_buffer(), let's take a look at the result of gprof again:
> > >
> > > We need to call grab_sub_body_contents(), grab_person() to rescan the
> > > buffer and extract the data.
> > > What if we can combine these multiple scanning and parsing into one completion?
> > > At least intuitively, this has an opportunity to improve performance.
> >
> > Yeah, but is there a way to check that we indeed scan or parse the
> > same objects multiple times? This way we might get an idea about how
> > much scanning and parsing we could save.
>
> I think find_subpos() called by grab_sub_body_contents() and find_wholine()
> called by grab_person() are evidences that we are repeating iteratively.
> But the proportion of time they occupy is too small. 0.0142% and 0.0109%

Could adding traces help with measuring how many times we call
functions like get_object() or format_ref_array_item() for each
object?

I think it's interesting to have a better idea about how many times
functions that seem to take time like the above, or functions that
read objects, like oid_object_info_extended(), are called for each
object.

> Sorry, but my attempts over the past two days have not gone well, the changes
> here will make the program very complicated, the optimization here is not worth
> doing.

Maybe but it would be interesting to document what didn't work and why.

> > > So I check the implementation
> > > details of `parse_commit_buffer()` and `parse_tag_buffer()`, maybe we
> > > can pass some "hook pointer"
> > > to these parsing functions like `oid_object_info_extended()` does to
> > > extract only the information we need?
> >
> > Would this also avoid scanning and parsing the same object many times?
>
> oid_object_info_extended()? I think it can set the pointer and extract
> the required
> value. Well, the problem it solves may be a little different from here.

Could you explain a bit more?

I wonder if we sometimes call for example oid_object_info_extended()
once for an object and then parse_commit_buffer() for the same object,
when perhaps calling only parse_commit_buffer() once would have given
all the information we need.

> > > I am thinking about whether it is possible to design a `struct
> > > object_view` (temporarily called
> > > `struct commit_view`) to store the offset of the parsed data in the
> > > object content. `parse_commit_buffer()`
> > > will check whether we need something for in-depth parsing. Like this:
> > >
> > > ```c
> > > struct commit_view {
> > > int need_tree : 1;
> > > int need_parents : 1;
> > >
> > > int need_author : 1;
> > > int need_author_name : 1;
> > > int need_author_email : 1;
> > > int need_author_date : 1;
> > >
> > > int need_committer : 1;
> > > int need_committer_name : 1;
> > > int need_committer_email : 1;
> > > int need_committer_date : 1;
> >
> > Is the above info specific for each commit? Or will the above be the
> > same for all the commits we are processing?
>
> According to the my previous thoughts, I think it is same for all commits.

Yeah, so I think it doesn't make sense to duplicate it for each
object. It could be a separate struct and we wouldn't need to have it
in a commit slab.

And I think maybe the above could be extended with fields like
"need_full_parsing" or "need_object_info" that could be computed from
the above fields. This could then help avoid several calls to
different functions when one could be enough.

Also aren't bitfields like the above "unsigned int" instead of "int"
in our code base?

> > Ok, so the idea is to use the commit slab feature to store the struct
> > commit_view instances. That seems reasonable to me.
>
> It's a pity that it may not bring much optimization in real situations.

Maybe it's because copying data isn't actually a performance issue.

> > > It seems that GSOC has only the last few weeks left, I'm not sure how
> > > far this patch series is from
> > > being merged by the master branch. Performance optimization may have
> > > no end.
> >
> > Yeah, but the idea for now is just to make using the ref-filter code
> > as fast as the current code.
>
> It seems difficult to achieve consistent performance. As we discussed
> before, the
> previous `git cat-file --batch` can only provide a few kinds of
> metadata that does not
> need to be parsed, and after using ref-filter logic allows cat-file to
> use more structured
> information about git objects.

So the issue seems to be that we can't detect if only a few metadata
that don't need to be parsed are needed?

Could fields like "need_full_parsing" or "need_object_info" that I
suggest above help with that?

> But this means it needs a harder path,
> It requires many
> traversals and many copies,

Could you explain why it needs many traversal and copies in more
details? And what could help avoid that?

> If we really use the logic in ref-filter,
> we can only do partial
> optimization, we can't expect it to be as fast as the old function.
> Unless we have the
> opportunity to not use the logic in ref-filter, but use the new atoms
> in ref-filter, this may
> has a chance to escape the copy in the ref-filter. I don't know what
> your opinion are...

Are you sure we couldn't detect in the ref-filter code that we need
only a few metadata that don't need to be parsed? And then skip
fetching and parsing data we don't need (without using a completely
separate code, like a fast path)?

Re: [GSoC] Git Blog 12

[Christian Couder]

On Wed, Aug 11, 2021 at 5:47 AM ZheNing Hu <adlternative@gmail.com> wrote:
>
> ZheNing Hu <adlternative@gmail.com> 于2021年8月10日周二 下午10:20写道：

> > I think find_subpos() called by grab_sub_body_contents() and find_wholine()
> > called by grab_person() are evidences that we are repeating iteratively.
> > But the proportion of time they occupy is too small. 0.0142% and 0.0109%
> >
>
> Using such a method may reduce some unnecessary scans [1]
> But it can do very little optimization... 1.6%.
> On the other hand, our optimization should focus on the default format of
> `git cat-file --batch`.
>
> My new idea is to need a fast path: when we use the default format,
> let us directly execute get_object() to avoid unnecessary traversal
> and checking.

I think it should be done not only when we use the default format but
when we use any format that only needs the metadata provided by
get_object(). This way that wouldn't be a special case fast path, but
rather a generally useful optimization.

Re: [GSoC] Git Blog 12

[ZheNing Hu]

Christian Couder <christian.couder@gmail.com> 于2021年8月11日周三 下午4:20写道：
>
> On Wed, Aug 11, 2021 at 5:47 AM ZheNing Hu <adlternative@gmail.com> wrote:
> >
> > ZheNing Hu <adlternative@gmail.com> 于2021年8月10日周二 下午10:20写道：
>
> > > I think find_subpos() called by grab_sub_body_contents() and find_wholine()
> > > called by grab_person() are evidences that we are repeating iteratively.
> > > But the proportion of time they occupy is too small. 0.0142% and 0.0109%
> > >
> >
> > Using such a method may reduce some unnecessary scans [1]
> > But it can do very little optimization... 1.6%.
> > On the other hand, our optimization should focus on the default format of
> > `git cat-file --batch`.
> >
> > My new idea is to need a fast path: when we use the default format,
> > let us directly execute get_object() to avoid unnecessary traversal
> > and checking.
>
> I think it should be done not only when we use the default format but
> when we use any format that only needs the metadata provided by
> get_object(). This way that wouldn't be a special case fast path, but
> rather a generally useful optimization.

Sorry, the reply is a bit late. These two days have been busy implementing
more valuable performance optimization patches. I finally did not implement
the above plan. At present, ref-filter does have some small areas worth
optimizing. A large part of the remaining performance loss comes from
more allocated memory and more copying. We must bear a certain gap
in performance. But we can minimize it as much as possible. This is perhaps
the most reasonable at present.

Let’s forget about the previous commit-slab for now and take a look at my
new optimization these two days:
https://lore.kernel.org/git/pull.1016.git.1628842990.gitgitgadget@gmail.com/

Thanks.
--
ZheNing Hu