Re: [PATCH v2 03/22] t3305: annotate with SHA1 prerequisite

From: Johan Herland <johan@herland.net>
Date: Jan 26, 2020, 18:18 UTC
Message-ID: <CALKQrgcF0KK1gEvyKe3th2w0YJBbmv+grgbCeN4fOzHKo=H1UA@mail.gmail.com>
In-Reply-To: <nycvar.QRO.7.76.6.2001261209590.46@tvgsbejvaqbjf.bet>

On Sun, Jan 26, 2020 at 12:16 PM Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Show 11 quoted lines

> On Sat, 25 Jan 2020, brian m. carlson wrote:
> > This test relies on a roughly equal distribution of hashes for notes in
> > order to ensure that fanouts are compressed.  If there are subtrees with
> > only one item left after removing notes, they'll end up still with one
> > level of fanout, causing the test to fail.
>
> That is _almost_ correct: The heuristic wants to see one bucket that has
> a note in it. Or something like that.
>
> See 73f77b909f8 (Notes API: for_each_note(): Traverse the entire notes
> tree with a callback, 2010-02-13) for details. (Cc:ing Johan.)

Something like that, yeah... Re-reading this code, I believe we stop the fanout at the current level when we can find one or more notes that do not share the high-nibble of their path with another note.

Here we're at the top level, so this corresponds to looking at the very first hex character (0-9a-f) of the path (oid of annotated object), and if there are at least two such objects for each hex character, we will use a fanout of 1, otherwise, we collapse the fanout to 0.

Hence we need an absolute minimum of 32 notes (and some rotten luck) to get a fanout of 1. As the number of notes increase, the probably of fanning out increases, passing 50% at ~79 notes, and reaching ~100% somewhere north of 150 notes.

Show 7 quoted lines

> > The test happens to pass with SHA-1, but doesn't necessarily with other
> > hash algorithms, so annotate it with the SHA1 prerequisite.
>
> I would rather see this tested, still, and reducing the number of notes
> that are retained from 50 to 20 before testing that the fanout has been
> reduced to 0 seems to do the trick. Therefore, I would love to submit this
> for squashing:

Yes, it seems that for SHA1 and the (deterministic) objects used in the test, we got away with 50 notes, but that is not the case for other hash algorithms. Lowering the number to 20 definitely results a fanout of 0, as should any other number below 32.

+1 to Dscho's squash.

...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net