From: Jeff King <peff@peff.net>
Date: Mon, 10 Apr 2017 20:55:40 GMT
Subject: Re: [PATCH v2] unpack-trees: avoid duplicate ODB lookups during checkout
Message-ID: <20170410205540.wvlb7ch7bodiytmh@sigill.intra.peff.net>
In-Reply-To: <23662d7b-84a9-4b71-1aa5-5d3d111f5c3d@web.de>

On Sat, Apr 08, 2017 at 04:06:41PM +0200, René Scharfe wrote:

> > +		} else if (i > 1 && are_same_oid(&names[i], &names[i-2])) {
> > +			/* implicitly borrow buf[i-2] inside tree_desc[i] */
> > +			memcpy(&t[i], &t[i-2], sizeof(struct tree_desc));
> 
> Similar case.
> 
> > +			buf[i] = NULL;
> 
> What makes the previous two entries special, or differently put: Why not
> just check *all* previous entries?  MAX_UNPACK_TREES is 8; the number of
> comparisons would just about double in the worst case and stay the same for
> three trees or less.  The order of four trees or more wouldn't matter
> anymore.

If I understand correctly, we've got N (up to 8) trees, and we want to
find sets of duplicates. Adjacency doesn't matter. Aren't our options
basically:

  - look through all previous entries naively, O(N^2)

  - sort the list, O(N log N); but we need the original order, so we'd
    have to unsort at the end, too

  - use a hash table, O(N) but with O(N) extra storage

I know N=8 isn't very big algorithmically speaking, but it would feel
ugly to introduce something quadratic. Especially the limit of 8 seems
rather arbitrary. In normal cases we see at most a 3-way merge. Beyond
that we're in octopus territory, and 8 is way too low there (I think the
octopus strategy just unpacks one at a time and barfs if there are any
conflicts).

I assume the rationale behind "check the last 2" is just "this
optimization will kick in reliably for all sane cases", weird octopus
unpack-trees be damned (though reading ca885a4fe, it sounds like 4-trees
can actually happen, but I'm not clear on how).

-Peff