Re: [BAD PATCH 0/9] v4-aware tree walker API

From: Duy Nguyen <pclouds@gmail.com>
Date: Oct 11, 2013, 12:22 UTC
Message-ID: <20131011122259.GA7776@lanh>
In-Reply-To: <alpine.LFD.2.03.1310091137310.3023@syhkavp.arg>

On Wed, Oct 09, 2013 at 12:51:26PM -0400, Nicolas Pitre wrote:

Show 18 quoted lines

> Now let's mitigate the deep delta chaining effect in the tree encoding:
> 
> $ rm .git/objects/pack/pack-foo.*
> $ ../../git/test-packv4 --min-tree-copy=50 orig/pack-*.pack .git/objects/pack/pack-foo.pack
> Scanning objects: 100% (162785/162785), done.
> Writing objects: 100% (162785/162785), done.
> $ time git rev-list --objects --all > /dev/null
> 
> real    0m9.451s
> user    0m9.393s
> sys     0m0.036s
> 
> Using --min-tree-copy=50 produces a pack which is still smaller than 
> pack v2 but any tree copy sequence must refer to a minimum of 50 
> entries.  This significantly reduces the CPU usage in decode_entries() 
> by reducing the needless chaining effect I mentioned here:
> 
> http://article.gmane.org/gmane.comp.version-control.git/234975

Yeah I was frustrated and did not think about trying --min-tree-copy.

Show 6 quoted lines

> So, there are 2 conclusions here:
> 
> 1: The current tree delta euristic is inefficient for pack v4.
> 
> 2- Something must be very wrong in your latest patches as they make it
>    close to 3 times more expensive than without them.

For one I know that get_tree_offset_cache() is called a lot more with the new API. I do rev-list on v1.8.4. With compatibility layer on, it's 211m calls (*). With new API it's 655m calls. The new API is basically do decode_entries() on every tree_entry() call. Perhaps I screwed up something in decode_entries() itself..

(*) for 15m tree entries, 211m are a lot of calls, which might translate to a lot of copy sequences..

Show 7 quoted lines

> > Maybe we could make an exception and allow the tree walker to pass
> > pv4_tree_cache* directly to decode_entries so it does not need to do
> > the first lookup every time..
> > 
> > Suggestions?
> 
> I'll try to have a look at your patches in more details soon.

Shameful fixup (though it does not seem to impact the timing)

diff --git a/packv4-parse.c b/packv4-parse.c
index 6f6152c..9d7589e 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -825,8 +825,8 @@ static struct object **get_packed_objs(struct pv4_tree_desc *desc)
 	if (!desc->p || !desc->sha1_index)
 		return NULL;
 	if (desc->p->version >= 4 && !desc->p->objs)
-		desc->p->objs =
-			xmalloc(sizeof(struct object *) * desc->p->num_objects);
+		desc->p->objs = xcalloc(desc->p->num_objects,
+					sizeof(struct object *));
 	return desc->p->objs;
 }