[PATCH 0/6 (v2)] Suggested for PU: revision caching system to significantly speed up packing/walking

SUGGESTED FOR 'PU': (patchset v2)

Traversing objects is currently very costly, as every commit and tree must be 
loaded and parsed.  Much time and energy could be saved by caching metadata and 
topological info in an efficient, easily accessible manner.  Furthermore, this 
could improve git's interfacing potential, by providing a condensed summary of 
a repository's commit tree.

This is a series to implement such a revision caching mechanism, aptly named 
rev-cache.  The series will provide:
 - a core API to manipulate and traverse caches
 - an integration into the internal revision walker
 - a porcelain front-end providing access to users and (shell) applications
 - a series of tests to verify/demonstrate correctness
 - documentation of the API, porcelain and core concepts

In cold starts rev-cache has sped up packing and walking by a factor of 4, and 
over twice that on warm starts.  Some times on slax for the linux repository:

rev-list --all --objects >/dev/null
 default
   cold    1:13
   warm    0:43
 rev-cache'd
   cold    0:19
   warm    0:02

pack-objects --revs --all --stdout >/dev/null
 default
   cold    2:44
   warm    1:21
 rev-cache'd
   cold    0:44
   warm    0:10

The mechanism is minimally intrusive: most of the changes take place in 
seperate files, and only a handful of git's existing functions are modified.

Hope you find this useful.

 - Nick

---
This is a revised patchset; the biggest changes are:
 - elimination of python dependency
 - revision of documentation
 - addition of name caching (patch 6)

 Documentation/git-rev-cache.txt       |   96 ++
 Documentation/technical/rev-cache.txt |  379 ++++++
 Makefile                              |    2 +
 blob.c                                |    1 +
 blob.h                                |    2 +
 builtin-rev-cache.c                   |  309 +++++
 builtin.h                             |    1 +
 commit.c                              |    3 +
 commit.h                              |    2 +
 git.c                                 |    1 +
 list-objects.c                        |   49 +-
 rev-cache.c                           | 2041 +++++++++++++++++++++++++++++++++
 revision.c                            |   89 ++-
 revision.h                            |   47 +-
 t/t6015-rev-cache-list.sh             |  246 ++++
 tree.h                                |    1 +
 16 files changed, 3244 insertions(+), 25 deletions(-)
 create mode 100755 Documentation/git-rev-cache.txt
 create mode 100755 Documentation/technical/rev-cache.txt
 create mode 100755 builtin-rev-cache.c
 create mode 100755 rev-cache.c
 create mode 100755 t/t6015-rev-cache-list.sh

Well crap, in my infinite wisdom I replied with the final updated
patchset to the wrong version :-/  I don't want to clog up the list
with my stupid mistakes, but if you need me to I can resend them to
v3.

But yeah, I've uploaded an updated version.  This patchset:
 - fixes whitespace errors
 - adds _ondisk versions of structures to ensure portability
 - cleans up definitions/fix a typo

Hope it works out for you all.  Sorry about the mismatched reply.

 - Nick

Nick Edelen wrote:

Well crap, in my infinite wisdom I replied with the final updated
patchset to the wrong version :-/  I don't want to clog up the list
with my stupid mistakes, but if you need me to I can resend them to
v3.
  

Heh, that sure reads like a sentence written after midnight :-)

These all say v2, and the last lot was labeled as v3.  And I see an
older submission labeled as v2 (8th August) and got duplicates of those
labeled as v3.

Are the ones attached to this the ones that are the best?

Sam

But yeah, I've uploaded an updated version.  This patchset:
 - fixes whitespace errors
 - adds _ondisk versions of structures to ensure portability
 - cleans up definitions/fix a typo

Hope it works out for you all.  Sorry about the mismatched reply.

 - Nick
  

Heh, that sure reads like a sentence written after midnight :-)

These all say v2, and the last lot was labeled as v3.  And I see an
older submission labeled as v2 (8th August) and got duplicates of those
labeled as v3.

Are the ones attached to this the ones that are the best?

Yeah, the latest ones Re: v2, uploaded a few hours ago, are the best.
They should be Re: v3 but they're not...  If I'm being confusing I can
just upload them to v3, but I didn't want to bombard everyone with
duplicates.

Hi,

On Mon, 17 Aug 2009, Nick Edelen wrote:

If I'm being confusing I can just upload them to v3, but I didn't want 
to bombard everyone with duplicates.

I think by now people _are_ confused, so it's probably better to "bomb" 
everyone with a clean current version of your patch series.

Although I have to admit that I am scared away by the sheer size of the 
individual patches (together with bad feelings from earlier discussions 
that I want to avoid).

Ciao,
Dscho