Re: [PATCH 17/23] pack-bitmap-write: build fewer intermediate bitmaps

From: SZEDER Gábor <szeder.dev@gmail.com>
Date: Nov 13, 2020, 22:23 UTC
Message-ID: <20201113222328.GA8033@szeder.dev>
In-Reply-To: <ab64354851e2aa61e901e37814b2ae33d8f855d1.1605123653.git.me@ttaylorr.com>

On Wed, Nov 11, 2020 at 02:43:51PM -0500, Taylor Blau wrote:

Show 19 quoted lines

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> The bitmap_writer_build() method calls bitmap_builder_init() to
> construct a list of commits reachable from the selected commits along
> with a "reverse graph". This reverse graph has edges pointing from a
> commit to other commits that can reach that commit. After computing a
> reachability bitmap for a commit, the values in that bitmap are then
> copied to the reachability bitmaps across the edges in the reverse
> graph.
> 
> We can now relax the role of the reverse graph to greatly reduce the
> number of intermediate reachability bitmaps we compute during this
> reverse walk. The end result is that we walk objects the same number of
> times as before when constructing the reachability bitmaps, but we also
> spend much less time copying bits between bitmaps and have much lower
> memory pressure in the process.
> 
> The core idea is to select a set of "important" commits based on
> interactions among the sets of commits reachable from each selected commit.

This patch breaks the test 'truncated bitmap fails gracefully (ewah)' when run with GIT_TEST_DEFAULT_HASH=sha256:

  expecting success of 5310.66 'truncated bitmap fails gracefully (ewah)':
          test_config pack.writebitmaphashcache false &&
          git repack -ad &&
          git rev-list --use-bitmap-index --count --all >expect &&
          bitmap=$(ls .git/objects/pack/*.bitmap) &&
          test_when_finished "rm -f $bitmap" &&
          test_copy_bytes 256 <$bitmap >$bitmap.tmp &&
          mv -f $bitmap.tmp $bitmap &&
          git rev-list --use-bitmap-index --count --all >actual 2>stderr &&
          test_cmp expect actual &&
          test_i18ngrep corrupt.ewah.bitmap stderr
  
  + test_config pack.writebitmaphashcache false
  + git repack -ad
  + git rev-list --use-bitmap-index --count --all
  + ls .git/objects/pack/pack-23fe19963d67a1d4797a39622c15144bbf35ab76a2c0638ba9288cc688c24c16.bitmap
  + bitmap=.git/objects/pack/pack-23fe19963d67a1d4797a39622c15144bbf35ab76a2c0638ba9288cc688c24c16.bitmap
  + test_when_finished rm -f .git/objects/pack/pack-23fe19963d67a1d4797a39622c15144bbf35ab76a2c0638ba9288cc688c24c16.bitmap
  + test_copy_bytes 256
  + mv -f .git/objects/pack/pack-23fe19963d67a1d4797a39622c15144bbf35ab76a2c0638ba9288cc688c24c16.bitmap.tmp .git/objects/pack/pack-23fe19963d67a1d4797a39622c15144bbf35ab76a2c0638ba9288cc688c24c16.bitmap
  + git rev-list --use-bitmap-index --count --all
  + test_cmp expect actual
  --- expect      2020-11-13 22:20:39.246355100 +0000
  +++ actual      2020-11-13 22:20:39.254355294 +0000
  @@ -1 +1 @@
  -239
  +236
  error: last command exited with $?=1