Git Mailing List Archive on lore.kernel.org
 help / color / Atom feed
From: Taylor Blau <me@ttaylorr.com>
To: Jonathan Tan <jonathantanmy@google.com>
Cc: me@ttaylorr.com, git@vger.kernel.org, dstolee@microsoft.com,
	gitster@pobox.com, peff@peff.net, martin.agren@gmail.com,
	szeder.dev@gmail.com
Subject: Re: [PATCH v2 12/24] pack-bitmap-write: fill bitmap with commit history
Date: Sat, 28 Nov 2020 12:21:20 -0500
Message-ID: <X8KHEMl87sU5cIGK@nand.local> (raw)
In-Reply-To: <20201125011409.941639-1-jonathantanmy@google.com>

On Tue, Nov 24, 2020 at 05:14:09PM -0800, Jonathan Tan wrote:
> > From: Derrick Stolee <dstolee@microsoft.com>
> >
> > The fill_bitmap_commit() method assumes that every parent of the given
> > commit is already part of the current bitmap. Instead of making that
> > assumption, let's walk parents until we reach commits already part of
> > the bitmap. Set the value for that parent immediately after querying to
> > save time doing double calls to find_object_pos() and to avoid inserting
> > the parent into the queue multiple times.
>
> I see from the later patches that this has no effect until the part
> where we can skip commits, but as Junio says [1], it's worth mentioning
> it here. Maybe something like:
>
>   The fill_bitmap_commit() method assumes that every parent of the given
>   commit is already part of the current bitmap. This is currently
>   correct, but a subsequent patch will change the nature of the edges of
>   the graph from parent-child to ancestor-descendant. In preparation for
>   that, let's walk parents...

Thanks. Stolee and I worked a little on revising this last week, and I
think that the current log message is more along these lines. Here's
what we wrote:

    pack-bitmap-write: fill bitmap with commit history

    The current implementation of bitmap_writer_build() creates a
    reachability bitmap for every walked commit. After computing a bitmap
    for a commit, those bits are pushed to an in-progress bitmap for its
    children.

    fill_bitmap_commit() assumes the bits corresponding to objects
    reachable from the parents of a commit are already set. This means that
    when visiting a new commit, we only have to walk the objects reachable
    between it and any of its parents.

    A future change to bitmap_writer_build() will relax this condition so
    not all parents have their reachable objects set in the in-progress
    bitmap. Prepare for that by having 'fill_bitmap_commit()' walk
    parents until reaching commits whose bits are already set. Then, walk
    the trees for these commits as well.

    This has no functional change with the current implementation of
    bitmap_writer_build().

> >  static void fill_bitmap_commit(struct bb_commit *ent,
> > -			       struct commit *commit)
> > +			       struct commit *commit,
> > +			       struct prio_queue *queue)
>
> As far as I can see, this function expects an empty queue and always
> ends with the queue empty, and the only reason why we don't instantiate
> a new queue every time is so that we can save on the internal array
> allocation/deallocation. Maybe add a comment to that effect.

Sure. Would you find a comment like that more helpful above
'fill_bitmap_commit()', or above the declaration of 'queue' (in
'bitmap_writer_build()') itself?

Thanks,
Taylor

  reply index

Thread overview: 174+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-11-11 19:41 [PATCH 00/23] pack-bitmap: bitmap generation improvements Taylor Blau
2020-11-11 19:41 ` [PATCH 01/23] ewah/ewah_bitmap.c: grow buffer past 1 Taylor Blau
2020-11-22 19:36   ` Junio C Hamano
2020-11-23 16:22     ` Taylor Blau
2020-11-24  2:48       ` Jeff King
2020-11-24  2:51         ` Jeff King
2020-12-01 22:56           ` Taylor Blau
2020-11-11 19:41 ` [PATCH 02/23] pack-bitmap: fix header size check Taylor Blau
2020-11-12 17:39   ` Martin Ågren
2020-11-11 19:42 ` [PATCH 03/23] pack-bitmap: bounds-check size of cache extension Taylor Blau
2020-11-12 17:47   ` Martin Ågren
2020-11-13  4:57     ` Jeff King
2020-11-13  5:26       ` Martin Ågren
2020-11-13 21:29       ` Taylor Blau
2020-11-13 21:39         ` Jeff King
2020-11-13 21:49           ` Taylor Blau
2020-11-13 22:11             ` Jeff King
2020-11-11 19:42 ` [PATCH 04/23] t5310: drop size of truncated ewah bitmap Taylor Blau
2020-11-11 19:42 ` [PATCH 05/23] rev-list: die when --test-bitmap detects a mismatch Taylor Blau
2020-11-11 19:42 ` [PATCH 06/23] ewah: factor out bitmap growth Taylor Blau
2020-11-11 19:42 ` [PATCH 07/23] ewah: make bitmap growth less aggressive Taylor Blau
2020-11-22 20:32   ` Junio C Hamano
2020-11-23 16:49     ` Taylor Blau
2020-11-24  3:00       ` Jeff King
2020-11-24 20:11         ` Junio C Hamano
2020-11-11 19:43 ` [PATCH 08/23] ewah: implement bitmap_or() Taylor Blau
2020-11-22 20:34   ` Junio C Hamano
2020-11-23 16:52     ` Taylor Blau
2020-11-11 19:43 ` [PATCH 09/23] ewah: add bitmap_dup() function Taylor Blau
2020-11-11 19:43 ` [PATCH 10/23] pack-bitmap-write: reimplement bitmap writing Taylor Blau
2020-11-11 19:43 ` [PATCH 11/23] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau
2020-11-11 19:43 ` [PATCH 12/23] pack-bitmap-write: fill bitmap with commit history Taylor Blau
2020-11-11 19:43 ` [PATCH 13/23] bitmap: add bitmap_diff_nonzero() Taylor Blau
2020-11-11 19:43 ` [PATCH 14/23] commit: implement commit_list_contains() Taylor Blau
2020-11-11 19:43 ` [PATCH 15/23] t5310: add branch-based checks Taylor Blau
2020-11-11 20:58   ` Derrick Stolee
2020-11-11 21:04     ` Junio C Hamano
2020-11-15 23:26       ` Johannes Schindelin
2020-11-11 19:43 ` [PATCH 16/23] pack-bitmap-write: rename children to reverse_edges Taylor Blau
2020-11-11 19:43 ` [PATCH 17/23] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau
2020-11-13 22:23   ` SZEDER Gábor
2020-11-13 23:03     ` Jeff King
2020-11-14  6:23       ` Jeff King
2020-11-11 19:43 ` [PATCH 18/23] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau
2020-11-11 19:44 ` [PATCH 19/23] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau
2020-11-11 19:44 ` [PATCH 20/23] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau
2020-11-11 19:44 ` [PATCH 21/23] pack-bitmap-write: use existing bitmaps Taylor Blau
2020-11-11 19:44 ` [PATCH 22/23] pack-bitmap-write: relax unique rewalk condition Taylor Blau
2020-11-11 19:44 ` [PATCH 23/23] pack-bitmap-write: better reuse bitmaps Taylor Blau
2020-11-17 21:46 ` [PATCH v2 00/24] pack-bitmap: bitmap generation improvements Taylor Blau
2020-11-17 21:46   ` [PATCH v2 01/24] ewah/ewah_bitmap.c: grow buffer past 1 Taylor Blau
2020-11-17 21:46   ` [PATCH v2 02/24] pack-bitmap: fix header size check Taylor Blau
2020-11-17 21:46   ` [PATCH v2 03/24] pack-bitmap: bounds-check size of cache extension Taylor Blau
2020-11-17 21:46   ` [PATCH v2 04/24] t5310: drop size of truncated ewah bitmap Taylor Blau
2020-11-17 21:46   ` [PATCH v2 05/24] rev-list: die when --test-bitmap detects a mismatch Taylor Blau
2020-11-17 21:46   ` [PATCH v2 06/24] ewah: factor out bitmap growth Taylor Blau
2020-11-17 21:47   ` [PATCH v2 07/24] ewah: make bitmap growth less aggressive Taylor Blau
2020-11-17 21:47   ` [PATCH v2 08/24] ewah: implement bitmap_or() Taylor Blau
2020-11-17 21:47   ` [PATCH v2 09/24] ewah: add bitmap_dup() function Taylor Blau
2020-11-17 21:47   ` [PATCH v2 10/24] pack-bitmap-write: reimplement bitmap writing Taylor Blau
2020-11-25  0:53     ` Jonathan Tan
2020-11-28 17:27       ` Taylor Blau
2020-11-17 21:47   ` [PATCH v2 11/24] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau
2020-11-25  1:00     ` Jonathan Tan
2020-11-17 21:47   ` [PATCH v2 12/24] pack-bitmap-write: fill bitmap with commit history Taylor Blau
2020-11-22 21:50     ` Junio C Hamano
2020-11-23 14:54       ` Derrick Stolee
2020-11-25  1:14     ` Jonathan Tan
2020-11-28 17:21       ` Taylor Blau [this message]
2020-11-30 18:33         ` Jonathan Tan
2020-11-17 21:47   ` [PATCH v2 13/24] bitmap: add bitmap_diff_nonzero() Taylor Blau
2020-11-22 22:01     ` Junio C Hamano
2020-11-23 20:19       ` Taylor Blau
2020-11-17 21:47   ` [PATCH v2 14/24] commit: implement commit_list_contains() Taylor Blau
2020-11-17 21:47   ` [PATCH v2 15/24] t5310: add branch-based checks Taylor Blau
2020-11-25  1:17     ` Jonathan Tan
2020-11-28 17:30       ` Taylor Blau
2020-11-17 21:47   ` [PATCH v2 16/24] pack-bitmap-write: rename children to reverse_edges Taylor Blau
2020-11-17 21:47   ` [PATCH v2 17/24] pack-bitmap.c: check reads more aggressively when loading Taylor Blau
2020-11-17 21:48   ` [PATCH v2 18/24] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau
2020-11-24  6:07     ` Jonathan Tan
2020-11-25  1:46     ` Jonathan Tan
2020-11-30 18:41       ` Derrick Stolee
2020-11-17 21:48   ` [PATCH v2 19/24] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau
2020-12-02  7:13     ` Jonathan Tan
2020-11-17 21:48   ` [PATCH v2 20/24] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau
2020-12-02  7:17     ` Jonathan Tan
2020-11-17 21:48   ` [PATCH v2 21/24] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau
2020-12-02  7:20     ` Jonathan Tan
2020-11-17 21:48   ` [PATCH v2 22/24] pack-bitmap-write: use existing bitmaps Taylor Blau
2020-12-02  7:28     ` Jonathan Tan
2020-12-02 16:21       ` Taylor Blau
2020-11-17 21:48   ` [PATCH v2 23/24] pack-bitmap-write: relax unique rewalk condition Taylor Blau
2020-12-02  7:44     ` Jonathan Tan
2020-12-02 16:30       ` Taylor Blau
2020-12-07 18:19         ` Jonathan Tan
2020-12-07 18:43           ` Derrick Stolee
2020-12-07 18:45             ` Derrick Stolee
2020-12-07 18:48           ` Jeff King
2020-11-17 21:48   ` [PATCH v2 24/24] pack-bitmap-write: better reuse bitmaps Taylor Blau
2020-12-02  8:08     ` Jonathan Tan
2020-12-02 16:35       ` Taylor Blau
2020-12-02 18:22         ` Derrick Stolee
2020-12-02 18:25           ` Taylor Blau
2020-12-07 18:26             ` Jonathan Tan
2020-12-07 18:24           ` Jonathan Tan
2020-12-07 19:20             ` Derrick Stolee
2020-11-18 18:32   ` [PATCH v2 00/24] pack-bitmap: bitmap generation improvements SZEDER Gábor
2020-11-18 19:51     ` Taylor Blau
2020-11-22  2:17       ` Taylor Blau
2020-11-22  2:28         ` Taylor Blau
2020-11-20  6:34   ` Martin Ågren
2020-11-21 19:37     ` Junio C Hamano
2020-11-21 20:11       ` Martin Ågren
2020-11-22  2:31         ` Taylor Blau
2020-11-24  2:43           ` Jeff King
2020-12-01 23:04             ` Taylor Blau
2020-12-01 23:37               ` Jonathan Tan
2020-12-01 23:43                 ` Taylor Blau
2020-12-02  8:11                   ` Jonathan Tan
2020-12-08  0:04 ` [PATCH v3 " Taylor Blau
2020-12-08  0:04   ` [PATCH v3 01/24] ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW() Taylor Blau
2020-12-08  0:04   ` [PATCH v3 02/24] pack-bitmap: fix header size check Taylor Blau
2020-12-08  0:04   ` [PATCH v3 03/24] pack-bitmap: bounds-check size of cache extension Taylor Blau
2020-12-08  0:04   ` [PATCH v3 04/24] t5310: drop size of truncated ewah bitmap Taylor Blau
2020-12-08  0:04   ` [PATCH v3 05/24] rev-list: die when --test-bitmap detects a mismatch Taylor Blau
2020-12-08  0:04   ` [PATCH v3 06/24] ewah: factor out bitmap growth Taylor Blau
2020-12-08  0:04   ` [PATCH v3 07/24] ewah: make bitmap growth less aggressive Taylor Blau
2020-12-08  0:04   ` [PATCH v3 08/24] ewah: implement bitmap_or() Taylor Blau
2020-12-08  0:04   ` [PATCH v3 09/24] ewah: add bitmap_dup() function Taylor Blau
2020-12-08  0:04   ` [PATCH v3 10/24] pack-bitmap-write: reimplement bitmap writing Taylor Blau
2020-12-08  0:05   ` [PATCH v3 11/24] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau
2020-12-08  0:05   ` [PATCH v3 12/24] pack-bitmap-write: fill bitmap with commit history Taylor Blau
2020-12-08  0:05   ` [PATCH v3 13/24] bitmap: implement bitmap_is_subset() Taylor Blau
2020-12-08  0:05   ` [PATCH v3 14/24] commit: implement commit_list_contains() Taylor Blau
2020-12-08  0:05   ` [PATCH v3 15/24] t5310: add branch-based checks Taylor Blau
2020-12-08  0:05   ` [PATCH v3 16/24] pack-bitmap-write: rename children to reverse_edges Taylor Blau
2020-12-08  0:05   ` [PATCH v3 17/24] pack-bitmap.c: check reads more aggressively when loading Taylor Blau
2020-12-08  0:05   ` [PATCH v3 18/24] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau
2020-12-08  0:05   ` [PATCH v3 19/24] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau
2020-12-08  0:05   ` [PATCH v3 20/24] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau
2020-12-08  0:05   ` [PATCH v3 21/24] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau
2020-12-08  0:05   ` [PATCH v3 22/24] pack-bitmap-write: use existing bitmaps Taylor Blau
2020-12-08  0:05   ` [PATCH v3 23/24] pack-bitmap-write: relax unique rewalk condition Taylor Blau
2020-12-08  0:05   ` [PATCH v3 24/24] pack-bitmap-write: better reuse bitmaps Taylor Blau
2020-12-08 20:56   ` [PATCH v3 00/24] pack-bitmap: bitmap generation improvements Junio C Hamano
2020-12-08 21:03     ` Taylor Blau
2020-12-08 22:03       ` Junio C Hamano
2020-12-08 22:03 ` [PATCH v4 " Taylor Blau
2020-12-08 22:03   ` [PATCH v4 01/24] ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW() Taylor Blau
2020-12-08 22:03   ` [PATCH v4 02/24] pack-bitmap: fix header size check Taylor Blau
2020-12-08 22:03   ` [PATCH v4 03/24] pack-bitmap: bounds-check size of cache extension Taylor Blau
2020-12-08 22:03   ` [PATCH v4 04/24] t5310: drop size of truncated ewah bitmap Taylor Blau
2020-12-08 22:03   ` [PATCH v4 05/24] rev-list: die when --test-bitmap detects a mismatch Taylor Blau
2020-12-08 22:03   ` [PATCH v4 06/24] ewah: factor out bitmap growth Taylor Blau
2020-12-08 22:03   ` [PATCH v4 07/24] ewah: make bitmap growth less aggressive Taylor Blau
2020-12-08 22:03   ` [PATCH v4 08/24] ewah: implement bitmap_or() Taylor Blau
2020-12-08 22:03   ` [PATCH v4 09/24] ewah: add bitmap_dup() function Taylor Blau
2020-12-08 22:03   ` [PATCH v4 10/24] pack-bitmap-write: reimplement bitmap writing Taylor Blau
2020-12-08 22:03   ` [PATCH v4 11/24] pack-bitmap-write: pass ownership of intermediate bitmaps Taylor Blau
2020-12-08 22:04   ` [PATCH v4 12/24] pack-bitmap-write: fill bitmap with commit history Taylor Blau
2020-12-08 22:04   ` [PATCH v4 13/24] bitmap: implement bitmap_is_subset() Taylor Blau
2020-12-08 22:04   ` [PATCH v4 14/24] commit: implement commit_list_contains() Taylor Blau
2020-12-08 22:04   ` [PATCH v4 15/24] t5310: add branch-based checks Taylor Blau
2020-12-08 22:04   ` [PATCH v4 16/24] pack-bitmap-write: rename children to reverse_edges Taylor Blau
2020-12-08 22:04   ` [PATCH v4 17/24] pack-bitmap.c: check reads more aggressively when loading Taylor Blau
2020-12-08 22:04   ` [PATCH v4 18/24] pack-bitmap-write: build fewer intermediate bitmaps Taylor Blau
2020-12-08 22:04   ` [PATCH v4 19/24] pack-bitmap-write: ignore BITMAP_FLAG_REUSE Taylor Blau
2020-12-08 22:04   ` [PATCH v4 20/24] pack-bitmap: factor out 'bitmap_for_commit()' Taylor Blau
2020-12-08 22:05     ` Taylor Blau
2020-12-08 22:05   ` [PATCH v4 21/24] pack-bitmap: factor out 'add_commit_to_bitmap()' Taylor Blau
2020-12-08 22:05   ` [PATCH v4 22/24] pack-bitmap-write: use existing bitmaps Taylor Blau
2020-12-08 22:05   ` [PATCH v4 23/24] pack-bitmap-write: relax unique revwalk condition Taylor Blau
2020-12-08 22:05   ` [PATCH v4 24/24] pack-bitmap-write: better reuse bitmaps Taylor Blau

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=X8KHEMl87sU5cIGK@nand.local \
    --to=me@ttaylorr.com \
    --cc=dstolee@microsoft.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jonathantanmy@google.com \
    --cc=martin.agren@gmail.com \
    --cc=peff@peff.net \
    --cc=szeder.dev@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 Mailing List Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/git/0 git/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 git git/ https://lore.kernel.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.git


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