Git Mailing List Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH 00/23] pack-bitmap: bitmap generation improvements
@ 2020-11-11 19:41 Taylor Blau
  2020-11-11 19:41 ` [PATCH 01/23] ewah/ewah_bitmap.c: grow buffer past 1 Taylor Blau
                   ` (25 more replies)
  0 siblings, 26 replies; 174+ messages in thread
From: Taylor Blau @ 2020-11-11 19:41 UTC (permalink / raw)
  To: git; +Cc: dstolee, gitster, peff

This series contains some patches that GitHub has been using in its fork
for the past few months to improve generating reachability bitmaps,
particularly in pathological cases, such as the repo containing all
forks of chromium/chromium.

The patches that follow are organized into five parts:

  - The first nine patches do some basic clean-up and fix a bug that we
    were able to exercise in tests while writing these patches.

  - The next two patches reimplements bitmap writing in order to avoid making
    multiple passes over the object graph. This approach ends up
    regressing both the time and memory used to generate bitmaps on the
    kernel's fork-network, but ends up being a useful stepping stone for
    further improvements.

  - The six patches that follow that culminates in a patch to build
    fewer intermediate bitmaps during the walk in order to reduce both
    memory and time for reasonably-sized repositories. (Which
    intermediate bitmaps are considered "important" is discussed in
    detail in the seventeenth patch).

  - The next several patches make reusing previously generated reachability
    bitmaps purely an optimization for generating new bitmaps. Importantly, that
    allows the bitmap selection process to pick better commits to bitmap going
    forward, rather than blindly reusing previously selected ones. They also
    include some light refactoring, and a patch to avoid tree walks when
    existing bitmaps suffice.

  - The final two patches address a trade-off in the prior patches between
    walking a wide history only once with high memory cost, and walking the same
    history multiple times with lower memory cost. Here, the walk is reduced to
    only cover the first-parent history. The final patch treats existing bitmaps
    as maximal in order to make it more difficult for a different set of
    selected commits to "walk around" the previously selected commits and force
    a large number of new bitmaps to be computed.

In the end, no block-buster performance improvements are attained on
normal-to-large sized repositories, but the new bitmap generation routine helps
substantially on enormous repositories, like the chromium/chromium fork-network.

Individual performance numbers are available in the patches throughout.

This series is a prerequisite to a list of other bitmap-related patches in
GitHub's fork, including multi-pack bitmaps.

Derrick Stolee (9):
  pack-bitmap-write: fill bitmap with commit history
  bitmap: add bitmap_diff_nonzero()
  commit: implement commit_list_contains()
  t5310: add branch-based checks
  pack-bitmap-write: rename children to reverse_edges
  pack-bitmap-write: build fewer intermediate bitmaps
  pack-bitmap-write: use existing bitmaps
  pack-bitmap-write: relax unique rewalk condition
  pack-bitmap-write: better reuse bitmaps

Jeff King (11):
  pack-bitmap: fix header size check
  pack-bitmap: bounds-check size of cache extension
  t5310: drop size of truncated ewah bitmap
  rev-list: die when --test-bitmap detects a mismatch
  ewah: factor out bitmap growth
  ewah: make bitmap growth less aggressive
  ewah: implement bitmap_or()
  ewah: add bitmap_dup() function
  pack-bitmap-write: reimplement bitmap writing
  pack-bitmap-write: pass ownership of intermediate bitmaps
  pack-bitmap-write: ignore BITMAP_FLAG_REUSE

Taylor Blau (3):
  ewah/ewah_bitmap.c: grow buffer past 1
  pack-bitmap: factor out 'bitmap_for_commit()'
  pack-bitmap: factor out 'add_commit_to_bitmap()'

 builtin/pack-objects.c  |   1 -
 commit.c                |  11 +
 commit.h                |   2 +
 ewah/bitmap.c           |  54 ++++-
 ewah/ewah_bitmap.c      |   2 +-
 ewah/ewok.h             |   3 +-
 pack-bitmap-write.c     | 452 +++++++++++++++++++++++++---------------
 pack-bitmap.c           | 130 +++++-------
 pack-bitmap.h           |   8 +-
 t/t5310-pack-bitmaps.sh | 164 ++++++++++++---
 10 files changed, 548 insertions(+), 279 deletions(-)

--
2.29.2.156.gc03786897f

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

end of thread, back to index

Thread overview: 174+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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   `