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

1 files changed, 4 insertions, 0 deletions

diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 28e0a4cc67..18f33147ce 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -25,10 +25,13 @@ badSectionEntry=Bad section entry: {0}
 bareRepositoryNoWorkdirAndIndex=Bare Repository has neither a working tree, nor an index
 base64InputNotProperlyPadded=Base64 input not properly padded.
 baseLengthIncorrect=base length incorrect
+bitmapMissingObject=Bitmap at {0} is missing {1}.
+bitmapsMustBePrepared=Bitmaps must be prepared before they may be written.
 blameNotCommittedYet=Not Committed Yet
 blobNotFound=Blob not found: {0}
 blobNotFoundForPath=Blob not found: {0} for path: {1}
 branchNameInvalid=Branch name {0} is not allowed
+buildingBitmaps=Building bitmaps
 cachedPacksPreventsIndexCreation=Using cached packs prevents index creation
 cachedPacksPreventsListingObjects=Using cached packs prevents listing objects
 cannotBeCombined=Cannot be combined.
@@ -426,6 +429,7 @@ rewinding=Rewinding to commit {0}
 searchForReuse=Finding sources
 searchForSizes=Getting sizes
 secondsAgo={0} seconds ago
+selectingCommits=Selecting commits
 sequenceTooLargeForDiffAlgorithm=Sequence too large for difference algorithm.
 serviceNotEnabledNoName=Service not enabled
 serviceNotPermitted={0} not permitted