[v2,11/24] pack-bitmap-write: pass ownership of intermediate bitmaps

Commit Message

Taylor Blau Nov. 17, 2020, 9:47 p.m. UTC

From: Jeff King <[e-mail]>

Our algorithm to generate reachability bitmaps walks through the commit
graph from the bottom up, passing bitmap data from each commit to its
descendants. For a linear stretch of history like:

  A -- B -- C

our sequence of steps is:

  - compute the bitmap for A by walking its trees, etc

  - duplicate A's bitmap as a starting point for B; we can now free A's
    bitmap, since we only needed it as an intermediate result

  - OR in any extra objects that B can reach into its bitmap

  - duplicate B's bitmap as a starting point for C; likewise, free B's
    bitmap

  - OR in objects for C, and so on...

Rather than duplicating bitmaps and immediately freeing the original, we
can just pass ownership from commit to commit. Note that this doesn't
always work:

  - the recipient may be a merge which already has an intermediate
    bitmap from its other ancestor. In that case we have to OR our
    result into it. Note that the first ancestor to reach the merge does
    get to pass ownership, though.

  - we may have multiple children; we can only pass ownership to one of
    them

However, it happens often enough and copying bitmaps is expensive enough
that this provides a noticeable speedup. On a clone of linux.git, this
reduces the time to generate bitmaps from 205s to 70s. This is about the
same amount of time it took to generate bitmaps using our old "many
traversals" algorithm (the previous commit measures the identical
scenario as taking 63s). It unfortunately provides only a very modest
reduction in the peak memory usage, though.

Signed-off-by: Jeff King <[e-mail]>
Signed-off-by: Taylor Blau <[e-mail]>
---
 pack-bitmap-write.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

Comments

Jonathan Tan Nov. 25, 2020, 1 a.m. UTC | #1

> diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
> index f2f0b6b2c2..d2d46ff5f4 100644
> --- a/pack-bitmap-write.c
> +++ b/pack-bitmap-write.c
> @@ -333,6 +333,7 @@ void bitmap_writer_build(struct packing_data *to_pack)
>  		struct commit *commit = bb.commits[i-1];
>  		struct bb_commit *ent = bb_data_at(&bb.data, commit);
>  		struct commit *child;
> +		int reused = 0;
>  
>  		fill_bitmap_commit(ent, commit);
>  

Before the following chunk is the start of a loop:

"while ((child = pop_commit(&ent->children))) {"

> @@ -348,10 +349,15 @@ void bitmap_writer_build(struct packing_data *to_pack)
>  
>  			if (child_ent->bitmap)
>  				bitmap_or(child_ent->bitmap, ent->bitmap);
> -			else
> +			else if (reused)
>  				child_ent->bitmap = bitmap_dup(ent->bitmap);
> +			else {
> +				child_ent->bitmap = ent->bitmap;
> +				reused = 1;
> +			}
>  		}
> -		bitmap_free(ent->bitmap);
> +		if (!reused)
> +			bitmap_free(ent->bitmap);
>  		ent->bitmap = NULL;
>  	}
>  	bitmap_builder_clear(&bb);
> -- 
> 2.29.2.312.gabc4d358d8

So this is clearly correct.

I asked myself if this optimization is worth it when we're going to
drastically reduce the number of steps in patch 18, but I think that the
answer is still yes.

Patch

diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index f2f0b6b2c2..d2d46ff5f4 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -333,6 +333,7 @@  void bitmap_writer_build(struct packing_data *to_pack)
 		struct commit *commit = bb.commits[i-1];
 		struct bb_commit *ent = bb_data_at(&bb.data, commit);
 		struct commit *child;
+		int reused = 0;
 
 		fill_bitmap_commit(ent, commit);
 
@@ -348,10 +349,15 @@  void bitmap_writer_build(struct packing_data *to_pack)
 
 			if (child_ent->bitmap)
 				bitmap_or(child_ent->bitmap, ent->bitmap);
-			else
+			else if (reused)
 				child_ent->bitmap = bitmap_dup(ent->bitmap);
+			else {
+				child_ent->bitmap = ent->bitmap;
+				reused = 1;
+			}
 		}
-		bitmap_free(ent->bitmap);
+		if (!reused)
+			bitmap_free(ent->bitmap);
 		ent->bitmap = NULL;
 	}
 	bitmap_builder_clear(&bb);