git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / Atom feed
From: Derrick Stolee <stolee@gmail.com>
To: Elijah Newren <newren@gmail.com>,
	Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>
Cc: Git Mailing List <git@vger.kernel.org>,
	Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH 0/9] [RFC] New sparse-checkout builtin and "cone" mode
Date: Thu, 22 Aug 2019 10:25:21 -0400
Message-ID: <67dc33a6-3995-bd3e-f1be-db337c04c7b2@gmail.com> (raw)
In-Reply-To: <08bd295b-ec5a-3128-42cf-acb24971d679@gmail.com>

On 8/22/2019 9:10 AM, Derrick Stolee wrote:
> On 8/21/2019 5:52 PM, Elijah Newren wrote:
>> On Tue, Aug 20, 2019 at 8:12 AM Derrick Stolee via GitGitGadget
>>> For example, if we add A/B/C as a recursive folder, then we add the
>>> following patterns to the sparse-checkout file:
>>>
>>> /*
>>> !/*/*
>>> /A/*
>>> !/A/*/*
>>> /A/B/*
>>> !/A/B/*/*
>>> /A/B/C/*
>>>
>>> The alternating positive/negative patterns say "include everything in this
>>> folder, but exclude everything another level deeper". The final pattern has
>>> no matching negation, so is a recursively closed pattern.
>>
>> Oh, um, would there be any option for fast but without grabbing
>> sibling and parent files of requested directories?  And could users
>> still request individual files (not with regex or pathspec, but fully
>> specifying the path) and still get the fast mode?
> 
> Exact files could probably be included and still be fast. It requires an
> extra hash check per entry, but that's a small price to pay I think.

Quick side note on this point about exact file names and the REAL reason
for the parent paths that I had forgotten until just now.

The following comment exists in unpack-trees.c, clear_ce_flags_dir():

	/*
	 * TODO: check el, if there are no patterns that may conflict
	 * with ret (iow, we know in advance the incl/excl
	 * decision for the entire directory), clear flag here without
	 * calling clear_ce_flags_1(). That function will call
	 * the expensive is_excluded_from_list() on every entry.
	 */

While I haven't implemented it yet in this RFC, this TODO can actually
happen with the current set of cone patterns:

1. If we hit a directory that is not in a parent or recursive path,
   then all paths it contains must have their skipworktree bits set.
   We can avoid computing hashes for them.

2. If we hit a directory that is in a recursive path, then all paths
   it contains must have skipworktree bits off. We can avoid computing
   hashes for them.

When we have a million index entries, these hash computations are not
insignificant!

With that in mind, I think there is a _performance_ reason to include
the parent folders in addition to _user experience_ reason. If we
were to add the complexity of exact file matches, then we would also
want to add the parent folders leading to that file so we can still
do the logic above.

Thanks,
-Stolee

  reply index

Thread overview: 196+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-08-20 15:11 Derrick Stolee via GitGitGadget
2019-08-20 15:11 ` [PATCH 1/9] sparse-checkout: create builtin with 'list' subcommand Derrick Stolee via GitGitGadget
2019-08-23 22:30   ` Elijah Newren
2019-08-20 15:11 ` [PATCH 2/9] sparse-checkout: create 'init' subcommand Derrick Stolee via GitGitGadget
2019-08-23 23:02   ` Elijah Newren
2019-09-11 14:27     ` Derrick Stolee
2019-09-11 20:28     ` Derrick Stolee
2019-08-20 15:11 ` [PATCH 3/9] clone: add --sparse mode Derrick Stolee via GitGitGadget
2019-08-23 23:17   ` Elijah Newren
2019-09-18 13:51     ` Derrick Stolee
2019-08-20 15:11 ` [PATCH 4/9] sparse-checkout: 'add' subcommand Derrick Stolee via GitGitGadget
2019-08-23 23:30   ` Elijah Newren
2019-09-18 13:55     ` Derrick Stolee
2019-09-18 14:56       ` Elijah Newren
2019-09-18 17:23         ` Derrick Stolee
2019-08-20 15:11 ` [PATCH 5/9] sparse-checkout: create 'disable' subcommand Derrick Stolee via GitGitGadget
2019-08-23 23:50   ` Elijah Newren
2019-08-20 15:11 ` [PATCH 6/9] trace2:experiment: clear_ce_flags_1 Jeff Hostetler via GitGitGadget
2019-08-24  0:08   ` Elijah Newren
2019-08-20 15:11 ` [PATCH 7/9] sparse-checkout: add 'cone' mode Derrick Stolee via GitGitGadget
2019-08-24  0:31   ` Elijah Newren
2019-08-20 15:11 ` [PATCH 8/9] sparse-checkout: use hashmaps for cone patterns Derrick Stolee via GitGitGadget
2019-08-24  4:56   ` Elijah Newren
2019-08-20 15:11 ` [PATCH 9/9] sparse-checkout: init and add in cone mode Derrick Stolee via GitGitGadget
2019-08-24  5:07   ` Elijah Newren
2019-08-21 21:52 ` [PATCH 0/9] [RFC] New sparse-checkout builtin and "cone" mode Elijah Newren
2019-08-22 13:10   ` Derrick Stolee
2019-08-22 14:25     ` Derrick Stolee [this message]
2019-08-24  5:40     ` Elijah Newren
2019-08-26 13:29       ` Derrick Stolee
2019-08-26 18:16         ` Elijah Newren
2019-08-26 19:16           ` Derrick Stolee
2019-09-02 17:55       ` Eric Sunshine
2019-09-19 14:43 ` [PATCH v2 00/11] " Derrick Stolee via GitGitGadget
2019-09-19 14:43   ` [PATCH v2 01/11] sparse-checkout: create builtin with 'list' subcommand Derrick Stolee via GitGitGadget
2019-10-05 19:22     ` Elijah Newren
2019-09-19 14:43   ` [PATCH v2 02/11] sparse-checkout: create 'init' subcommand Derrick Stolee via GitGitGadget
2019-10-05 19:34     ` Elijah Newren
2019-09-19 14:43   ` [PATCH v2 03/11] clone: add --sparse mode Derrick Stolee via GitGitGadget
2019-10-05 19:40     ` Elijah Newren
2019-10-07 13:56       ` Derrick Stolee
2019-09-19 14:43   ` [PATCH v2 05/11] sparse-checkout: add '--stdin' option to set subcommand Derrick Stolee via GitGitGadget
2019-09-19 14:43   ` [PATCH v2 04/11] sparse-checkout: 'set' subcommand Derrick Stolee via GitGitGadget
2019-10-05 22:44     ` Elijah Newren
2019-10-06  0:30       ` Elijah Newren
2019-10-07 18:26         ` Derrick Stolee
2019-10-11 22:24           ` Elijah Newren
2019-09-19 14:43   ` [PATCH v2 06/11] sparse-checkout: create 'disable' subcommand Derrick Stolee via GitGitGadget
2019-10-06  4:10     ` Elijah Newren
2019-10-07 19:12       ` Derrick Stolee
2019-09-19 14:43   ` [PATCH v2 07/11] trace2: add region in clear_ce_flags Jeff Hostetler via GitGitGadget
2019-10-06  4:13     ` Elijah Newren
2019-09-19 14:43   ` [PATCH v2 08/11] sparse-checkout: add 'cone' mode Derrick Stolee via GitGitGadget
2019-10-06  4:22     ` Elijah Newren
2019-10-07 19:15       ` Derrick Stolee
2019-09-19 14:43   ` [PATCH v2 09/11] sparse-checkout: use hashmaps for cone patterns Derrick Stolee via GitGitGadget
2019-09-19 20:59     ` Derrick Stolee
2019-09-20 14:37       ` Derrick Stolee
2019-09-19 14:43   ` [PATCH v2 10/11] sparse-checkout: init and set in cone mode Derrick Stolee via GitGitGadget
2019-09-19 14:43   ` [PATCH v2 11/11] unpack-trees: hash less " Derrick Stolee via GitGitGadget
2019-10-01 13:40   ` [PATCH v2 00/11] New sparse-checkout builtin and "cone" mode Derrick Stolee
2019-10-01 16:54     ` Elijah Newren
2019-10-01 18:15       ` Derrick Stolee
2019-10-03 22:28     ` Junio C Hamano
2019-10-07 20:08   ` [PATCH v3 00/17] " Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 01/17] sparse-checkout: create builtin with 'list' subcommand Derrick Stolee via GitGitGadget
2019-10-11 22:01       ` Elijah Newren
2019-10-07 20:08     ` [PATCH v3 02/17] sparse-checkout: create 'init' subcommand Derrick Stolee via GitGitGadget
2019-10-11 22:14       ` Elijah Newren
2019-10-14 20:22         ` Derrick Stolee
2019-10-07 20:08     ` [PATCH v3 03/17] clone: add --sparse mode Derrick Stolee via GitGitGadget
2019-10-11 22:20       ` Elijah Newren
2019-10-07 20:08     ` [PATCH v3 04/17] sparse-checkout: 'set' subcommand Derrick Stolee via GitGitGadget
2019-10-11 22:26       ` Elijah Newren
2019-10-11 22:30         ` Elijah Newren
2019-10-07 20:08     ` [PATCH v3 05/17] sparse-checkout: add '--stdin' option to set subcommand Derrick Stolee via GitGitGadget
2019-10-11 22:27       ` Elijah Newren
2019-10-14 20:28         ` Derrick Stolee
2019-10-07 20:08     ` [PATCH v3 06/17] sparse-checkout: create 'disable' subcommand Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 07/17] trace2: add region in clear_ce_flags Jeff Hostetler via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 08/17] sparse-checkout: add 'cone' mode Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 09/17] sparse-checkout: use hashmaps for cone patterns Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 10/17] sparse-checkout: init and set in cone mode Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 11/17] unpack-trees: hash less " Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 12/17] unpack-trees: add progress to clear_ce_flags() Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 13/17] read-tree: show progress by default Derrick Stolee via GitGitGadget
2019-10-12 22:16       ` Elijah Newren
2019-10-14 20:31         ` Derrick Stolee
2019-10-07 20:08     ` [PATCH v3 14/17] sparse-checkout: sanitize for nested folders Derrick Stolee via GitGitGadget
2019-10-07 20:08     ` [PATCH v3 15/17] sparse-checkout: update working directory in-process Derrick Stolee via GitGitGadget
2019-10-12 22:57       ` Elijah Newren
2019-10-14 20:39         ` Derrick Stolee
2019-10-07 20:08     ` [PATCH v3 16/17] sparse-checkout: write using lockfile Derrick Stolee via GitGitGadget
2019-10-12 22:59       ` Elijah Newren
2019-10-14 20:41         ` Derrick Stolee
2019-10-07 20:08     ` [PATCH v3 17/17] sparse-checkout: cone mode should not interact with .gitignore Derrick Stolee via GitGitGadget
2019-10-12 23:00       ` Elijah Newren
2019-10-12 23:22     ` [PATCH v3 00/17] New sparse-checkout builtin and "cone" mode Elijah Newren
2019-10-15 13:55     ` [PATCH v4 " Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 01/17] sparse-checkout: create builtin with 'list' subcommand Derrick Stolee via GitGitGadget
2019-10-16 19:00         ` Elijah Newren
2019-10-21 12:10           ` Derrick Stolee
2019-10-18 16:07         ` SZEDER Gábor
2019-10-21 11:42           ` Derrick Stolee
2019-10-15 13:55       ` [PATCH v4 02/17] sparse-checkout: create 'init' subcommand Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 03/17] clone: add --sparse mode Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 04/17] sparse-checkout: 'set' subcommand Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 05/17] sparse-checkout: add '--stdin' option to set subcommand Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 06/17] sparse-checkout: create 'disable' subcommand Derrick Stolee via GitGitGadget
2019-10-18 16:31         ` SZEDER Gábor
2019-10-15 13:55       ` [PATCH v4 07/17] trace2: add region in clear_ce_flags Jeff Hostetler via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 08/17] sparse-checkout: add 'cone' mode Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 09/17] sparse-checkout: use hashmaps for cone patterns Derrick Stolee via GitGitGadget
2019-10-18 15:31         ` SZEDER Gábor
2019-10-21 11:44           ` Derrick Stolee
2019-10-15 13:55       ` [PATCH v4 10/17] sparse-checkout: init and set in cone mode Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 11/17] unpack-trees: hash less " Derrick Stolee via GitGitGadget
2019-10-15 13:55       ` [PATCH v4 12/17] unpack-trees: add progress to clear_ce_flags() Derrick Stolee via GitGitGadget
2019-10-15 13:56       ` [PATCH v4 13/17] read-tree: show progress by default Derrick Stolee via GitGitGadget
2019-10-15 13:56       ` [PATCH v4 14/17] sparse-checkout: sanitize for nested folders Derrick Stolee via GitGitGadget
2019-10-15 13:56       ` [PATCH v4 15/17] sparse-checkout: update working directory in-process Derrick Stolee via GitGitGadget
2019-10-18 20:24         ` SZEDER Gábor
2019-10-18 20:40           ` SZEDER Gábor
2019-10-21 11:59             ` Derrick Stolee
2019-10-15 13:56       ` [PATCH v4 16/17] sparse-checkout: write using lockfile Derrick Stolee via GitGitGadget
2019-10-15 13:56       ` [PATCH v4 17/17] sparse-checkout: cone mode should not interact with .gitignore Derrick Stolee via GitGitGadget
2019-10-16 20:07       ` [PATCH v4 00/17] New sparse-checkout builtin and "cone" mode Elijah Newren
2019-10-17 23:53       ` Jon Simons
2019-10-21 12:08         ` Derrick Stolee
2019-10-21 13:56       ` [PATCH v5 " Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 01/17] sparse-checkout: create builtin with 'list' subcommand Derrick Stolee via GitGitGadget
2019-11-19 22:51           ` SZEDER Gábor
2019-10-21 13:56         ` [PATCH v5 02/17] sparse-checkout: create 'init' subcommand Derrick Stolee via GitGitGadget
2019-11-19 14:33           ` SZEDER Gábor
2019-11-20 14:13             ` SZEDER Gábor
2019-11-21 11:49           ` SZEDER Gábor
2019-11-21 12:34             ` SZEDER Gábor
2019-11-21 14:28             ` Derrick Stolee
2019-11-21 15:27               ` SZEDER Gábor
2019-11-21 15:36                 ` Derrick Stolee
2019-11-21 16:37                   ` SZEDER Gábor
2019-11-21 17:01                     ` Elijah Newren
2019-11-21 17:15                       ` Derrick Stolee
2019-10-21 13:56         ` [PATCH v5 03/17] clone: add --sparse mode Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 04/17] sparse-checkout: 'set' subcommand Derrick Stolee via GitGitGadget
2019-11-19 15:46           ` SZEDER Gábor
2019-11-21 13:04             ` Derrick Stolee
2019-11-21 13:36               ` SZEDER Gábor
2019-10-21 13:56         ` [PATCH v5 05/17] sparse-checkout: add '--stdin' option to set subcommand Derrick Stolee via GitGitGadget
2019-11-21 11:21           ` SZEDER Gábor
2019-11-21 13:15             ` Derrick Stolee
2019-10-21 13:56         ` [PATCH v5 06/17] sparse-checkout: create 'disable' subcommand Derrick Stolee via GitGitGadget
2019-11-19 16:15           ` SZEDER Gábor
2019-11-21 13:17             ` Derrick Stolee
2019-10-21 13:56         ` [PATCH v5 07/17] trace2: add region in clear_ce_flags Jeff Hostetler via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 08/17] sparse-checkout: add 'cone' mode Derrick Stolee via GitGitGadget
2019-11-19 17:36           ` SZEDER Gábor
2019-10-21 13:56         ` [PATCH v5 09/17] sparse-checkout: use hashmaps for cone patterns Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 10/17] sparse-checkout: init and set in cone mode Derrick Stolee via GitGitGadget
2019-11-19 17:50           ` SZEDER Gábor
2019-11-21 13:45             ` Derrick Stolee
2019-10-21 13:56         ` [PATCH v5 11/17] unpack-trees: hash less " Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 12/17] unpack-trees: add progress to clear_ce_flags() Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 13/17] read-tree: show progress by default Derrick Stolee via GitGitGadget
2019-10-21 15:04           ` Phillip Wood
2019-10-21 15:14             ` Derrick Stolee
2019-10-23  3:48               ` Junio C Hamano
2019-10-23 12:50                 ` Derrick Stolee
2019-10-24 10:18                   ` Phillip Wood
2019-10-24 10:18                 ` Phillip Wood
2019-10-21 13:56         ` [PATCH v5 14/17] sparse-checkout: sanitize for nested folders Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 15/17] sparse-checkout: update working directory in-process Derrick Stolee via GitGitGadget
2019-11-19 17:07           ` SZEDER Gábor
2019-10-21 13:56         ` [PATCH v5 16/17] sparse-checkout: write using lockfile Derrick Stolee via GitGitGadget
2019-10-21 13:56         ` [PATCH v5 17/17] sparse-checkout: cone mode should not interact with .gitignore Derrick Stolee via GitGitGadget
2019-10-23  3:52         ` [PATCH v5 00/17] New sparse-checkout builtin and "cone" mode Junio C Hamano
2019-11-21 22:04         ` [PATCH v6 00/19] " Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 01/19] sparse-checkout: create builtin with 'list' subcommand Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 02/19] sparse-checkout: create 'init' subcommand Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 03/19] clone: add --sparse mode Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 04/19] sparse-checkout: 'set' subcommand Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 05/19] sparse-checkout: add '--stdin' option to set subcommand Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 06/19] sparse-checkout: create 'disable' subcommand Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 07/19] trace2: add region in clear_ce_flags Jeff Hostetler via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 08/19] sparse-checkout: add 'cone' mode Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 09/19] sparse-checkout: use hashmaps for cone patterns Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 10/19] sparse-checkout: init and set in cone mode Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 11/19] unpack-trees: hash less " Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 12/19] unpack-trees: add progress to clear_ce_flags() Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 13/19] sparse-checkout: sanitize for nested folders Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 14/19] sparse-checkout: update working directory in-process Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 15/19] sparse-checkout: use in-process update for disable subcommand Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 16/19] sparse-checkout: write using lockfile Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 17/19] sparse-checkout: cone mode should not interact with .gitignore Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 18/19] sparse-checkout: update working directory in-process for 'init' Derrick Stolee via GitGitGadget
2019-11-21 22:04           ` [PATCH v6 19/19] sparse-checkout: check for dirty status Derrick Stolee via GitGitGadget

Reply instructions:

You may reply publically 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=67dc33a6-3995-bd3e-f1be-db337c04c7b2@gmail.com \
    --to=stolee@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --cc=gitster@pobox.com \
    --cc=newren@gmail.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

git@vger.kernel.org list mirror (unofficial, one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Example config snippet for mirrors

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git