git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format
@ 2022-06-20 12:33 Abhradeep Chakraborty via GitGitGadget
  2022-06-20 12:33 ` [PATCH 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
                   ` (6 more replies)
  0 siblings, 7 replies; 162+ messages in thread
From: Abhradeep Chakraborty via GitGitGadget @ 2022-06-20 12:33 UTC (permalink / raw)
  To: git; +Cc: Taylor Blau, Kaartic Sivaram, Abhradeep Chakraborty

When parsing the .bitmap file, git loads all the bitmaps one by one even if
some of the bitmaps are not necessary. We can remove this overhead by
loading only the necessary bitmaps. A look up table extension can solve this
issue.

The proposed table has:

 * a list of nr_entries object ids. These objects are commits that has
   bitmaps. Ids are stored in lexicographic order (for better searching).
 * a list of <offset, xor-offset> pairs (4-byte integers, network-byte
   order). The i'th pair denotes the offset and xor-offset(respectively) of
   the bitmap of i'th commit in the previous list. These two informations
   are necessary because only in this way bitmaps can be found without
   parsing all the bitmap.
 * a 4-byte integer for table specific flags (none exists currently).

Whenever git want to parse the bitmap for a specific commit, it will first
refer to the table and will look for the offset and xor-offset for that
commit. Git will then try to parse the bitmap located at the offset
position. The xor-offset can be used to find the xor-bitmap for the
bitmap(if any). This process is recursive and will end if xor-offset is null
(i.e. there is no xor-bitmap left).

Abhradeep Chakraborty (5):
  Documentation/technical: describe bitmap lookup table extension
  pack-bitmap: prepare to read lookup table extension
  pack-bitmap-write.c: write lookup table extension
  bitmap-commit-table: add tests for the bitmap lookup table
  bitmap-lookup-table: add performance tests

Taylor Blau (1):
  builtin/pack-objects.c: learn pack.writeBitmapLookupTable

 Documentation/config/pack.txt             |   7 +
 Documentation/technical/bitmap-format.txt |  31 ++++
 builtin/pack-objects.c                    |   8 +
 pack-bitmap-write.c                       |  59 +++++++-
 pack-bitmap.c                             | 172 +++++++++++++++++++++-
 pack-bitmap.h                             |   1 +
 t/perf/p5310-pack-bitmaps.sh              |  60 +++++---
 t/perf/p5326-multi-pack-bitmaps.sh        |  55 ++++---
 t/t5310-pack-bitmaps.sh                   |  14 ++
 t/t5326-multi-pack-bitmaps.sh             |  19 +++
 10 files changed, 375 insertions(+), 51 deletions(-)


base-commit: 5699ec1b0aec51b9e9ba5a2785f65970c5a95d84
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1266%2FAbhra303%2Fbitmap-commit-table-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1266/Abhra303/bitmap-commit-table-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1266
-- 
gitgitgadget

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

end of thread, other threads:[~2022-08-26 16:02 UTC | newest]

Thread overview: 162+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-06-20 12:33 [PATCH 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Abhradeep Chakraborty via GitGitGadget
2022-06-20 12:33 ` [PATCH 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-06-20 16:56   ` Derrick Stolee
2022-06-20 17:09     ` Taylor Blau
2022-06-21  8:31       ` Abhradeep Chakraborty
2022-06-22 16:26         ` Taylor Blau
2022-06-21  8:23     ` Abhradeep Chakraborty
2022-06-20 17:21   ` Taylor Blau
2022-06-21  9:22     ` Abhradeep Chakraborty
2022-06-22 16:29       ` Taylor Blau
2022-06-22 16:45         ` Abhradeep Chakraborty
2022-06-20 20:21   ` Derrick Stolee
2022-06-21 10:08     ` Abhradeep Chakraborty
2022-06-22 16:30       ` Taylor Blau
2022-06-20 12:33 ` [PATCH 2/6] pack-bitmap: prepare to read " Abhradeep Chakraborty via GitGitGadget
2022-06-20 20:49   ` Derrick Stolee
2022-06-21 10:28     ` Abhradeep Chakraborty
2022-06-20 22:06   ` Taylor Blau
2022-06-21 11:52     ` Abhradeep Chakraborty
2022-06-22 16:49       ` Taylor Blau
2022-06-22 17:18         ` Abhradeep Chakraborty
2022-06-22 21:34           ` Taylor Blau
2022-06-20 12:33 ` [PATCH 3/6] pack-bitmap-write.c: write " Abhradeep Chakraborty via GitGitGadget
2022-06-20 22:16   ` Taylor Blau
2022-06-21 12:50     ` Abhradeep Chakraborty
2022-06-22 16:51       ` Taylor Blau
2022-06-20 12:33 ` [PATCH 4/6] builtin/pack-objects.c: learn pack.writeBitmapLookupTable Taylor Blau via GitGitGadget
2022-06-20 22:18   ` Taylor Blau
2022-06-20 12:33 ` [PATCH 5/6] bitmap-commit-table: add tests for the bitmap lookup table Abhradeep Chakraborty via GitGitGadget
2022-06-22 16:54   ` Taylor Blau
2022-06-20 12:33 ` [PATCH 6/6] bitmap-lookup-table: add performance tests Abhradeep Chakraborty via GitGitGadget
2022-06-22 17:14   ` Taylor Blau
2022-06-26 13:10 ` [PATCH v2 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Abhradeep Chakraborty via GitGitGadget
2022-06-26 13:10   ` [PATCH v2 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-06-27 14:18     ` Derrick Stolee
2022-06-27 15:48       ` Taylor Blau
2022-06-27 16:51       ` Abhradeep Chakraborty
2022-06-26 13:10   ` [PATCH v2 2/6] pack-bitmap-write.c: write " Abhradeep Chakraborty via GitGitGadget
2022-06-27 14:35     ` Derrick Stolee
2022-06-27 16:12       ` Taylor Blau
2022-06-27 17:10       ` Abhradeep Chakraborty
2022-06-27 16:05     ` Taylor Blau
2022-06-27 18:29       ` Abhradeep Chakraborty
2022-06-26 13:10   ` [PATCH v2 3/6] pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests Abhradeep Chakraborty via GitGitGadget
2022-06-27 14:43     ` Derrick Stolee
2022-06-27 17:42       ` Abhradeep Chakraborty
2022-06-27 17:49         ` Taylor Blau
2022-06-27 17:47     ` Taylor Blau
2022-06-27 18:39       ` Abhradeep Chakraborty
2022-06-29 20:11         ` Taylor Blau
2022-06-26 13:10   ` [PATCH v2 4/6] pack-bitmap: prepare to read lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-06-27 15:12     ` Derrick Stolee
2022-06-27 18:06       ` [PATCH v2 4/6] pack-bitmap: prepare to read lookup table Abhradeep Chakraborty
2022-06-27 18:32         ` Derrick Stolee
2022-06-27 21:49       ` [PATCH v2 4/6] pack-bitmap: prepare to read lookup table extension Taylor Blau
2022-06-28  8:59         ` [PATCH v2 4/6] pack-bitmap: prepare to read lookup table Abhradeep Chakraborty
2022-06-29 20:22           ` Taylor Blau
2022-06-30  6:58             ` [PATCH v2 4/6] pack-bitmap: prepare to read lookup table extension Abhradeep Chakraborty
2022-06-27 21:38     ` Taylor Blau
2022-06-28 19:25       ` Abhradeep Chakraborty
2022-06-29 20:37         ` Taylor Blau
2022-06-29 20:41           ` Taylor Blau
2022-06-30  8:35           ` Abhradeep Chakraborty
2022-06-26 13:10   ` [PATCH v2 5/6] bitmap-lookup-table: add performance tests for lookup table Abhradeep Chakraborty via GitGitGadget
2022-06-27 21:53     ` Taylor Blau
2022-06-28  7:58       ` Abhradeep Chakraborty
2022-06-29 20:40         ` Taylor Blau
2022-06-26 13:10   ` [PATCH v2 6/6] p5310-pack-bitmaps.sh: enable pack.writeReverseIndex for testing Abhradeep Chakraborty via GitGitGadget
2022-06-27 21:50     ` Taylor Blau
2022-06-28  8:01       ` Abhradeep Chakraborty
2022-07-04  8:46   ` [PATCH v3 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Abhradeep Chakraborty via GitGitGadget
2022-07-04  8:46     ` [PATCH v3 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-07-08 16:38       ` Philip Oakley
2022-07-09  7:53         ` Abhradeep Chakraborty
2022-07-10 15:01           ` Philip Oakley
2022-07-14 23:15             ` Taylor Blau
2022-07-15 10:36               ` Philip Oakley
2022-07-15 18:48             ` Abhradeep Chakraborty
2022-07-04  8:46     ` [PATCH v3 2/6] pack-bitmap-write.c: write " Abhradeep Chakraborty via GitGitGadget
2022-07-14 23:26       ` Taylor Blau
2022-07-15  2:22       ` Taylor Blau
2022-07-15 15:58         ` Abhradeep Chakraborty
2022-07-15 22:15           ` Taylor Blau
2022-07-16 11:50             ` Abhradeep Chakraborty
2022-07-26  0:34               ` Taylor Blau
2022-07-18  8:59       ` Martin Ågren
2022-07-04  8:46     ` [PATCH v3 3/6] pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests Abhradeep Chakraborty via GitGitGadget
2022-07-04  8:46     ` [PATCH v3 4/6] pack-bitmap: prepare to read lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-07-15  2:46       ` Taylor Blau
2022-07-15 16:38         ` Abhradeep Chakraborty
2022-07-15 22:20           ` Taylor Blau
2022-07-18  9:06             ` Martin Ågren
2022-07-18 19:25               ` Abhradeep Chakraborty
2022-07-18 23:26                 ` Martin Ågren
2022-07-26  0:45               ` Taylor Blau
2022-07-04  8:46     ` [PATCH v3 5/6] bitmap-lookup-table: add performance tests for lookup table Abhradeep Chakraborty via GitGitGadget
2022-07-15  2:53       ` Taylor Blau
2022-07-15 18:23         ` Abhradeep Chakraborty
2022-07-04  8:46     ` [PATCH v3 6/6] p5310-pack-bitmaps.sh: remove pack.writeReverseIndex Abhradeep Chakraborty via GitGitGadget
2022-07-04 16:35     ` [PATCH v3 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Abhradeep Chakraborty
2022-07-06 19:21     ` Junio C Hamano
2022-07-07  8:48       ` Abhradeep Chakraborty
2022-07-07 18:09         ` Kaartic Sivaraam
2022-07-07 18:42           ` Abhradeep Chakraborty
2022-07-20 14:05     ` [PATCH v4 " Abhradeep Chakraborty via GitGitGadget
2022-07-20 14:05       ` [PATCH v4 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-07-20 14:05       ` [PATCH v4 2/6] pack-bitmap-write.c: write " Abhradeep Chakraborty via GitGitGadget
2022-07-20 14:05       ` [PATCH v4 3/6] pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests Abhradeep Chakraborty via GitGitGadget
2022-07-20 14:05       ` [PATCH v4 4/6] pack-bitmap: prepare to read lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-07-20 14:05       ` [PATCH v4 5/6] p5310-pack-bitmaps.sh: enable `pack.writeReverseIndex` Abhradeep Chakraborty via GitGitGadget
2022-07-20 14:05       ` [PATCH v4 6/6] bitmap-lookup-table: add performance tests for lookup table Abhradeep Chakraborty via GitGitGadget
2022-07-20 18:38       ` [PATCH v5 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Abhradeep Chakraborty via GitGitGadget
2022-07-20 18:38         ` [PATCH v5 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-07-20 18:38         ` [PATCH v5 2/6] pack-bitmap-write.c: write " Abhradeep Chakraborty via GitGitGadget
2022-07-26  0:52           ` Taylor Blau
2022-07-26 18:22             ` Abhradeep Chakraborty
2022-07-20 18:38         ` [PATCH v5 3/6] pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests Abhradeep Chakraborty via GitGitGadget
2022-07-28 19:22           ` Johannes Schindelin
2022-08-02 12:40             ` Abhradeep Chakraborty
2022-08-02 15:35               ` Johannes Schindelin
2022-08-02 17:44                 ` Abhradeep Chakraborty
2022-08-08 13:06                   ` Johannes Schindelin
2022-08-08 13:58                     ` Abhradeep Chakraborty
2022-08-09  9:03                       ` Johannes Schindelin
2022-08-09 12:03                         ` Abhradeep Chakraborty
2022-08-09 12:07                           ` Abhradeep Chakraborty
2022-08-10  9:09                           ` Johannes Schindelin
2022-08-10  9:20                             ` Johannes Schindelin
2022-08-10 10:04                               ` Abhradeep Chakraborty
2022-08-10 17:51                                 ` Derrick Stolee
2022-08-12 18:51                                   ` Abhradeep Chakraborty
2022-08-12 19:22                                     ` Derrick Stolee
2022-08-13 10:59                                       ` Abhradeep Chakraborty
2022-08-16 21:57                                         ` Taylor Blau
2022-08-17 10:02                                           ` Abhradeep Chakraborty
2022-08-17 20:38                                             ` Taylor Blau
2022-08-19 21:49                                               ` Taylor Blau
2022-08-13 11:05                               ` Abhradeep Chakraborty
2022-08-16 18:47                             ` Taylor Blau
2022-07-20 18:38         ` [PATCH v5 4/6] pack-bitmap: prepare to read lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-07-26  1:13           ` Taylor Blau
2022-07-26 18:56             ` Abhradeep Chakraborty
2022-07-26 19:36             ` Eric Sunshine
2022-07-20 18:38         ` [PATCH v5 5/6] p5310-pack-bitmaps.sh: enable `pack.writeReverseIndex` Abhradeep Chakraborty via GitGitGadget
2022-07-26  1:18           ` Taylor Blau
2022-07-26  7:15             ` Ævar Arnfjörð Bjarmason
2022-07-26 13:32               ` Derrick Stolee
2022-07-26 13:54                 ` Ævar Arnfjörð Bjarmason
2022-07-26 18:17                   ` Abhradeep Chakraborty
2022-07-20 18:38         ` [PATCH v5 6/6] bitmap-lookup-table: add performance tests for lookup table Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55         ` [PATCH v6 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55           ` [PATCH v6 1/6] Documentation/technical: describe bitmap lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55           ` [PATCH v6 2/6] bitmap: move `get commit positions` code to `bitmap_writer_finish` Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55           ` [PATCH v6 3/6] pack-bitmap-write.c: write lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55           ` [PATCH v6 4/6] pack-bitmap-write: learn pack.writeBitmapLookupTable and add tests Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55           ` [PATCH v6 5/6] pack-bitmap: prepare to read lookup table extension Abhradeep Chakraborty via GitGitGadget
2022-08-14 16:55           ` [PATCH v6 6/6] bitmap-lookup-table: add performance tests for lookup table Abhradeep Chakraborty via GitGitGadget
2022-08-19 21:21           ` [PATCH v6 0/6] [GSoC] bitmap: integrate a lookup table extension to the bitmap format Junio C Hamano
2022-08-22 14:42             ` Johannes Schindelin
2022-08-22 14:48               ` Taylor Blau
2022-08-25 22:16           ` Taylor Blau
2022-08-26 16:02             ` Junio C Hamano

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