From: Johan Herland <johan@herland.net>
To: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Cc: "brian m. carlson" <sandals@crustytoothpaste.net>,
Git mailing list <git@vger.kernel.org>,
Eric Sunshine <sunshine@sunshineco.com>
Subject: Re: [PATCH v2 03/22] t3305: annotate with SHA1 prerequisite
Date: Sun, 26 Jan 2020 19:18:15 +0100 [thread overview]
Message-ID: <CALKQrgcF0KK1gEvyKe3th2w0YJBbmv+grgbCeN4fOzHKo=H1UA@mail.gmail.com> (raw)
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:
> 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.
> > 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
next prev parent reply other threads:[~2020-01-26 18:54 UTC|newest]
Thread overview: 52+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-25 23:00 [PATCH v2 00/23] SHA-256 test fixes, part 8 brian m. carlson
2020-01-25 23:00 ` [PATCH v2 01/22] t/lib-pack: support SHA-256 brian m. carlson
2020-01-25 23:00 ` [PATCH v2 02/22] t3206: make hash size independent brian m. carlson
2020-01-25 23:00 ` [PATCH v2 03/22] t3305: annotate with SHA1 prerequisite brian m. carlson
2020-01-26 11:15 ` Johannes Schindelin
2020-01-26 18:18 ` Johan Herland [this message]
2020-01-26 21:28 ` Johannes Schindelin
2020-01-26 21:50 ` brian m. carlson
2020-01-26 23:57 ` Johan Herland
2020-01-27 12:22 ` Johannes Schindelin
2020-01-26 19:44 ` brian m. carlson
2020-01-25 23:00 ` [PATCH v2 04/22] t3308: make test work with SHA-256 brian m. carlson
2020-01-25 23:00 ` [PATCH v2 05/22] t3309: " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 06/22] t3310: " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 07/22] t3311: " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 08/22] t4013: make test hash independent brian m. carlson
2020-01-26 22:08 ` Johannes Schindelin
2020-01-26 22:26 ` brian m. carlson
2020-01-25 23:00 ` [PATCH v2 09/22] t4060: make test work with SHA-256 brian m. carlson
2020-01-25 23:00 ` [PATCH v2 10/22] t4211: make test hash independent brian m. carlson
2020-01-26 22:13 ` Johannes Schindelin
2020-01-25 23:00 ` [PATCH v2 11/22] t5302: make hash size independent brian m. carlson
2020-01-26 22:23 ` Johannes Schindelin
2020-01-26 22:33 ` brian m. carlson
2020-01-25 23:00 ` [PATCH v2 12/22] t5309: make test hash independent brian m. carlson
2020-01-25 23:00 ` [PATCH v2 13/22] t5313: " brian m. carlson
2020-01-28 18:15 ` Junio C Hamano
2020-01-25 23:00 ` [PATCH v2 14/22] t5321: " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 15/22] t5515: " brian m. carlson
2020-01-28 18:28 ` Junio C Hamano
2020-01-29 4:04 ` brian m. carlson
2020-01-25 23:00 ` [PATCH v2 16/22] t5318: update for SHA-256 brian m. carlson
2020-01-25 23:00 ` [PATCH v2 17/22] t5607: make hash size independent brian m. carlson
2020-01-25 23:00 ` [PATCH v2 17/23] t5616: use correct filter syntax brian m. carlson
2020-01-28 19:06 ` Junio C Hamano
2020-01-29 3:53 ` brian m. carlson
2020-01-25 23:00 ` [PATCH v2 18/23] t5607: make hash size independent brian m. carlson
2020-01-25 23:00 ` [PATCH v2 18/22] t5703: make test work with SHA-256 brian m. carlson
2020-01-28 19:09 ` Junio C Hamano
2020-01-29 3:46 ` brian m. carlson
2020-01-25 23:00 ` [PATCH v2 19/23] " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 19/22] t5703: switch tests to use test_oid brian m. carlson
2020-01-25 23:00 ` [PATCH v2 20/23] " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 20/22] t6000: abstract away SHA-1-specific constants brian m. carlson
2020-01-25 23:00 ` [PATCH v2 21/23] " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 21/22] t6006: make hash size independent brian m. carlson
2020-01-25 23:00 ` [PATCH v2 22/23] " brian m. carlson
2020-01-25 23:00 ` [PATCH v2 22/22] t6024: update for SHA-256 brian m. carlson
2020-01-25 23:00 ` [PATCH v2 23/23] " brian m. carlson
2020-01-26 10:25 ` [PATCH v2 00/23] SHA-256 test fixes, part 8 Johannes Schindelin
2020-01-26 19:42 ` brian m. carlson
2020-01-26 21:30 ` Johannes Schindelin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CALKQrgcF0KK1gEvyKe3th2w0YJBbmv+grgbCeN4fOzHKo=H1UA@mail.gmail.com' \
--to=johan@herland.net \
--cc=Johannes.Schindelin@gmx.de \
--cc=git@vger.kernel.org \
--cc=sandals@crustytoothpaste.net \
--cc=sunshine@sunshineco.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).