From: Junio C Hamano <gitster@pobox.com>
To: "René Scharfe" <l.s.r@web.de>
Cc: Brandon Williams <bwilliamseng@gmail.com>,
git <git@vger.kernel.org>, Jeff King <peff@peff.net>
Subject: Re: invalid tree and commit object
Date: Sat, 09 May 2020 13:27:50 -0700 [thread overview]
Message-ID: <xmqqh7wovoop.fsf@gitster.c.googlers.com> (raw)
In-Reply-To: <938f0818-7e57-b883-009f-01db88ef8f65@web.de> (=?utf-8?Q?=22R?= =?utf-8?Q?en=C3=A9?= Scharfe"'s message of "Sat, 9 May 2020 21:24:43 +0200")
René Scharfe <l.s.r@web.de> writes:
> Hmm, this could lead to quadratic behavior in the worst case, can't it?
Oh, absolutely. But as you have shown, you'd need a specially
crafted tree with early entries that are prefixes of later ones,
which would rather be rare, and most of the time the bottom pointer
would advance by one every time we consume one path.
So it is trading (hopefully rare) worst-case runtime with reduced
storage cost.
> We could, however, reduce the names we add to the string_list to
> those that are possible candidates for conflict -- blobs followed by an
> entry whose name starts with the blob name followed by a dot and trees
> that follow an entry whose name matches in the same way.
Yes, that is a valid solution that strikes a different balance
between allocation and runtime.
We may want to survey how commonly "bad" trees appear in real
projects. Depending on the result, we might want to update the
"limit re-scanning using the bottom pointer" hack we have been using
in the unpack-trees code.
Thanks.
next prev parent reply other threads:[~2020-05-09 20:27 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-09 6:19 invalid tree and commit object Brandon Williams
2020-05-09 10:16 ` René Scharfe
2020-05-09 7:16 ` Johannes Schindelin
2020-05-09 11:51 ` René Scharfe
2020-05-09 17:28 ` Junio C Hamano
2020-05-09 19:24 ` René Scharfe
2020-05-09 20:27 ` Junio C Hamano [this message]
2020-05-10 9:07 ` René Scharfe
2020-05-10 16:12 ` René Scharfe
2020-05-11 16:25 ` Junio C Hamano
2020-05-13 16:27 ` Brandon Williams
2020-05-21 9:51 ` René Scharfe
2020-05-21 9:52 ` [PATCH 1/4] fsck: fix a typo in a comment René Scharfe
2020-05-21 10:10 ` Denton Liu
2020-05-21 11:15 ` René Scharfe
2020-05-21 9:52 ` [PATCH 2/4] t1450: increase test coverage of in-tree d/f detection René Scharfe
2020-05-21 10:20 ` Denton Liu
2020-05-21 13:31 ` René Scharfe
2020-05-21 18:01 ` Junio C Hamano
2020-05-21 9:52 ` [PATCH 3/4] t1450: demonstrate undetected in-tree d/f conflict René Scharfe
2020-05-21 9:52 ` [PATCH 4/4] fsck: detect more in-tree d/f conflicts René Scharfe
2020-05-10 16:37 ` invalid tree and commit object Junio C Hamano
2020-05-21 9:51 ` René Scharfe
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqh7wovoop.fsf@gitster.c.googlers.com \
--to=gitster@pobox.com \
--cc=bwilliamseng@gmail.com \
--cc=git@vger.kernel.org \
--cc=l.s.r@web.de \
--cc=peff@peff.net \
/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.
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 NNTP newsgroup(s).