RE: [PATCH 3/5] name-hash: precompute hash values during preload-index

From: Jeff Hostetler <jeff.hostetler@microsoft.com>
Date: Feb 19, 2017, 00:19 UTC
Message-ID: <MWHPR03MB295845950BB87BA9479E973E8A5F0@MWHPR03MB2958.namprd03.prod.outlook.com>
In-Reply-To: <xmqq37fcnj7v.fsf@gitster.mtv.corp.google.com>

From: Junio C Hamano [mailto:jch2355@gmail.com] On Behalf Of Junio C Hamano

Show 14 quoted lines

> 
> The fact that each preload_thread() still walks the index in-order
> makes me wonder if it may allow us to further optimize the "dir"
> part of the hash by passing the previous ce for which we already
> precomputed hash values.  While the loop is iterating over the paths
> in the same directory, .dir component from the previous ce can be
> reused and .name component can "continue", no?
> 
> It's possible that you already tried such an optimization and
> rejected it after finding that the cost of comparison of pathnames
> to tell if ce and previous ce are still in the same directory is
> more than unconditionally memihash() the directory part, and I am in
> no way saying that I found a missed optimization opportunity you
> must pursue.  I am just being curious.

I looked at doing this, but I didn't think the complexity and overhead to forward search for peers at the current level didn't warrant the limited gains. (I was just looking at the complexity of clear_ce_flags_1() in unpack-trees.c and how hard it has to look to find the end of the current directory and the effect that that has on the recursion and it felt like too much work for the potential gain.)

Whereas remembering the previous one was basically free. Granted, it only helps us for adjacent files in the index, so it's not perfect, but gives us the best bang for the buck.

Jeff