[PATCH] improve depth heuristic for maximum delta size
- From
Nicolas Pitre <nico@cam.org>
- Date
- May 16, 2006, 20:29 UTC
- Message-ID
- <Pine.LNX.4.64.0605161510200.18071@localhost.localdomain>
- In-Reply-To
- <7v4pzqhh3t.fsf@assigned-by-dhcp.cox.net>
This provides a linear decrement on the penalty related to delta depth instead of being an 1/x function. With this another 5% reduction is observed on packs for both the GIT repo and the Linux kernel repo, as well as fixing a pack size regression in another sample repo I have.
Signed-off-by: Nicolas Pitre <nico@cam.org>
---
On Mon, 15 May 2006, Junio C Hamano wrote:
Show 20 quoted lines
> Nicolas Pitre <nico@cam.org> writes: > > > @@ -1038,8 +1038,8 @@ static int try_delta(struct unpacked *tr > > > > /* Now some size filtering euristics. */ > > size = trg_entry->size; > > - max_size = size / 2 - 20; > > - if (trg_entry->delta) > > + max_size = (size/2 - 20) / (src_entry->depth + 1); > > + if (trg_entry->delta && trg_entry->delta_size <= max_size) > > max_size = trg_entry->delta_size-1; > > src_size = src_entry->size; > > sizediff = src_size < size ? size - src_size : 0; > > At the first glance, this seems rather too agressive. It makes > me wonder if it is a good balance to penalize the second > generation base by requiring it to produce a small delta that is > at most half as we normally would (and the third generation a > third), or maybe the penalty should kick in more gradually, like > e.g. ((max_depth * 2 - src_entry->depth) / (max_depth * 2).
You are right. However your formula converge towards 0.5 which is not enough to be sure the bad effect with early eviction of max depth object from the object window won't come back. I prefer this patch with a formula converging toward 0.
diff --git a/pack-objects.c b/pack-objects.c index 566a2a2..3116020 100644 --- a/pack-objects.c +++ b/pack-objects.c @@ -1036,9 +1036,12 @@ static int try_delta(struct unpacked *tr if (src_entry->depth >= max_depth) return 0; - /* Now some size filtering euristics. */ + /* Now some size filtering heuristics. */ size = trg_entry->size; - max_size = (size/2 - 20) / (src_entry->depth + 1); + max_size = size/2 - 20; + max_size = max_size * (max_depth - src_entry->depth) / max_depth; + if (max_size == 0) + return 0; if (trg_entry->delta && trg_entry->delta_size <= max_size) max_size = trg_entry->delta_size-1; src_size = src_entry->size;