Re: [PATCH v6 0/3] read-cache: speed up add_index_entry

From: Jeff King <peff@peff.net>
Date: Apr 7, 2017, 04:46 UTC
Message-ID: <20170407044626.ypsqnyxguw43gprm@sigill.intra.peff.net>
In-Reply-To: <20170406163442.36463-1-git@jeffhostetler.com>

On Thu, Apr 06, 2017 at 04:34:39PM +0000, git@jeffhostetler.com wrote:

Show 9 quoted lines

> Teach add_index_entry_with_check() and has_dir_name()
> to avoid index lookups if the given path sorts after
> the last entry in the index.
> 
> This saves at least 2 binary searches per entry.
> 
> This improves performance during checkout and read-tree because
> merge_working_tree() and unpack_trees() processes a list of already
> sorted entries.

Just thinking about this algorithmically for a moment. You're saving the binary search when the input is given in sorted order. But in other cases you're adding an extra strcmp() before the binary search begins. So it's a tradeoff.

How often is the input sorted? You save O(log n) strcmps for a "hit" with your patch, and one for a "miss". So it's a net win if we expect at least 1/log(n) of additions to be sorted (I'm talking about individual calls, but it should scale linearly either way over a set of n calls).

I have no clue if that's a reasonable assumption or not.

-Peff