From: Andreas Ericsson <ae@op5•se>
To: Johannes Schindelin <Johannes.Schindelin@gmx•de>
Cc: Jakub Narebski <jnareb@gmail•com>,
"Shawn O. Pearce" <spearce@spearce•org>,
Nicolas Pitre <nico@cam•org>, Junio C Hamano <gitster@pobox•com>,
git@vger•kernel.org, Stephan Hennig <mailing_list@arcor•de>
Subject: Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack
Date: Mon, 14 Jul 2008 14:51:36 +0200 [thread overview]
Message-ID: <487B4BD8.5030208@op5.se> (raw)
In-Reply-To: <alpine.DEB.1.00.0807141322140.8950@racer>
Johannes Schindelin wrote:
> 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
next prev parent reply other threads:[~2008-07-14 12:54 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-07-10 14:40 git pull is slow Stephan Hennig
2008-07-10 15:13 ` Martin Langhoff
2008-07-10 15:28 ` Petr Baudis
2008-07-10 15:30 ` Johannes Sixt
2008-07-10 15:45 ` Stephan Hennig
2008-07-10 15:50 ` Petr Baudis
2008-07-10 17:44 ` Stephan Hennig
2008-07-11 12:25 ` Stephan Hennig
2008-07-11 13:34 ` Andreas Ericsson
2008-07-11 14:04 ` Johannes Schindelin
2008-07-12 12:32 ` Stephan Hennig
2008-07-12 17:05 ` Johannes Schindelin
2008-07-13 1:15 ` Shawn O. Pearce
2008-07-13 13:59 ` Johannes Schindelin
2008-07-13 22:11 ` Shawn O. Pearce
2008-07-14 2:07 ` [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack Shawn O. Pearce
2008-07-14 2:27 ` Nicolas Pitre
2008-07-14 3:12 ` Shawn O. Pearce
2008-07-14 11:44 ` Johannes Schindelin
2008-07-14 11:54 ` Jakub Narebski
2008-07-14 12:10 ` Johannes Schindelin
2008-07-14 12:16 ` Andreas Ericsson
2008-07-14 12:25 ` Johannes Schindelin
2008-07-14 12:51 ` Andreas Ericsson [this message]
2008-07-14 12:58 ` Johannes Schindelin
2008-07-15 2:21 ` Nicolas Pitre
2008-07-15 2:47 ` Shawn O. Pearce
2008-07-15 3:06 ` Nicolas Pitre
2008-07-17 16:06 ` Stephan Hennig
2008-07-17 16:25 ` Nicolas Pitre
2008-07-17 21:35 ` Shawn O. Pearce
2008-07-17 22:02 ` [RFC PATCH] index-pack: Issue a warning if deltaBaseCacheLimit is too small Shawn O. Pearce
2008-07-17 23:45 ` Nicolas Pitre
2008-07-15 4:19 ` [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack Shawn O. Pearce
2008-07-14 2:07 ` [PATCH 1/4] index-pack: Refactor base arguments of resolve_delta into a struct Shawn O. Pearce
2008-07-15 2:40 ` Nicolas Pitre
2008-07-14 2:07 ` [PATCH 2/4] index-pack: Chain the struct base_data on the stack for traversal Shawn O. Pearce
2008-07-15 2:48 ` Nicolas Pitre
2008-07-14 2:07 ` [PATCH 3/4] index-pack: Track the object_entry that creates each base_data Shawn O. Pearce
2008-07-14 10:15 ` Johannes Schindelin
2008-07-15 2:50 ` Nicolas Pitre
2008-07-15 3:20 ` Shawn O. Pearce
2008-07-15 3:42 ` Nicolas Pitre
2008-07-14 2:07 ` [PATCH 4/4] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas Shawn O. Pearce
2008-07-15 3:05 ` Nicolas Pitre
2008-07-15 3:18 ` Shawn O. Pearce
2008-07-15 4:45 ` [PATCH v2] " Shawn O. Pearce
2008-07-15 5:05 ` Nicolas Pitre
2008-07-15 18:48 ` Junio C Hamano
2008-07-13 9:01 ` git pull is slow Stephan Hennig
2008-07-11 12:55 ` Stephan Hennig
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=487B4BD8.5030208@op5.se \
--to=ae@op5$(echo .)se \
--cc=Johannes.Schindelin@gmx$(echo .)de \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=jnareb@gmail$(echo .)com \
--cc=mailing_list@arcor$(echo .)de \
--cc=nico@cam$(echo .)org \
--cc=spearce@spearce$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox