git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 00/13] midx: incremental multi-pack indexes, part two
@ 2024-08-15 21:01 Taylor Blau
  2024-08-15 21:01 ` [PATCH 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
                   ` (16 more replies)
  0 siblings, 17 replies; 136+ messages in thread
From: Taylor Blau @ 2024-08-15 21:01 UTC (permalink / raw)
  To: git; +Cc: Jeff King, Elijah Newren, Junio C Hamano

This series is based on 'master', with an additional merge between
tb/incremental-midx-part-1[1] and my newer series to fix a handful of
bugs related to pseudo-merge bitmaps[2].

This is the second of three series to implement support for incremental
multi-pack indexes (MIDXs). This series brings support for bitmaps that
are tied to incremental MIDXs in addition to regular MIDX bitmaps.

The details are laid out in the commits themselves, but the high-level
approach is as follows:

  - Each layer in the incremental MIDX chain has its own corresponding
    *.bitmap file. Each bitmap contains commits / pseudo-merges which
    are selected only from the commits in that layer. Likewise, only
    that layer's objects are written in the type-level bitmaps.

  - The reachability traversal is only conducted on the top-most bitmap
    corresponding to the most recent layer in the incremental MIDX
    chain. Earlier layers may be consulted to retrieve commit /
    pseudo-merge reachability bitmaps, but only the top-most bitmap's
    "result" and "haves" fields are used.

  - In essence, the top-most bitmap is the only one that "matters", and
    earlier bitmaps are merely used to look up commit and pseudo-merge
    bitmaps from that layer.

  - Whenever we need to look at the type-level bitmaps corresponding to
    the whole incremental MIDX chain, a new "ewah_or_iterator" is used.
    This works in concept like a typical ewah_iterator, except works
    over many EWAH bitmaps in parallel, OR-ing their results together
    before returning them to the user.

    In effect, this allows us to treat the union of all type-level
    bitmaps (each of which only stores information about the objects its
    corresponding layer within the incremental MIDX chain) as a single
    type-level bitmap corresponding to all of the objects across every
    layer of the incremental MIDX chain.

The sum total of this series is that we are able to append new commits /
pseudo-merges to a repository's reachability bitmaps without having to
rewrite existing bitmaps, making the operation much cheaper to perform
in large repositories.

The series is laid out roughly as follows:

  - The first patch describes the technical details of incremental MIDX
    bitmaps.

  - The second patch adjusts the pack-revindex internals to prepare for
    incremental MIDX bitmaps.

  - The next seven patches adjust various components of the pack-bitmap
    internals to do the same.

  - The next three patches introduce and adjust callers to use the
    ewah_or_iterator (as above).

  - The final patch implements writing incremental MIDX bitmaps, and
    introduces tests.

After this series, the remaining goals for this project include being
able to compact contiguous runs of incremental MIDX layers into a single
layer to support growing the chain of MIDX layers without the chain
itself becoming too long.

Thanks in advance for your review!

[1]: https://lore.kernel.org/git/cover.1722958595.git.me@ttaylorr.com/
[2]: https://lore.kernel.org/git/cover.1723743050.git.me@ttaylorr.com/

Taylor Blau (13):
  Documentation: describe incremental MIDX bitmaps
  pack-revindex: prepare for incremental MIDX bitmaps
  pack-bitmap.c: open and store incremental bitmap layers
  pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs
  pack-bitmap.c: teach `show_objects_for_type()` about incremental MIDXs
  pack-bitmap.c: support bitmap pack-reuse with incremental MIDXs
  pack-bitmap.c: teach `rev-list --test-bitmap` about incremental MIDXs
  pack-bitmap.c: compute disk-usage with incremental MIDXs
  pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs
  ewah: implement `struct ewah_or_iterator`
  pack-bitmap.c: keep track of each layer's type bitmaps
  pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators
  midx: implement writing incremental MIDX bitmaps

 Documentation/technical/multi-pack-index.txt |  64 ++++
 builtin/pack-objects.c                       |   3 +-
 ewah/ewah_bitmap.c                           |  33 ++
 ewah/ewok.h                                  |  12 +
 midx-write.c                                 |  35 +-
 pack-bitmap-write.c                          |  65 +++-
 pack-bitmap.c                                | 328 ++++++++++++++-----
 pack-bitmap.h                                |   4 +-
 pack-revindex.c                              |  32 +-
 t/t5334-incremental-multi-pack-index.sh      |  84 +++++
 10 files changed, 548 insertions(+), 112 deletions(-)


base-commit: f28e4ef872c247b0b35f48b1c3d2c5f77753b908
-- 
2.46.0.86.ge766d390f0.dirty

^ permalink raw reply	[flat|nested] 136+ messages in thread

end of thread, other threads:[~2025-03-26 18:08 UTC | newest]

Thread overview: 136+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-08-15 21:01 [PATCH 00/13] midx: incremental multi-pack indexes, part two Taylor Blau
2024-08-15 21:01 ` [PATCH 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2024-08-15 21:01 ` [PATCH 02/13] pack-revindex: prepare for " Taylor Blau
2024-08-15 21:01 ` [PATCH 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2024-08-15 21:01 ` [PATCH 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2024-08-15 21:01 ` [PATCH 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2024-08-15 21:01 ` [PATCH 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2024-08-15 21:01 ` [PATCH 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2024-08-15 21:01 ` [PATCH 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2024-08-15 21:01 ` [PATCH 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2024-08-15 21:01 ` [PATCH 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2024-08-15 21:01 ` [PATCH 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2024-08-15 21:01 ` [PATCH 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2024-08-15 21:01 ` [PATCH 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2024-08-15 22:28 ` [PATCH v2 00/13] midx: incremental multi-pack indexes, part two Taylor Blau
2024-08-15 22:28   ` [PATCH v2 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2024-08-15 22:28   ` [PATCH v2 02/13] pack-revindex: prepare for " Taylor Blau
2024-08-15 22:28   ` [PATCH v2 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2024-08-15 22:29   ` [PATCH v2 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2024-08-15 22:29   ` [PATCH v2 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2024-08-15 22:29   ` [PATCH v2 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2024-08-15 22:29   ` [PATCH v2 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2024-08-15 22:29   ` [PATCH v2 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2024-08-15 22:29   ` [PATCH v2 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2024-08-15 22:29   ` [PATCH v2 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2024-08-15 22:29   ` [PATCH v2 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2024-08-15 22:29   ` [PATCH v2 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2024-08-15 22:29   ` [PATCH v2 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2024-08-28 17:55     ` [PATCH] fixup! " Junio C Hamano
2024-08-28 18:33       ` Jeff King
2024-08-29 18:57         ` Taylor Blau
2024-08-29 19:27           ` Jeff King
2024-11-19 20:56             ` Taylor Blau
2024-11-19 22:07 ` [PATCH v3 00/13] midx: incremental multi-pack indexes, part two Taylor Blau
2024-11-19 22:07   ` [PATCH v3 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-02-28 23:26       ` Taylor Blau
2025-03-03 10:54         ` Patrick Steinhardt
2024-11-19 22:07   ` [PATCH v3 02/13] pack-revindex: prepare for " Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-02-28 23:39       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-02-28 23:49       ` Taylor Blau
2025-03-03 10:55         ` Patrick Steinhardt
2024-11-19 22:07   ` [PATCH v3 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:12       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2024-11-19 22:07   ` [PATCH v3 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:16       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:19       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2024-11-19 22:07   ` [PATCH v3 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2024-11-19 22:07   ` [PATCH v3 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:22       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:26       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:28       ` Taylor Blau
2024-11-19 22:07   ` [PATCH v3 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2025-02-28 10:01     ` Patrick Steinhardt
2025-03-01  0:31       ` Taylor Blau
2024-11-20  8:49   ` [PATCH v3 00/13] midx: incremental multi-pack indexes, part two Junio C Hamano
2025-03-14 20:18 ` [PATCH v4 " Taylor Blau
2025-03-14 20:18   ` [PATCH v4 01/13] Documentation: describe incremental MIDX bitmaps Taylor Blau
2025-03-18  1:16     ` Jeff King
2025-03-18 23:11       ` Taylor Blau
2025-03-18  2:42     ` Elijah Newren
2025-03-18 23:19       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 02/13] pack-revindex: prepare for " Taylor Blau
2025-03-18  1:27     ` Jeff King
2025-03-19  0:02       ` Taylor Blau
2025-03-19  0:07         ` Taylor Blau
2025-03-26 18:08           ` Jeff King
2025-03-18  2:43     ` Elijah Newren
2025-03-19  0:03       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 03/13] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2025-03-18  4:13     ` Elijah Newren
2025-03-19  0:08       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2025-03-18  1:38     ` Jeff King
2025-03-19  0:13       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 05/13] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2025-03-14 20:18   ` [PATCH v4 06/13] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2025-03-18  4:13     ` Elijah Newren
2025-03-19  0:17       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2025-03-18  5:31     ` Elijah Newren
2025-03-19  0:30       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 08/13] pack-bitmap.c: compute disk-usage with " Taylor Blau
2025-03-18  1:41     ` Jeff King
2025-03-19  0:30       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 09/13] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2025-03-14 20:18   ` [PATCH v4 10/13] ewah: implement `struct ewah_or_iterator` Taylor Blau
2025-03-18  1:44     ` Jeff King
2025-03-19  0:33       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2025-03-18  2:01     ` Jeff King
2025-03-19  0:38       ` Taylor Blau
2025-03-18  6:43     ` Elijah Newren
2025-03-19  0:39       ` Taylor Blau
2025-03-14 20:18   ` [PATCH v4 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2025-03-18  2:05     ` Jeff King
2025-03-19 23:02       ` Taylor Blau
2025-03-14 20:19   ` [PATCH v4 13/13] midx: implement writing incremental MIDX bitmaps Taylor Blau
2025-03-18  2:16     ` Jeff King
2025-03-20  0:14       ` Taylor Blau
2025-03-18 17:13     ` Elijah Newren
2025-03-20  0:16       ` Taylor Blau
2025-03-18  2:21   ` [PATCH v4 00/13] midx: incremental multi-pack indexes, part two Jeff King
2025-03-20  0:18     ` Taylor Blau
2025-03-20 17:56 ` [PATCH v5 00/14] " Taylor Blau
2025-03-20 17:56   ` [PATCH v5 01/14] Documentation: remove a "future work" item from the MIDX docs Taylor Blau
2025-03-20 17:56   ` [PATCH v5 02/14] Documentation: describe incremental MIDX bitmaps Taylor Blau
2025-03-20 17:56   ` [PATCH v5 03/14] pack-revindex: prepare for " Taylor Blau
2025-03-20 17:56   ` [PATCH v5 04/14] pack-bitmap.c: open and store incremental bitmap layers Taylor Blau
2025-03-20 17:56   ` [PATCH v5 05/14] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Taylor Blau
2025-03-20 17:56   ` [PATCH v5 06/14] pack-bitmap.c: teach `show_objects_for_type()` " Taylor Blau
2025-03-20 17:56   ` [PATCH v5 07/14] pack-bitmap.c: support bitmap pack-reuse with " Taylor Blau
2025-03-20 17:56   ` [PATCH v5 08/14] pack-bitmap.c: teach `rev-list --test-bitmap` about " Taylor Blau
2025-03-20 17:56     ` Taylor Blau
2025-03-20 17:58       ` Taylor Blau
2025-03-20 17:56   ` [PATCH v5 09/14] pack-bitmap.c: compute disk-usage with " Taylor Blau
2025-03-20 17:56   ` [PATCH v5 10/14] pack-bitmap.c: apply pseudo-merge commits " Taylor Blau
2025-03-20 17:56   ` [PATCH v5 11/14] ewah: implement `struct ewah_or_iterator` Taylor Blau
2025-03-20 17:57   ` [PATCH v5 12/14] pack-bitmap.c: keep track of each layer's type bitmaps Taylor Blau
2025-03-20 17:57   ` [PATCH v5 13/14] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Taylor Blau
2025-03-20 17:57   ` [PATCH v5 14/14] midx: implement writing incremental MIDX bitmaps Taylor Blau
2025-03-20 20:00   ` [PATCH v5 00/14] midx: incremental multi-pack indexes, part two Elijah Newren

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).