Re: [PATCH 2/2 v7] pack-objects: use reachability bitmap index when generating non-stdout pack

[Junio C Hamano]

Kirill Smelkov  writes:

>> This is v7, but as I understand your numbering, it goes with v5 of patch
>> 1/2 that I just reviewed (usually we just increment the version number
>> on the whole series and treat it as a unit, even if some patches didn't
>> change from version to version).
>
> The reason those patches are having their own numbers is that they are
> orthogonal to each other and can be applied / rejected independently.

In such a case, we wouldn't label them 1/2 and 2/2, which tells the
readers that these are two pieces that are to be applied together to
form a single unit of change.  That was what these numbered patches
with different version numbers confusing.

> But ok, since now we have them considered both together, their next
> versions posted will be uniform v8.

OK.  Thanks for clarifying.

Re: [PATCH 2/2 v7] pack-objects: use reachability bitmap index when generating non-stdout pack

[Kirill Smelkov]

On Thu, Aug 18, 2016 at 02:06:15PM -0400, Jeff King wrote:
> On Tue, Aug 09, 2016 at 10:32:17PM +0300, Kirill Smelkov wrote:
> 
> > Subject: Re: [PATCH 2/2 v7] pack-objects: use reachability bitmap index when
> >    generating non-stdout pack
> 
> This is v7, but as I understand your numbering, it goes with v5 of patch
> 1/2 that I just reviewed (usually we just increment the version number
> on the whole series and treat it as a unit, even if some patches didn't
> change from version to version).

The reason those patches are having their own numbers is that they are
orthogonal to each other and can be applied / rejected independently.
Since I though Junio might want to pick them up as separate topics they
were versioned separately.

But ok, since now we have them considered both together, their next
versions posted will be uniform v8.


> > So we can teach pack-objects to use bitmap index for initial object
> > counting phase when generating resultant pack file too:
> > 
> > - if we care it is not activated under git-repack:
> 
> Do you mean "if we take care that it is not..." here?
> 
> (I think you might just be getting tripped up in the English idioms;
> "care" means that we have a preference; "to take care" means that we are
> being careful).

Ok, I've might have been tripped and thanks for the catch up. I've changed to

"if we take care to not let it be activated under git-repack"

> 
> > - if we know bitmap index generation is not enabled for resultant pack:
> > 
> >   Current code has singleton bitmap_git so cannot work simultaneously
> >   with two bitmap indices.
> 
> Minor English fixes:
> 
>   The current code has a singleton bitmap_git, so it cannot work
>   simultaneously with two bitmap indices.

ok.

> > - if we keep pack reuse enabled still only for "send-to-stdout" case:
> > 
> >   Because on pack reuse raw entries are directly written out to destination
> >   pack by write_reused_pack() bypassing needed for pack index generation
> >   bookkeeping done by regular codepath in write_one() and friends.
> 
> Ditto on English:
> 
>   On pack reuse raw entries are directly written out to the destination
>   pack by write_reused_pack(), bypassing the need for pack index
>   generation bookkeeping done by the regular code path in write_one()
>   and friends.
> 
> I think this is missing the implication. Why wouldn't we want to reuse
> in this case? Certainly we don't when doing a "careful" on-disk repack.
> I suspect the answer is that we cannot write a ".idx" off of the result
> of write_reused_pack(), and write-to-disk always includes the .idx.

Yes, mentioning pack-to-file needs to generate .idx makes it more clear
and thanks for pointing this out. I've changed this item to the
following (picking some of your English corrections):

- if we keep pack reuse enabled still only for "send-to-stdout" case:

  Because pack-to-file needs to generate index for destination pack, and
  currently on pack reuse raw entries are directly written out to the
  destination pack by write_reused_pack(), bypassing needed for pack index
  generation bookkeeping done by regular codepath in write_one() and
  friends.

  ( In the future we might teach pack-reuse code about cases when index
also needs to be generated for resultant pack and remove
pack-reuse-only-for-stdout limitation )

Hope it is ok.

> > More context:
> > 
> > http://marc.info/?t=14679210141=1=2
> 
> Can we turn this into a link to public-inbox? We have just been bit by
> all of our old links to gmane dying, and they cannot easily be replaced
> because they use a gmane-specific article number. public-inbox URLs use
> message-ids, which should be usable for other archives if public-inbox
> goes away.

Yes, makes sense to put msgid here. I've added

http://public-inbox.org/git/20160707190917.20011-1-k...@nexedi.com/T/#t


> > diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> > index b1007f2..c92d7fc 100644
> > --- a/builtin/pack-objects.c
> > +++ b/builtin/pack-objects.c
> 
> The code here looks fine.

Thanks.

> > diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
> > index a278d30..9602e9a 100755
> > --- a/t/t5310-pack-bitmaps.sh
> > +++ b/t/t5310-pack-bitmaps.sh
> > @@ -196,6 +196,18 @@ test_expect_success 'pack-objects respects --local 
> > (non-local bitmapped pack)' '
> > ! has_any packbitmap.objects 3b.objects
> >  '
> >  
> > +test_expect_success 'pack-objects to file can use bitmap' '
> > +   # make sure we still have 1 bitmap index from previo

Re: [PATCH 2/2 v7] pack-objects: use reachability bitmap index when generating non-stdout pack

[Jeff King]

On Tue, Aug 09, 2016 at 10:32:17PM +0300, Kirill Smelkov wrote:

> Subject: Re: [PATCH 2/2 v7] pack-objects: use reachability bitmap index when
>generating non-stdout pack

This is v7, but as I understand your numbering, it goes with v5 of patch
1/2 that I just reviewed (usually we just increment the version number
on the whole series and treat it as a unit, even if some patches didn't
change from version to version).

> So we can teach pack-objects to use bitmap index for initial object
> counting phase when generating resultant pack file too:
> 
> - if we care it is not activated under git-repack:

Do you mean "if we take care that it is not..." here?

(I think you might just be getting tripped up in the English idioms;
"care" means that we have a preference; "to take care" means that we are
being careful).

> - if we know bitmap index generation is not enabled for resultant pack:
> 
>   Current code has singleton bitmap_git so cannot work simultaneously
>   with two bitmap indices.

Minor English fixes:

  The current code has a singleton bitmap_git, so it cannot work
  simultaneously with two bitmap indices.

> - if we keep pack reuse enabled still only for "send-to-stdout" case:
> 
>   Because on pack reuse raw entries are directly written out to destination
>   pack by write_reused_pack() bypassing needed for pack index generation
>   bookkeeping done by regular codepath in write_one() and friends.

Ditto on English:

  On pack reuse raw entries are directly written out to the destination
  pack by write_reused_pack(), bypassing the need for pack index
  generation bookkeeping done by the regular code path in write_one()
  and friends.

I think this is missing the implication. Why wouldn't we want to reuse
in this case? Certainly we don't when doing a "careful" on-disk repack.
I suspect the answer is that we cannot write a ".idx" off of the result
of write_reused_pack(), and write-to-disk always includes the .idx.

> More context:
> 
> http://marc.info/?t=14679210141=1=2

Can we turn this into a link to public-inbox? We have just been bit by
all of our old links to gmane dying, and they cannot easily be replaced
because they use a gmane-specific article number. public-inbox URLs use
message-ids, which should be usable for other archives if public-inbox
goes away.

> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
> index b1007f2..c92d7fc 100644
> --- a/builtin/pack-objects.c
> +++ b/builtin/pack-objects.c

The code here looks fine.

> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
> index a278d30..9602e9a 100755
> --- a/t/t5310-pack-bitmaps.sh
> +++ b/t/t5310-pack-bitmaps.sh
> @@ -196,6 +196,18 @@ test_expect_success 'pack-objects respects --local 
> (non-local bitmapped pack)' '
>   ! has_any packbitmap.objects 3b.objects
>  '
>  
> +test_expect_success 'pack-objects to file can use bitmap' '
> + # make sure we still have 1 bitmap index from previous tests
> + ls .git/objects/pack/ | grep bitmap >output &&
> + test_line_count = 1 output &&
> + # verify equivalent packs are generated with/without using bitmap index
> + packasha1=$(git pack-objects --no-use-bitmap-index --all packa 
>  + packbsha1=$(git pack-objects --use-bitmap-index --all packb  &&
> + list_packed_objects <packa-$packasha1.idx >packa.objects &&
> + list_packed_objects <packb-$packbsha1.idx >packb.objects &&
> + test_cmp packa.objects packb.objects
> +'

Of course we can't know if bitmaps were actually used, or if they were
turned off under the hood. But at least this exercises the code a bit.

You could possibly add a perf test which shows off the improvement, but
I don't think it's strictly necessary.

-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 2/2 v7] pack-objects: use reachability bitmap index when generating non-stdout pack

[Kirill Smelkov]

Starting from 6b8fda2d (pack-objects: use bitmaps when packing objects)
if a repository has bitmap index, pack-objects can nicely speedup
"Counting objects" graph traversal phase. That however was done only for
case when resultant pack is sent to stdout, not written into a file.

The reason here is for on-disk repack by default we want:

- to produce good pack (with bitmap index not-yet-packed objects are
  emitted to pack in suboptimal order).

- to use more robust pack-generation codepath (avoiding possible
  bugs in bitmap code and possible bitmap index corruption).

Jeff King further explains:

The reason for this split is that pack-objects tries to determine how
"careful" it should be based on whether we are packing to disk or to
stdout. Packing to disk implies "git repack", and that we will likely
delete the old packs after finishing. We want to be more careful (so
as not to carry forward a corruption, and to generate a more optimal
pack), and we presumably run less frequently and can afford extra CPU.
Whereas packing to stdout implies serving a remote via "git fetch" or
"git push". This happens more frequently (e.g., a server handling many
fetching clients), and we assume the receiving end takes more
responsibility for verifying the data.

But this isn't always the case. One might want to generate on-disk
packfiles for a specialized object transfer. Just using "--stdout" and
writing to a file is not optimal, as it will not generate the matching
pack index.

So it would be useful to have some way of overriding this heuristic:
to tell pack-objects that even though it should generate on-disk
files, it is still OK to use the reachability bitmaps to do the
traversal.

So we can teach pack-objects to use bitmap index for initial object
counting phase when generating resultant pack file too:

- if we care it is not activated under git-repack:

  See above about repack robustness and not forward-carrying corruption.

- if we know bitmap index generation is not enabled for resultant pack:

  Current code has singleton bitmap_git so cannot work simultaneously
  with two bitmap indices.

  We also want to avoid (at least with current implementation)
  generating bitmaps off of bitmaps. The reason here is: when generating
  a pack, not-yet-packed objects will be emitted into pack in
  suboptimal order and added to tail of the bitmap as "extended entries".
  When the resultant pack + some new objects in associated repository
  are in turn used to generate another pack with bitmap, the situation
  repeats: new objects are again not emitted optimally and just added to
  bitmap tail - not in recency order.

  So the pack badness can grow over time when at each step we have
  bitmapped pack + some other objects. That's why we want to avoid
  generating bitmaps off of bitmaps, not to let pack badness grow.

- if we keep pack reuse enabled still only for "send-to-stdout" case:

  Because on pack reuse raw entries are directly written out to destination
  pack by write_reused_pack() bypassing needed for pack index generation
  bookkeeping done by regular codepath in write_one() and friends.

This way for pack-objects -> file we get nice speedup:

erp5.git[1] (~230MB) extracted from ~ 5GB lab.nexedi.com backup
repository managed by git-backup[2] via

time echo 0186ac99 | git pack-objects --revs erp5pack

before:  37.2s
after:   26.2s

And for `git repack -adb` packed git.git

time echo 5c589a73 | git pack-objects --revs gitpack

before:   7.1s
after:3.6s

i.e. it can be 30% - 50% speedup for pack extraction.

git-backup extracts many packs on repositories restoration. That was my
initial motivation for the patch.

[1] https://lab.nexedi.com/nexedi/erp5
[2] https://lab.nexedi.com/kirr/git-backup

NOTE

Jeff also suggests that pack.useBitmaps was probably a mistake to
introduce originally. This way we are not adding another config point,
but instead just always default to-file pack-objects not to use bitmap
index: Tools which need to generate on-disk packs with using bitmap, can
pass --use-bitmap-index explicitly. And git-repack does never pass
--use-bitmap-index, so this way we can be sure regular on-disk repacking
remains robust.

NOTE2

`git pack-objects --stdout >file.pack` + `git index-pack file.pack` is much 
slower
than `git pack-objects file.pack`. Extracting erp5.git pack from
lab.nexedi.com backup repository:

$ time echo 0186ac99 | git pack-objects --stdout --revs 
>erp5pack-stdout.pack

real0m22.309s
user0m21.148s
sys 0m0.932s

$ time git index-pack erp5pack-stdout.pack

real0m50.873s   <-- more than 2 times slower than time to generate pack 
itself!
user0m49.300s
sys 0m1.360s

So the time for

`pack-object --stdout >file.pack` + `index-pack file.pack`  is  72s,

while

`pack-objects file.pack` which does both pack and index is  27s.

And even