Subject: Re: Git in Outreachy?

From: Taylor Blau <[email-masked]>
Date: Wed, 9 Sep 2020 22:19:16 -0400

On Wed, Sep 09, 2020 at 06:39:15PM -0700, Jonathan Nieder wrote:
> Taylor Blau wrote:
> In other words: this isn't about changing how tests are executed ---
> it's about going from patches on list to git commits that can be
> tested.

Fair enough; it sounds like a Snowpatch-like tool might be useful for
that case.

> [...]
> >> - formats: on-disk reverse idx
> >
> > As a heads up, I think that I am going to start working on (an
> > alternative to) this myself,
>
> Neat!  I look forward to seeing what you build.  (Is this related to
> the bitmaps-using-midx-ordering work?)

You guessed it ;-). It's sort of a tricky issue: the pack-objects code
needs to know things like the position of an object in index order so
that it can look at the offset of the next object and determine its
size.

But, in the multi-pack case, things aren't so simple. It would be nice
if we could look at a bit position and say "you are at bit position N
and there are M different packs before you, so I know what position
you are within your pack", but this can't be done in general when you
have duplicate objects among packs in your MIDX.

The MIDX is only going to choose one of them, and so you don't know how
many "holes" are present before you. In my development version, I have a
bitmap extension I'm calling the "rev-cache" which acts like a mapping
between bit position and MIDX name order (which can then be used to look
up auxiliary info like which pack an object came from, its position in
the pack's index order, and so on).

But, having an on-disk mapping between objects and their position in
different orderings will be useful not only for this, but for:

  - avoiding building a reverse index in memory from scratch (which can
    occupy quite a bit of the heap in some repositories that we see),
    and

  - dropping GitHub's custom "bit-cache" extension, which maps objects
    from name order to bit position.

Anyway, obviously not related to Outreachy, and obviously many more
details to come once I have patches that are more mature, but I couldn't
help myself in the meantime.

> Thanks,
> Jonathan
>
> >> [*] https://github.com/ruscur/snowpatch

Thanks,
Taylor