From: Abhishek Kumar <abhishekkumar8222@gmail.com>
To: jnareb@gmail.com
Cc: christian.couder@gmail.com, git@vger.kernel.org, stolee@gmail.com
Subject: Re: [RFC] Possible idea for GSoC 2020
Date: Tue, 17 Mar 2020 23:30:00 +0530 [thread overview]
Message-ID: <CAHk66fv-fRZdUFC978sKUT_b7VYi6S2f2vdTQ6iB-wcCznnBHg@mail.gmail.com> (raw)
Greetings Jakub
> So perhaps we should expand "Commit graph labeling for speeding up git
> commands" idea, splitting it into two possible ways of working in this
> project: the more technical 'Generation number v2', and 'Interval labels
> for commit graph' which is more of research project? Which should be
> put first, then?
I would suggest working on generation number v2 first because:
- We ship improved performance *sooner*.
- I find it easier to shift from simpler to more complex systems.
On a personal note, I would be able to do a better job at working on generation
number v2 than on interval labels. While reading through the papers mentioned
was fun and full of a-ha moments, I find building things more
fulfilling. I would be
glad if either you or Derrick opt for mentoring it.
You could read my proposal at the link below. It is very rough and I haven't
proofread it yet. I will send out a more formal proposal once the direction
of this project is decided.
https://github.com/abhishekkumar2718/GSoC20/blob/master/graph_labelling.md
**Too long, didn't read**
- Commit graphs are small to medium-sized (compared to problem sizes observed in
graph-theory literature) sparse graphs. They have unusual properties compared
to more conventional graphs that can be exploited for better performance.
- Most of git's reachability queries are negative and using a negative-cut
filter improves performance more than a positive-cut filter.
- Implementing and maintaining a two-dimensional reachability index is hard
and does not offer justifiable performance gains.
- We plan to use corrected commit date as the generation number v2 because it is
locally computable, immutable and can be incrementally updated.
- If git ever considers a two-dimensional reachability index, either post order
DFS, GRAIL or an index based on commit date would be good starting
places to explore.
I go in more details about GRAIL, FERRARI and PReaCH, explaining
briefly how they work, their advantages, and disadvantages.
> Note that for example "Convert scripts to builtins" idea is in similar
> situation: it is also many projects in one.
Regards
Abhishek
next reply other threads:[~2020-03-17 18:00 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-17 18:00 Abhishek Kumar [this message]
2020-03-19 12:50 ` [RFC] Possible idea for GSoC 2020 Jakub Narebski
[not found] <CAHk66ftQqFqP-4kd4-8cHtCMEofSUvbeSQ24pcCCrkz7+2JG1w@mail.gmail.com>
2020-03-27 18:31 ` Jakub Narębski
-- strict thread matches above, loose matches on Subject: below --
2020-03-17 17:00 Abhishek Kumar
2020-03-17 18:05 ` Jakub Narebski
2020-03-13 17:30 Abhishek Kumar
2020-03-10 14:50 Jakub Narebski
2020-03-11 19:03 ` Junio C Hamano
2020-03-13 10:56 ` Jakub Narebski
2020-03-15 14:26 ` Jakub Narebski
2020-03-17 12:24 ` Kaartic Sivaraam
2020-03-17 12:39 ` Kaartic Sivaraam
2020-03-17 14:22 ` Jakub Narebski
2020-03-11 20:29 ` Christian Couder
2020-03-11 21:30 ` Jakub Narebski
2020-03-11 21:48 ` Christian Couder
2020-03-12 12:17 ` Jakub Narebski
2020-03-12 13:08 ` Jakub Narebski
2020-03-13 10:59 ` Jakub Narebski
2020-03-13 13:08 ` Philip Oakley
2020-03-13 14:34 ` Jakub Narebski
2020-03-15 18:57 ` Philip Oakley
2020-03-15 21:14 ` Jakub Narebski
2020-03-16 14:47 ` Philip Oakley
2020-03-16 12:44 ` Derrick Stolee
2020-03-17 3:13 ` Jakub Narebski
2020-03-17 7:24 ` Christian Couder
2020-03-17 11:49 ` Derrick Stolee
2020-03-17 14:18 ` Jakub Narebski
2020-03-17 17:04 ` Christian Couder
2020-03-18 13:55 ` Jakub Narebski
2020-03-18 15:25 ` Derrick Stolee
2020-03-19 12:52 ` Jakub Narebski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAHk66fv-fRZdUFC978sKUT_b7VYi6S2f2vdTQ6iB-wcCznnBHg@mail.gmail.com \
--to=abhishekkumar8222@gmail.com \
--cc=christian.couder@gmail.com \
--cc=git@vger.kernel.org \
--cc=jnareb@gmail.com \
--cc=stolee@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).