From: ZheNing Hu <hidden> Date: 2021-08-09 05:56:27
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:
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:
structcommit_view{intneed_tree:1;intneed_parents:1;intneed_author:1;intneed_author_name:1;intneed_author_email:1;intneed_author_date:1;intneed_committer:1;intneed_committer_name:1;intneed_committer_email:1;intneed_committer_date:1;inttree_offset;inttree_length;intparents_nr;int*parents_offset;int*parents_length;intauthor_offset;intauthor_length;intauthor_name_offset;intauthor_name_length;intauthor_email_offset;intauthor_email_length;intauthor_date_offset;intauthor_date_length;intcommitter_offset;intcommitter_length;intcommitter_name_offset;intcommitter_name_length;intcommitter_email_offset;intcommitter_email_length;intcommitter_date_offset;intcommitter_date_length;};define_commit_slab(commit_view_slab,structcommit_view);staticstructcommit_view_slabview_slab=COMMIT_SLAB_INIT(1,view_slab);intparse_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)returnerror("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
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:
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;
}
}
...
}
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).
From: ZheNing Hu <hidden> Date: 2021-08-10 14:27:46
Christian Couder [off-list ref] 于2021年8月10日周二 下午4:04写道：
quoted
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.
quoted
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.
quoted
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.
quoted
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:
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.
quoted
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
From: ZheNing Hu <hidden> Date: 2021-08-11 03:47:41
ZheNing Hu [off-list ref] 于2021年8月10日周二 下午10:20写道：
Christian Couder [off-list ref] 于2021年8月10日周二 下午4:04写道：
quoted
quoted
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
From: Christian Couder <hidden> Date: 2021-08-11 08:20:22
On Wed, Aug 11, 2021 at 5:47 AM ZheNing Hu [off-list ref] wrote:
ZheNing Hu [off-list ref] 于2021年8月10日周二 下午10:20写道：
quoted
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.
From: ZheNing Hu <hidden> Date: 2021-08-13 08:26:09
Christian Couder [off-list ref] 于2021年8月11日周三 下午4:20写道：
On Wed, Aug 11, 2021 at 5:47 AM ZheNing Hu [off-list ref] wrote:
quoted
ZheNing Hu [off-list ref] 于2021年8月10日周二 下午10:20写道：
quoted
quoted
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
From: Christian Couder <hidden> Date: 2021-08-11 08:15:24
On Tue, Aug 10, 2021 at 4:20 PM ZheNing Hu [off-list ref] wrote:
Christian Couder [off-list ref] 于2021年8月10日周二 下午4:04写道：
quoted
quoted
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.
quoted
quoted
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.
quoted
quoted
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:
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?
quoted
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.
quoted
quoted
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)?