On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
I'd like to see some sort of extension mechanism like in
$GIT_DIR/index, so that we don't have to increase pack index version
often. What I have in mind is optional commit cache to speed up
rev-list and merge, which could be stored in pack index too.
Can you share some of your ideas?
In Linus' Linux kernel tree there are currently about 323,178 commits.
If we store just the pre-parsed commit time as an int32 field this is
an additional 1.2 MiB of data in the pack-*.idx file, assuming we can
use additional data like pack offset position to correlate commit to
the parsed int. If we stored parent pointers in a similar way you
probably need at least 3.6 MiB of additional disk space on the index.
For example, use 12 bytes for each commit to store enough of the
parsed commit time to sort commits, and up to 2 parent pointers per
commit.... with a reserved magic value for octopus merges to mean the
commit itself has to be parsed to get the graph structure correct.
From: Jeff King <hidden> Date: 2016-06-15 22:54:53
On Thu, Sep 27, 2012 at 08:51:51AM -0700, Shawn O. Pearce wrote:
On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
I'd like to see some sort of extension mechanism like in
$GIT_DIR/index, so that we don't have to increase pack index version
often. What I have in mind is optional commit cache to speed up
rev-list and merge, which could be stored in pack index too.
On Thu, Sep 27, 2012 at 10:39 AM, Jeff King [off-list ref] wrote:
On Thu, Sep 27, 2012 at 08:51:51AM -0700, Shawn O. Pearce wrote:
quoted
On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
I'd like to see some sort of extension mechanism like in
$GIT_DIR/index, so that we don't have to increase pack index version
often. What I have in mind is optional commit cache to speed up
rev-list and merge, which could be stored in pack index too.
Quoting from that patch:
On 2012-08-12 Nguyen Thai Ngoc Duy [off-list ref] wrote:
Long term we might gain slight lookup speedup if we know object type
as search region is made smaller. But for that to happen, we need to
propagate object type hint down to find_pack_entry_one() and friends.
Possible thing to do, I think.
I'm not sure reclustering the index by object type is going to make a
worthwhile difference. Of 2.2m objects in the Linux tree, 320k are
commits. The difference between doing the binary search through all
objects vs. just commits is only 2 iterations more of binary search if
we assume the per-type ranges have their own fan-out tables.
The main reason to group objects by type is to make it possible to
create another sha1->something mapping for a particular object type,
without wasting space for storing sha-1 keys again. For example, we
can store commit caches, tree caches... at the end of the index as
extensions.
Using ordinal position in the pack also works, and doesn't require
clustering objects by type.
From: Jeff King <hidden> Date: 2016-06-15 22:54:53
On Thu, Sep 27, 2012 at 10:45:32AM -0700, Shawn O. Pearce wrote:
On 2012-08-12 Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
Long term we might gain slight lookup speedup if we know object type
as search region is made smaller. But for that to happen, we need to
propagate object type hint down to find_pack_entry_one() and friends.
Possible thing to do, I think.
I'm not sure reclustering the index by object type is going to make a
worthwhile difference. Of 2.2m objects in the Linux tree, 320k are
commits. The difference between doing the binary search through all
objects vs. just commits is only 2 iterations more of binary search if
we assume the per-type ranges have their own fan-out tables.
To me the big win would be implicit indexing for items that are present
for every instance of a particular object type. So if we wanted to keep
the timestamp for every commit, you could have a "pack-*.timestamps"
that is literally just a packed list of uint32's, one per commit, where
the position of a commit's timestamp in the list is the same as its
position in the index of sha1s in the pack index.
That's simple to do if your index is just commits. But if it includes
all objects, then your list is sparse. So either you waste space by
making an empty slot for the non-commit objects, or you have an extra
level of indirection mapping the commit into the packed list, which is
going to double the storage in this case (though you could reuse that
extra mapping for the parent, generation number, etc, so it at least
gets amortized as you store more data). Or is there some clever solution
I'm missing?
For your extension, I don't think it matters. You're sparse even in the
commit-object space, so you have to store the mapping anyway. And your
data is big enough that the overhead isn't too painful.
-Peff
On Fri, Sep 28, 2012 at 12:39 AM, Jeff King [off-list ref] wrote:
On Thu, Sep 27, 2012 at 08:51:51AM -0700, Shawn O. Pearce wrote:
quoted
On Thu, Sep 27, 2012 at 5:17 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
I'd like to see some sort of extension mechanism like in
$GIT_DIR/index, so that we don't have to increase pack index version
often. What I have in mind is optional commit cache to speed up
rev-list and merge, which could be stored in pack index too.
On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce [off-list ref] wrote:
In Linus' Linux kernel tree there are currently about 323,178 commits.
If we store just the pre-parsed commit time as an int32 field this is
an additional 1.2 MiB of data in the pack-*.idx file, assuming we can
use additional data like pack offset position to correlate commit to
the parsed int. If we stored parent pointers in a similar way you
probably need at least 3.6 MiB of additional disk space on the index.
For example, use 12 bytes for each commit to store enough of the
parsed commit time to sort commits, and up to 2 parent pointers per
commit.... with a reserved magic value for octopus merges to mean the
commit itself has to be parsed to get the graph structure correct.
This is much better than my naive approach (storing sha-1 and
timestamps). We could use less space by storing parent pointer of
non-merge commits only. Merge commits linux-2.6 is 6% the number of
commits. git.git has higher percentage, 21%. I bet many projects do
not merge as much and the number of merge commits is less than 5%.
--
Duy
On Thu, Sep 27, 2012 at 7:14 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce [off-list ref] wrote:
quoted
In Linus' Linux kernel tree there are currently about 323,178 commits.
If we store just the pre-parsed commit time as an int32 field this is
an additional 1.2 MiB of data in the pack-*.idx file, assuming we can
use additional data like pack offset position to correlate commit to
the parsed int. If we stored parent pointers in a similar way you
probably need at least 3.6 MiB of additional disk space on the index.
For example, use 12 bytes for each commit to store enough of the
parsed commit time to sort commits, and up to 2 parent pointers per
commit.... with a reserved magic value for octopus merges to mean the
commit itself has to be parsed to get the graph structure correct.
This is much better than my naive approach (storing sha-1 and
timestamps). We could use less space by storing parent pointer of
non-merge commits only. Merge commits linux-2.6 is 6% the number of
commits. git.git has higher percentage, 21%. I bet many projects do
not merge as much and the number of merge commits is less than 5%.
Some projects merge quite often. Android's frameworks/base repository
has a very large number of merges. Out of 79905 commits reachable from
the master branch, 65.3% are merges. So actually there are more merge
commits in the Android history than there are code commits. A cache of
only non-merges may be worthless on such a history.
On Mon, Oct 1, 2012 at 8:49 AM, Shawn Pearce [off-list ref] wrote:
On Thu, Sep 27, 2012 at 7:14 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce [off-list ref] wrote:
quoted
In Linus' Linux kernel tree there are currently about 323,178 commits.
If we store just the pre-parsed commit time as an int32 field this is
an additional 1.2 MiB of data in the pack-*.idx file, assuming we can
use additional data like pack offset position to correlate commit to
the parsed int. If we stored parent pointers in a similar way you
probably need at least 3.6 MiB of additional disk space on the index.
For example, use 12 bytes for each commit to store enough of the
parsed commit time to sort commits, and up to 2 parent pointers per
commit.... with a reserved magic value for octopus merges to mean the
commit itself has to be parsed to get the graph structure correct.
This is much better than my naive approach (storing sha-1 and
timestamps). We could use less space by storing parent pointer of
non-merge commits only. Merge commits linux-2.6 is 6% the number of
commits. git.git has higher percentage, 21%. I bet many projects do
not merge as much and the number of merge commits is less than 5%.
Some projects merge quite often. Android's frameworks/base repository
has a very large number of merges. Out of 79905 commits reachable from
the master branch, 65.3% are merges. So actually there are more merge
commits in the Android history than there are code commits. A cache of
only non-merges may be worthless on such a history.
The good thing about these cache is it's configurable. Merge-preferred
projects can choose to cache the first two parents. Non-merge projects
can choose to cache just the first parent. We don't need a fixed
format for both.
--
Duy
On Sun, Sep 30, 2012 at 7:05 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
On Mon, Oct 1, 2012 at 8:49 AM, Shawn Pearce [off-list ref] wrote:
quoted
On Thu, Sep 27, 2012 at 7:14 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
On Thu, Sep 27, 2012 at 10:51 PM, Shawn Pearce [off-list ref] wrote:
quoted
In Linus' Linux kernel tree there are currently about 323,178 commits.
If we store just the pre-parsed commit time as an int32 field this is
an additional 1.2 MiB of data in the pack-*.idx file, assuming we can
use additional data like pack offset position to correlate commit to
the parsed int. If we stored parent pointers in a similar way you
probably need at least 3.6 MiB of additional disk space on the index.
For example, use 12 bytes for each commit to store enough of the
parsed commit time to sort commits, and up to 2 parent pointers per
commit.... with a reserved magic value for octopus merges to mean the
commit itself has to be parsed to get the graph structure correct.
This is much better than my naive approach (storing sha-1 and
timestamps). We could use less space by storing parent pointer of
non-merge commits only. Merge commits linux-2.6 is 6% the number of
commits. git.git has higher percentage, 21%. I bet many projects do
not merge as much and the number of merge commits is less than 5%.
Some projects merge quite often. Android's frameworks/base repository
has a very large number of merges. Out of 79905 commits reachable from
the master branch, 65.3% are merges. So actually there are more merge
commits in the Android history than there are code commits. A cache of
only non-merges may be worthless on such a history.
The good thing about these cache is it's configurable. Merge-preferred
projects can choose to cache the first two parents. Non-merge projects
can choose to cache just the first parent. We don't need a fixed
format for both.
Git has enough magic switches. It doesn't need yet another magic
switch that one group of users needs to set, and another can safely
ignore because their project's usage just happens to align with Linus
Torvald's current world view.
On Mon, Oct 1, 2012 at 9:27 AM, Shawn Pearce [off-list ref] wrote:
Git has enough magic switches. It doesn't need yet another magic
switch that one group of users needs to set, and another can safely
ignore because their project's usage just happens to align with Linus
Torvald's current world view.
I see it as tuning, not switching. It's like setting the number of
commits where bitmaps are taken. We can see the commit cache as a
table, where columns are commit properties. We have a column for date,
one for the first parent. Users can choose to have a third column for
the second parent, or another one for root tree sha-1. The
implementation could be made generic to support caching any <n>
sha1-columns.
--
Duy