]> source.dussan.org Git - jgit.git/commit
Use a bucket sort for PackReverseIndex. 54/14154/3
authorColby Ranger <cranger@google.com>
Fri, 28 Jun 2013 17:37:56 +0000 (10:37 -0700)
committerColby Ranger <cranger@google.com>
Mon, 1 Jul 2013 16:23:29 +0000 (09:23 -0700)
commit6cc532a43cf28403cb623d3df8600a2542a40a43
tree52683fa02a85b513a7af0a92e8f70d045f56a0fd
parent903fb9c7395cc45b5e8c98948c3a627c0bcc01d9
Use a bucket sort for PackReverseIndex.

Previously it took 1200ms to create a reverse index (sorted by offset).
Using a simple bucket sort algorithm, that time is reduced to 450ms.
The bucket index into the offset array is kept, in order to decrease
the binary search window.

Don't keep a copy of the offsets. Instead, use nth position
to lookup the offset in the PackIndex.

Change-Id: If51ab76752622e04a4430d9a14db95ad02f5329d
org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackReverseIndex.java