diff options
| author | Shawn O. Pearce <spearce@spearce.org> | 2010-11-04 19:01:51 -0700 |
|---|---|---|
| committer | Shawn O. Pearce <spearce@spearce.org> | 2010-11-12 14:01:28 -0800 |
| commit | e7e9a47b5222fd3dd1f989c413f4220444ecb23d (patch) | |
| tree | 652bb67529561c705f89ef7fc4e82731dbb5469f | |
| parent | 2b0df15f7f1bdcfc41349c478319fad50158c183 (diff) | |
| download | jgit-e7e9a47b5222fd3dd1f989c413f4220444ecb23d.tar.gz jgit-e7e9a47b5222fd3dd1f989c413f4220444ecb23d.zip | |
Remove unnecessary note fanout when removing notes
Fanout level notes trees are combined back together into a flat leaf
level tree if during a removal of a subtree there are less than 3/4 of
the fanout subtrees still existing, and the size of the combined leaf
is under the 256 split limit noted above.
This rule is used because deletes are less common than insertions, and
SHA-1's relatively uniform distribution suggests that with only 192
subtrees existing in the fanout, there should be approximately 192
names in the combined replacement leaf tree.
Change-Id: Ia9d145ffd5454982509fc40906bc4dbbf2b13952
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
3 files changed, 49 insertions, 0 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java index ae34938eec..e1b96eaae9 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java @@ -159,6 +159,33 @@ class FanoutBucket extends InMemoryNoteBucket { } @Override + int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException { + // If most of this fan-out is full, estimate it should still be split. + if (LeafBucket.MAX_SIZE * 3 / 4 <= cnt) + return 1 + LeafBucket.MAX_SIZE; + + // Due to the uniform distribution of ObjectIds, having less nodes full + // indicates a good chance the total number of children below here + // is less than the MAX_SIZE split point. Get a more accurate count. + + MutableObjectId id = new MutableObjectId(); + id.fromObjectId(noteOn); + + int sz = 0; + for (int cell = 0; cell < 256; cell++) { + NoteBucket b = table[cell]; + if (b == null) + continue; + + id.setByte(prefixLen >> 1, cell); + sz += b.estimateSize(id, or); + if (LeafBucket.MAX_SIZE < sz) + break; + } + return sz; + } + + @Override InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData, ObjectReader or) throws IOException { int cell = cell(noteOn); @@ -182,6 +209,15 @@ class FanoutBucket extends InMemoryNoteBucket { if (cnt == 0) return null; + if (estimateSize(noteOn, or) < LeafBucket.MAX_SIZE) { + // We are small enough to just contract to a single leaf. + InMemoryNoteBucket r = new LeafBucket(prefixLen); + for (Iterator<Note> i = iterator(noteOn, or); i.hasNext();) + r = r.append(i.next()); + r.nonNotes = nonNotes; + return r; + } + return this; } else if (n != b) { @@ -269,6 +305,11 @@ class FanoutBucket extends InMemoryNoteBucket { } @Override + int estimateSize(AnyObjectId objId, ObjectReader or) throws IOException { + return load(objId, or).estimateSize(objId, or); + } + + @Override InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData, ObjectReader or) throws IOException { return load(noteOn, or).set(noteOn, noteData, or); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java index 068a4c24c8..af6c6f455e 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java @@ -129,6 +129,11 @@ class LeafBucket extends InMemoryNoteBucket { }; } + @Override + int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException { + return cnt; + } + InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData, ObjectReader or) throws IOException { int p = search(noteOn); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java index e13067cc12..defc37dbec 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java @@ -64,6 +64,9 @@ abstract class NoteBucket { abstract Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader) throws IOException; + abstract int estimateSize(AnyObjectId noteOn, ObjectReader or) + throws IOException; + abstract InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData, ObjectReader reader) throws IOException; |