Re: [PATCH] git-pack-objects: cache small deltas between big objects

From: Martin Koegler <mkoegler@auto.tuwien.ac.at>
Date: May 21, 2007, 17:59 UTC
Message-ID: <20070521175950.GA13818@auto.tuwien.ac.at>
In-Reply-To: <56b7f5510705202135s8c9cd9qf4489b2b5bb2e264@mail.gmail.com>

On Sun, May 20, 2007 at 09:35:56PM -0700, Dana How wrote:

Show 7 quoted lines

> On 5/20/07, Martin Koegler <mkoegler@auto.tuwien.ac.at> wrote:
> >Creating deltas between big blobs is a CPU and memory intensive task.
> >In the writing phase, all (not reused) deltas are redone.
> 
> Actually,  just the ones selected,  which is approx 1/window.
> Do you have any numbers describing the effects on runtime
> and memory size for a known repo like linux-2.6?

Objects below 1 MB are not considered for caching. 
The linux kernel has only such objects:
linux.git$ find -size +1000k |grep -v ".git"|wc
      0       0       0
So no caching happens. The required memory is only increased by the
new pointer in object_entry.

At runtime, we have additional (#object)*(window size+1) null pointer checks, (#objects)*(window size) pointer initialiations with zero and check (#objects)*(window size) times the caching policy check: ((src_size

>> 20) + (trg_size >> 21) > (delta_size >> 10))

Writing a cached delta is faster, as we avoid creating a delta. Some calls to free are delayed.

Show 11 quoted lines

> >This patch adds support for caching deltas from the deltifing phase, so
> >that that the writing phase is faster.
> >
> >The caching is limited to small deltas to avoid increasing memory usage 
> >very much.
> >The implemented limit is (memory needed to create the delta)/1024.
> 
> Your limit is applied per-object,  and there is no overall limit
> on the amount of memory not freed in the delta phase.
> I suspect this caching would be disastrous for the large repo
> with "megablobs" I'm trying to wrestle with at the moment.

http://www.spinics.net/lists/git/msg31241.html:

Show 5 quoted lines

> At the moment I'm experimenting on a git repository with
> a 4.5GB checkout,  and 18 months of history in 4K commits
> comprising 100GB (uncompressed) of blobs stored in
> 7 packfiles of 2GB or less. Hopefully I'll be able to say
> more about tweaking packing shortly.

I you have 100 GB of uncompressed data in your pack files, the cache limit is between 100MB and 200MB with the current policy.

The aim of my patch is to speed up pack writing without increasing memory usage very much, if you have blobs of some hundred MB size in your repository.

The caching policy could be extended to speed more memory on caching other deltas. Ideas on this topic are welcome.

mfg Martin Kögler
PS: If you are trying to optimize packing speed/size, you could test
the following patch: http://marc.info/?l=git&m=117908942525171&w=2