[PATCH v1] WIP unpack-trees: avoid duplicate ODB lookups during checkout

[PATCH v1] WIP unpack-trees: avoid duplicate ODB lookups during checkout

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Avoid duplicate ODB lookups for trees during traverse_tree_recursive().

I'm marking this WIP so we can talk about the TODO in the
commit message.

Jeff Hostetler (1):
  unpack-trees: avoid duplicate ODB lookups during checkout

 tree-walk.c    |  8 ++++++++
 tree-walk.h    |  1 +
 unpack-trees.c | 13 +++++++++----
 3 files changed, 18 insertions(+), 4 deletions(-)

-- 
2.9.3

[PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[git]

From: Jeff Hostetler <jeffhost@microsoft.com>

Teach traverse_trees_recursive() to not do redundant ODB
lookups when both directories refer to the same OID.

In operations such as read-tree, checkout, and merge when
the differences between the commits are relatively small,
there will likely be many directories that have the same
SHA-1.  In these cases we can avoid hitting the ODB multiple
times for the same SHA-1.

TODO This change is a first attempt to test that by comparing
TODO the hashes of name[i] and name[i-i] and simply copying
TODO the tree-descriptor data.  I was thinking of the n=2
TODO case here.  We may want to extend this to the n=3 case.

================
On the Windows repo (500K trees, 3.1M files, 450MB index),
this reduced the overall time by 0.75 seconds when cycling
between 2 commits with a single file difference.

(avg) before: 22.699
(avg) after:  21.955
===============

================
Using the p0004-read-tree test (posted earlier this week)
with 1M files on Linux:

before:
$ ./p0004-read-tree.sh
0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)
0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)

after:
$ ./p0004-read-tree.sh
0004.5: switch work1 work2 (1003037)       11.17(7.84+2.76)
0004.6: switch commit aliases (1003037)    11.13(7.82+2.72)
================

Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
---
 tree-walk.c    |  8 ++++++++
 tree-walk.h    |  1 +
 unpack-trees.c | 13 +++++++++----
 3 files changed, 18 insertions(+), 4 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index ff77605..3b82f0e 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -92,6 +92,14 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
 	return buf;
 }
 
+void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src)
+{
+	void *buf = xmalloc(src->size);
+	memcpy(buf, src->buffer, src->size);
+	init_tree_desc(dest, buf, src->size);
+	return buf;
+}
+
 static void entry_clear(struct name_entry *a)
 {
 	memset(a, 0, sizeof(*a));
diff --git a/tree-walk.h b/tree-walk.h
index 68bb78b..ca4032b 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -43,6 +43,7 @@ int tree_entry(struct tree_desc *, struct name_entry *);
 int tree_entry_gently(struct tree_desc *, struct name_entry *);
 
 void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);
+void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src);
 
 struct traverse_info;
 typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);
diff --git a/unpack-trees.c b/unpack-trees.c
index 3a8ee19..50aacad 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -554,10 +554,15 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
 	newinfo.df_conflicts |= df_conflicts;
 
 	for (i = 0; i < n; i++, dirmask >>= 1) {
-		const unsigned char *sha1 = NULL;
-		if (dirmask & 1)
-			sha1 = names[i].oid->hash;
-		buf[i] = fill_tree_descriptor(t+i, sha1);
+		if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&
+			!hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {
+			buf[i] = copy_tree_descriptor(&t[i], &t[i-1]);
+		} else {
+			const unsigned char *sha1 = NULL;
+			if (dirmask & 1)
+				sha1 = names[i].oid->hash;
+			buf[i] = fill_tree_descriptor(t+i, sha1);
+		}
 	}
 
 	bottom = switch_cache_bottom(&newinfo);
-- 
2.9.3

Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[Stefan Beller]

On Thu, Apr 6, 2017 at 1:37 PM,  <git@jeffhostetler.com> wrote:
> From: Jeff Hostetler <jeffhost@microsoft.com>
>
> Teach traverse_trees_recursive() to not do redundant ODB
> lookups when both directories refer to the same OID.

And the reason for this is that omitting the second lookup
saves time, i.e. a lookup in the ODB of a sufficiently large
repo is slow.

My kneejerk line of thinking:
* yes, it sounds good to reduce the number of ODB accesses.
* But if we consider ODB lookups to be slow and we perform
  a structured access, how about a cache in front of the ODB?
* We already have that! (sort of..) 9a414486d9 (lookup_object:
  prioritize recently found objects, 2013-05-01)
* Instead of improving the caching, maybe change the
  size of the problem: We could keep the objects of different types
  in different hash-tables.

object.c has its own hash table, I presume for historical and
performance reasons, this would be split up to multiple hash
tables.

Additionally to "object *lookup_object(*sha1)", we'd have
a function

"object *lookup_object(*sha1, enum object_type hint)"
which looks into the correct the hash table.

If you were to call just  lookup_object with no hint, then you'd
look into all the different tables (I guess there is a preferrable
order in which to look, haven't thought about that).

>
> In operations such as read-tree, checkout, and merge when
> the differences between the commits are relatively small,
> there will likely be many directories that have the same
> SHA-1.  In these cases we can avoid hitting the ODB multiple
> times for the same SHA-1.

This would explain partially why there was such a good
performance boost in the referenced commit above as we
implicitly lookup the same object multiple times.

Peff is really into getting this part faster, c.f.
https://public-inbox.org/git/20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net/

> TODO This change is a first attempt to test that by comparing
> TODO the hashes of name[i] and name[i-i] and simply copying
> TODO the tree-descriptor data.  I was thinking of the n=2
> TODO case here.  We may want to extend this to the n=3 case.

>
> ================
> On the Windows repo (500K trees, 3.1M files, 450MB index),
> this reduced the overall time by 0.75 seconds when cycling
> between 2 commits with a single file difference.
>
> (avg) before: 22.699
> (avg) after:  21.955
> ===============

So it shaves off 4% of the time needed. it doesn't sound like a
break through, but I guess these small patches add up. :)

>         for (i = 0; i < n; i++, dirmask >>= 1) {
> -               const unsigned char *sha1 = NULL;
> -               if (dirmask & 1)
> -                       sha1 = names[i].oid->hash;
> -               buf[i] = fill_tree_descriptor(t+i, sha1);
> +               if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&
> +                       !hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {

Why do we need to check for dirmask & 1 here?
This ought to be covered by the hashcmp already IIUC.
So maybe we can pull out the
                         if (dirmask & 1)
                                 sha1 = names[i].oid->hash;
out of the else when dropping that dirmask check?


Thanks,
Stefan

Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[René Scharfe]

Am 06.04.2017 um 22:37 schrieb git@jeffhostetler.com:
> From: Jeff Hostetler <jeffhost@microsoft.com>
> 
> Teach traverse_trees_recursive() to not do redundant ODB
> lookups when both directories refer to the same OID.
> 
> In operations such as read-tree, checkout, and merge when
> the differences between the commits are relatively small,
> there will likely be many directories that have the same
> SHA-1.  In these cases we can avoid hitting the ODB multiple
> times for the same SHA-1.
> 
> TODO This change is a first attempt to test that by comparing
> TODO the hashes of name[i] and name[i-i] and simply copying
> TODO the tree-descriptor data.  I was thinking of the n=2
> TODO case here.  We may want to extend this to the n=3 case.
> 
> ================
> On the Windows repo (500K trees, 3.1M files, 450MB index),
> this reduced the overall time by 0.75 seconds when cycling
> between 2 commits with a single file difference.
> 
> (avg) before: 22.699
> (avg) after:  21.955
> ===============
> 
> ================
> Using the p0004-read-tree test (posted earlier this week)
> with 1M files on Linux:
> 
> before:
> $ ./p0004-read-tree.sh
> 0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)
> 0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)
> 
> after:
> $ ./p0004-read-tree.sh
> 0004.5: switch work1 work2 (1003037)       11.17(7.84+2.76)
> 0004.6: switch commit aliases (1003037)    11.13(7.82+2.72)
> ================
> 
> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---
>   tree-walk.c    |  8 ++++++++
>   tree-walk.h    |  1 +
>   unpack-trees.c | 13 +++++++++----
>   3 files changed, 18 insertions(+), 4 deletions(-)
> 
> diff --git a/tree-walk.c b/tree-walk.c
> index ff77605..3b82f0e 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -92,6 +92,14 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)
>   	return buf;
>   }
>   
> +void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src)
> +{
> +	void *buf = xmalloc(src->size);
> +	memcpy(buf, src->buffer, src->size);
> +	init_tree_desc(dest, buf, src->size);
> +	return buf;
> +}
> +
>   static void entry_clear(struct name_entry *a)
>   {
>   	memset(a, 0, sizeof(*a));
> diff --git a/tree-walk.h b/tree-walk.h
> index 68bb78b..ca4032b 100644
> --- a/tree-walk.h
> +++ b/tree-walk.h
> @@ -43,6 +43,7 @@ int tree_entry(struct tree_desc *, struct name_entry *);
>   int tree_entry_gently(struct tree_desc *, struct name_entry *);
>   
>   void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);
> +void *copy_tree_descriptor(struct tree_desc *dest, const struct tree_desc *src);
>   
>   struct traverse_info;
>   typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);
> diff --git a/unpack-trees.c b/unpack-trees.c
> index 3a8ee19..50aacad 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -554,10 +554,15 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
>   	newinfo.df_conflicts |= df_conflicts;
>   
>   	for (i = 0; i < n; i++, dirmask >>= 1) {
> -		const unsigned char *sha1 = NULL;
> -		if (dirmask & 1)
> -			sha1 = names[i].oid->hash;
> -		buf[i] = fill_tree_descriptor(t+i, sha1);
> +		if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&

Can .oid even be NULL?  (I didn't check, but it's dereferenced in the 
sha1 assignment below, so I guess the answer is no and these two checks 
are not needed.)

> +			!hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {

Calling oidcmp would be shorter.

> +			buf[i] = copy_tree_descriptor(&t[i], &t[i-1]);

buf keeps track of the allocations that need to be freed at the end of 
the function.  I assume these buffers are read-only.  Can you use an 
alias here instead of a duplicate by calling init_tree_desc with the 
predecessor's buffer and setting buf[i] to NULL?  Or even just copying 
t[i - 1] to t[i] with an assignment?  That would be shorter and probably 
also quicker.

> +		} else {
> +			const unsigned char *sha1 = NULL;
> +			if (dirmask & 1)
> +				sha1 = names[i].oid->hash;
> +			buf[i] = fill_tree_descriptor(t+i, sha1);
> +		}
>   	}
>   
>   	bottom = switch_cache_bottom(&newinfo);
> 

Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[Jeff King]

On Thu, Apr 06, 2017 at 03:48:07PM -0700, Stefan Beller wrote:

> On Thu, Apr 6, 2017 at 1:37 PM,  <git@jeffhostetler.com> wrote:
> > From: Jeff Hostetler <jeffhost@microsoft.com>
> >
> > Teach traverse_trees_recursive() to not do redundant ODB
> > lookups when both directories refer to the same OID.
> 
> And the reason for this is that omitting the second lookup
> saves time, i.e. a lookup in the ODB of a sufficiently large
> repo is slow.
> 
> My kneejerk line of thinking:
> * yes, it sounds good to reduce the number of ODB accesses.
> * But if we consider ODB lookups to be slow and we perform
>   a structured access, how about a cache in front of the ODB?
> * We already have that! (sort of..) 9a414486d9 (lookup_object:
>   prioritize recently found objects, 2013-05-01)
> * Instead of improving the caching, maybe change the
>   size of the problem: We could keep the objects of different types
>   in different hash-tables.

I don't think this is using lookup_object() at all, though. It goes
straight to fill_tree_descriptor(), which will read the object contents
from disk. So our time is going to:

  1. Finding the object in the odb (ideally a binary search in a single
     pack index, but less optimal when there are many packs).

  2. Reconstructing the object. This means zlib-inflating from disk, but
     it may also mean delta reconstruction.

I think there _are_ some caches at play here, though, when you look up
the same tree back to back. The pack-mru means that we'll always look in
the correct pack first. And in theory the delta base cache means that
we'll already have the whole thing reconstructed in memory (though I
have often been confused by exactly when we put items into that cache,
so I might be wrong).

So in theory, this is not all that different than the "just allocate and
copy the bytes" optimization that's happening here (though I'm not
surprised that doing it at a higher level can produce some speedup).

I think the more interesting optimization is "just use the same buffer
without bothering to copy", which is hard for the low-level code to do
(since it doesn't know what lifetime the caller is expecting). 

> object.c has its own hash table, I presume for historical and
> performance reasons, this would be split up to multiple hash
> tables.

So I don't think lookup_object() is really relevant here. But I'm also
not sure that multiple hash tables would really buy us much. In theory
hash tables are O(1), so multiple smaller tables doesn't help (and might
hurt, since now we have four O(1) lookups to do). Of course that's a
minor fiction because of collisions, but we keep the load factor on the
object.c table pretty low (and that's why things like quadratic probing
and cuckoo hashing never showed great improvement).

-Peff

Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[Jeff Hostetler]

On 4/7/2017 1:19 AM, Jeff King wrote:
> On Thu, Apr 06, 2017 at 03:48:07PM -0700, Stefan Beller wrote:
>
>> On Thu, Apr 6, 2017 at 1:37 PM,  <git@jeffhostetler.com> wrote:
>>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>>
>>> Teach traverse_trees_recursive() to not do redundant ODB
>>> lookups when both directories refer to the same OID.
>>
>> And the reason for this is that omitting the second lookup
>> saves time, i.e. a lookup in the ODB of a sufficiently large
>> repo is slow.
>>
>> My kneejerk line of thinking:
>> * yes, it sounds good to reduce the number of ODB accesses.
>> * But if we consider ODB lookups to be slow and we perform
>>   a structured access, how about a cache in front of the ODB?
>> * We already have that! (sort of..) 9a414486d9 (lookup_object:
>>   prioritize recently found objects, 2013-05-01)
>> * Instead of improving the caching, maybe change the
>>   size of the problem: We could keep the objects of different types
>>   in different hash-tables.
>
> I don't think this is using lookup_object() at all, though. It goes
> straight to fill_tree_descriptor(), which will read the object contents
> from disk. So our time is going to:
>
>   1. Finding the object in the odb (ideally a binary search in a single
>      pack index, but less optimal when there are many packs).
>
>   2. Reconstructing the object. This means zlib-inflating from disk, but
>      it may also mean delta reconstruction.
>
> I think there _are_ some caches at play here, though, when you look up
> the same tree back to back. The pack-mru means that we'll always look in
> the correct pack first. And in theory the delta base cache means that
> we'll already have the whole thing reconstructed in memory (though I
> have often been confused by exactly when we put items into that cache,
> so I might be wrong).

This change shaved 500K calls to fill_tree_descriptor() (on the Windows
source tree on a "checkout -b" to the same commit).  I was surprised it
didn't give more of a speed up, so some of that caching may be in play
here, but it's hard to tell.

Also, on my repo I have 100GB+ of packfiles, so that may be messing
with things a bit.

>
> So in theory, this is not all that different than the "just allocate and
> copy the bytes" optimization that's happening here (though I'm not
> surprised that doing it at a higher level can produce some speedup).
>
> I think the more interesting optimization is "just use the same buffer
> without bothering to copy", which is hard for the low-level code to do
> (since it doesn't know what lifetime the caller is expecting).

My first draft did just borrow the buffer right there in traverse_
and it seemed to work just fine.  I was being cautious and copied it
properly in the lower layer.  Since the bufs are freed at the bottom
it felt safe, but I didn't want to overlook anything.  I'll switch it
back.

>
>> object.c has its own hash table, I presume for historical and
>> performance reasons, this would be split up to multiple hash
>> tables.
>
> So I don't think lookup_object() is really relevant here. But I'm also
> not sure that multiple hash tables would really buy us much. In theory
> hash tables are O(1), so multiple smaller tables doesn't help (and might
> hurt, since now we have four O(1) lookups to do). Of course that's a
> minor fiction because of collisions, but we keep the load factor on the
> object.c table pretty low (and that's why things like quadratic probing
> and cuckoo hashing never showed great improvement).

I do wonder now about the initial hash table size and any limits
on it, but that is a question for another day.

Thanks
Jeff

Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[Jeff Hostetler]

On 4/6/2017 8:32 PM, René Scharfe wrote:
> Am 06.04.2017 um 22:37 schrieb git@jeffhostetler.com:
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> Teach traverse_trees_recursive() to not do redundant ODB
>> lookups when both directories refer to the same OID.
>>
>> In operations such as read-tree, checkout, and merge when
>> the differences between the commits are relatively small,
>> there will likely be many directories that have the same
>> SHA-1.  In these cases we can avoid hitting the ODB multiple
>> times for the same SHA-1.
>>
>> TODO This change is a first attempt to test that by comparing
>> TODO the hashes of name[i] and name[i-i] and simply copying
>> TODO the tree-descriptor data.  I was thinking of the n=2
>> TODO case here.  We may want to extend this to the n=3 case.
>>
>> ================
>> On the Windows repo (500K trees, 3.1M files, 450MB index),
>> this reduced the overall time by 0.75 seconds when cycling
>> between 2 commits with a single file difference.
>>
>> (avg) before: 22.699
>> (avg) after:  21.955
>> ===============
>>
>> ================
>> Using the p0004-read-tree test (posted earlier this week)
>> with 1M files on Linux:
>>
>> before:
>> $ ./p0004-read-tree.sh
>> 0004.5: switch work1 work2 (1003037)       11.99(8.12+3.32)
>> 0004.6: switch commit aliases (1003037)    11.95(8.20+3.14)
>>
>> after:
>> $ ./p0004-read-tree.sh
>> 0004.5: switch work1 work2 (1003037)       11.17(7.84+2.76)
>> 0004.6: switch commit aliases (1003037)    11.13(7.82+2.72)
>> ================
>>
>> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
>> ---
>>   tree-walk.c    |  8 ++++++++
>>   tree-walk.h    |  1 +
>>   unpack-trees.c | 13 +++++++++----
>>   3 files changed, 18 insertions(+), 4 deletions(-)
>>
>> diff --git a/tree-walk.c b/tree-walk.c
>> index ff77605..3b82f0e 100644
>> --- a/tree-walk.c
>> +++ b/tree-walk.c
>> @@ -92,6 +92,14 @@ void *fill_tree_descriptor(struct tree_desc *desc,
>> const unsigned char *sha1)
>>       return buf;
>>   }
>>   +void *copy_tree_descriptor(struct tree_desc *dest, const struct
>> tree_desc *src)
>> +{
>> +    void *buf = xmalloc(src->size);
>> +    memcpy(buf, src->buffer, src->size);
>> +    init_tree_desc(dest, buf, src->size);
>> +    return buf;
>> +}
>> +
>>   static void entry_clear(struct name_entry *a)
>>   {
>>       memset(a, 0, sizeof(*a));
>> diff --git a/tree-walk.h b/tree-walk.h
>> index 68bb78b..ca4032b 100644
>> --- a/tree-walk.h
>> +++ b/tree-walk.h
>> @@ -43,6 +43,7 @@ int tree_entry(struct tree_desc *, struct name_entry
>> *);
>>   int tree_entry_gently(struct tree_desc *, struct name_entry *);
>>     void *fill_tree_descriptor(struct tree_desc *desc, const unsigned
>> char *sha1);
>> +void *copy_tree_descriptor(struct tree_desc *dest, const struct
>> tree_desc *src);
>>     struct traverse_info;
>>   typedef int (*traverse_callback_t)(int n, unsigned long mask,
>> unsigned long dirmask, struct name_entry *entry, struct traverse_info *);
>> diff --git a/unpack-trees.c b/unpack-trees.c
>> index 3a8ee19..50aacad 100644
>> --- a/unpack-trees.c
>> +++ b/unpack-trees.c
>> @@ -554,10 +554,15 @@ static int traverse_trees_recursive(int n,
>> unsigned long dirmask,
>>       newinfo.df_conflicts |= df_conflicts;
>>         for (i = 0; i < n; i++, dirmask >>= 1) {
>> -        const unsigned char *sha1 = NULL;
>> -        if (dirmask & 1)
>> -            sha1 = names[i].oid->hash;
>> -        buf[i] = fill_tree_descriptor(t+i, sha1);
>> +        if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&
>
> Can .oid even be NULL?  (I didn't check, but it's dereferenced in the
> sha1 assignment below, so I guess the answer is no and these two checks
> are not needed.)

yes.  i think the (dirmask&1) is hiding it for name[i].  i put both in
the code above, but it also worked fine just testing both oid's (and
without dirmask).

>
>> +            !hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {
>
> Calling oidcmp would be shorter.

right.

>
>> +            buf[i] = copy_tree_descriptor(&t[i], &t[i-1]);
>
> buf keeps track of the allocations that need to be freed at the end of
> the function.  I assume these buffers are read-only.  Can you use an
> alias here instead of a duplicate by calling init_tree_desc with the
> predecessor's buffer and setting buf[i] to NULL?  Or even just copying
> t[i - 1] to t[i] with an assignment?  That would be shorter and probably
> also quicker.

Yes, my first draft did that.  Just being cautious, but i'll switch it
back since that seems to be the consensus.

>
>> +        } else {
>> +            const unsigned char *sha1 = NULL;
>> +            if (dirmask & 1)
>> +                sha1 = names[i].oid->hash;
>> +            buf[i] = fill_tree_descriptor(t+i, sha1);
>> +        }
>>       }
>>         bottom = switch_cache_bottom(&newinfo);
>>

Thanks
Jeff

Re: [PATCH v1] unpack-trees: avoid duplicate ODB lookups during checkout

[Jeff Hostetler]

On 4/6/2017 6:48 PM, Stefan Beller wrote:
> On Thu, Apr 6, 2017 at 1:37 PM,  <git@jeffhostetler.com> wrote:
>> From: Jeff Hostetler <jeffhost@microsoft.com>
>>
>> Teach traverse_trees_recursive() to not do redundant ODB
>> lookups when both directories refer to the same OID.
>
> And the reason for this is that omitting the second lookup
> saves time, i.e. a lookup in the ODB of a sufficiently large
> repo is slow.
>
> My kneejerk line of thinking:
> * yes, it sounds good to reduce the number of ODB accesses.
> * But if we consider ODB lookups to be slow and we perform
>   a structured access, how about a cache in front of the ODB?
> * We already have that! (sort of..) 9a414486d9 (lookup_object:
>   prioritize recently found objects, 2013-05-01)
> * Instead of improving the caching, maybe change the
>   size of the problem: We could keep the objects of different types
>   in different hash-tables.
>
> object.c has its own hash table, I presume for historical and
> performance reasons, this would be split up to multiple hash
> tables.
>
> Additionally to "object *lookup_object(*sha1)", we'd have
> a function
>
> "object *lookup_object(*sha1, enum object_type hint)"
> which looks into the correct the hash table.
>
> If you were to call just  lookup_object with no hint, then you'd
> look into all the different tables (I guess there is a preferrable
> order in which to look, haven't thought about that).
>
>>
>> In operations such as read-tree, checkout, and merge when
>> the differences between the commits are relatively small,
>> there will likely be many directories that have the same
>> SHA-1.  In these cases we can avoid hitting the ODB multiple
>> times for the same SHA-1.
>
> This would explain partially why there was such a good
> performance boost in the referenced commit above as we
> implicitly lookup the same object multiple times.
>
> Peff is really into getting this part faster, c.f.
> https://public-inbox.org/git/20160914235547.h3n2otje2hec6u7k@sigill.intra.peff.net/

That looks interesting, but I question the probabilities for
my use case here.  When walking the trees and files in a single
commit, I have no expectation that I'll see the same tree OID
twice, so the cache is not really useful and may just add
overhead.  However, in a checkout or merge there is a high
expectation of visiting the same tree OID -- and most of the
time they are peers -- since commits tend to only change
isolated parts of the tree.  (I'm not going to worry about the
case where someone moves an entire sub-tree to somewhere else
in the tree and violates my peer assertion.)

I did notice that we do 2 independent passes during checkout.
First to compare the old and new commits.  Then to compare the
new with the worktree.  So we touch each tree object 3 times.

My patch helps the first, but does nothing for the second.
Hopefully the cache is helping it (but I have not measured that).


>
>> TODO This change is a first attempt to test that by comparing
>> TODO the hashes of name[i] and name[i-i] and simply copying
>> TODO the tree-descriptor data.  I was thinking of the n=2
>> TODO case here.  We may want to extend this to the n=3 case.
>
>>
>> ================
>> On the Windows repo (500K trees, 3.1M files, 450MB index),
>> this reduced the overall time by 0.75 seconds when cycling
>> between 2 commits with a single file difference.
>>
>> (avg) before: 22.699
>> (avg) after:  21.955
>> ===============
>
> So it shaves off 4% of the time needed. it doesn't sound like a
> break through, but I guess these small patches add up. :)

Agreed, but on the Windows source repo, it can take 30 seconds to
do a "checkout -b" (without changing the actual HEAD commit).
That's just for the housekeeping of ensuring you get a clean
worktree.  If I can knock off 5% here with minimal impact
and without changing any file formats, I'll take it.

And if I can just repeat that n times...  :-)

>
>>         for (i = 0; i < n; i++, dirmask >>= 1) {
>> -               const unsigned char *sha1 = NULL;
>> -               if (dirmask & 1)
>> -                       sha1 = names[i].oid->hash;
>> -               buf[i] = fill_tree_descriptor(t+i, sha1);
>> +               if (i > 0 && (dirmask & 1) && names[i].oid && names[i-1].oid &&
>> +                       !hashcmp(names[i].oid->hash, names[i-1].oid->hash)) {
>
> Why do we need to check for dirmask & 1 here?
> This ought to be covered by the hashcmp already IIUC.
> So maybe we can pull out the
>                          if (dirmask & 1)
>                                  sha1 = names[i].oid->hash;
> out of the else when dropping that dirmask check?

I was wondering about the test in the else clause.
Just now I put a quick assert in there and it went off,
so I'm not going to change this.

Thanks
Jeff