]> source.dussan.org Git - jgit.git/commit
Support creating pack bitmap indexes in PackWriter. 40/7940/18
authorColby Ranger <cranger@google.com>
Mon, 6 Aug 2012 18:09:53 +0000 (11:09 -0700)
committerColby Ranger <cranger@google.com>
Tue, 5 Mar 2013 19:14:45 +0000 (11:14 -0800)
commitdafcb8f6db82b899c917832768f1c240d273190c
tree96ff22dbf1b95b3bdad4ce9f2f1614ffddd83088
parent3b325917a5c928caadd88a0ec718b1632f088fd5
Support creating pack bitmap indexes in PackWriter.

Update the PackWriter to support writing out pack bitmap indexes,
a parallel ".bitmap" file to the ".pack" file.
Bitmaps are selected at commits every 1 to 5,000 commits for
each unique path from the start. The most recent 100 commits are
all bitmapped. The next 19,000 commits have a bitmaps every 100
commits. The remaining commits have a bitmap every 5,000 commits.
Commits with more than 1 parent are prefered over ones
with 1 or less. Furthermore, previously computed bitmaps are reused,
if the previous entry had the reuse flag set, which is set when the
bitmap was placed at the max allowed distance.

Bitmaps are used to speed up the counting phase when packing, for
requests that are not shallow. The PackWriterBitmapWalker uses
a RevFilter to proactively mark commits with RevFlag.SEEN, when
they appear in a bitmap. The walker produces the full closure
of reachable ObjectIds, given the collection of starting ObjectIds.

For fetch request, two ObjectWalks are executed to compute the
ObjectIds reachable from the haves and from the wants. The
ObjectIds needed to be written are determined by taking all the
resulting wants AND NOT the haves.

For clone requests, we get cached pack support for "free" since
it is possible to determine if all of the ObjectIds in a pack file
are included in the resulting list of ObjectIds to write.

On my machine, the best times for clones and fetches of the linux
kernel repository (with about 2.6M objects and 300K commits) are
tabulated below:

Operation                   Index V2               Index VE003
Clone                       37530ms (524.06 MiB)     82ms (524.06 MiB)
Fetch (1 commit back)          75ms                 107ms
Fetch (10 commits back)       456ms (269.51 KiB)    341ms (265.19 KiB)
Fetch (100 commits back)      449ms (269.91 KiB)    337ms (267.28 KiB)
Fetch (1000 commits back)    2229ms ( 14.75 MiB)    189ms ( 14.42 MiB)
Fetch (10000 commits back)   2177ms ( 16.30 MiB)    254ms ( 15.88 MiB)
Fetch (100000 commits back) 14340ms (185.83 MiB)   1655ms (189.39 MiB)

Change-Id: Icdb0cdd66ff168917fb9ef17b96093990cc6a98d
14 files changed:
org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java [new file with mode: 0644]
org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java
org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java [new file with mode: 0644]
org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java [new file with mode: 0644]