Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack

From: Andreas Ericsson <ae@op5.se>
Date: Jul 14, 2008, 12:51 UTC
Message-ID: <487B4BD8.5030208@op5.se>
In-Reply-To: <alpine.DEB.1.00.0807141322140.8950@racer>

Johannes Schindelin wrote:

Show 20 quoted lines

> Hi,
> 
> On Mon, 14 Jul 2008, Andreas Ericsson wrote:
> 
>> Sorry for being clueless here, but why does the older versions need
>> to be kept in-memory anyway? Aren't we applying the delta each time
>> we find one, repeatedly creating a new base-object in-memory for
>> each delta? If we aren't doing that, why do we need more than just
>> a small amount of memory just for keeping the delta?
> 
> Think of a delta chain of 49 delta objects, 1 base object.  Now 
> reconstruct all of the objects.
> 
> If you do it one by one, not storing the intermediate results, you end up 
> applying 1 delta for the first, 2 for the second (first the first, then 
> the second), and so on, in total 1 + 2 + 3 + ... + 49 = 49 * 50 / 2 = 1225 
> times.
> 
> Compare that to the 49 times when reusing the intermediate results.
>

That's only true if you discard the result of applying D1 to DB though. What I'm wondering is; Why isn't it done like this (pseudo-code):

while (delta = find_earlier_delta(sha1)) {
	if (is_base_object(delta)) {
		base_object = delta;
		break;
	}
	push_delta(delta, patch_stack);
}

while (pop_delta(patch_stack))
	apply_delta(base_object, delta);

where "apply_delta" replaces the base_object->blob with the delta applied, releasing the previously used memory?

That way, you'll never use more memory than the largest ever size of the object + 1 delta at a time and still not apply the delta more than delta_chain_length-1 times.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231