Re: [PATCH v2 2/6] pack-bitmap-write.c: write lookup table extension

[Taylor Blau <me@ttaylorr.com>]

On Sun, Jun 26, 2022 at 01:10:13PM +0000, Abhradeep Chakraborty via GitGitGadget wrote:
> From: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>
>
> The bitmap lookup table extension was documentated by an earlier
> change, but Git does not yet knowhow to write that extension.
>
> Teach git to write bitmap lookup table extension. The table contains
> the list of `N` <commit pos, offset, xor offset>` triplets. These
> triplets are sorted according to their commit pos (ascending order).
> The meaning of each data in the i'th triplet is given below:
>
>   - Commit pos is the position of the commit in the pack-index
>     (or midx) to which the i'th bitmap belongs. It is a 4 byte
>     network byte order integer.
>
>   - offset is the position of the i'th bitmap.
>
>   - xor offset denotes the position of the triplet with whose
>     bitmap the current triplet's bitmap need to xor with.
>
> Co-authored-by: Taylor Blau <me@ttaylorr.com>
> Mentored-by: Taylor Blau <me@ttaylorr.com>
> Co-mentored-by: Kaartic Sivaraam <kaartic.sivaraam@gmail.com>
> Signed-off-by: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>
> ---
>  pack-bitmap-write.c | 72 +++++++++++++++++++++++++++++++++++++++++++--
>  pack-bitmap.h       |  5 ++--
>  2 files changed, 73 insertions(+), 4 deletions(-)
>
> diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
> index c43375bd344..899a4a941e1 100644
> --- a/pack-bitmap-write.c
> +++ b/pack-bitmap-write.c
> @@ -650,7 +650,9 @@ static const struct object_id *oid_access(size_t pos, const void *table)
>
>  static void write_selected_commits_v1(struct hashfile *f,
>  				      struct pack_idx_entry **index,
> -				      uint32_t index_nr)
> +				      uint32_t index_nr,
> +				      uint64_t *offsets,

We should probably leave this as a pointer to an off_t, since that is a
more appropriate type for keeping track of an offset within a file (and
indeed it is the return type of hashfile_total()).

But since it's platform-dependent, we should make sure to cast it to a
uint64_t before writing it as part of the lookup table.

> +				      uint32_t *commit_positions)
>  {
>  	int i;
>
> @@ -663,6 +665,11 @@ static void write_selected_commits_v1(struct hashfile *f,
>  		if (commit_pos < 0)
>  			BUG("trying to write commit not in index");
>
> +		if (offsets)
> +			offsets[i] = hashfile_total(f);

This makes sense to store here, since we can't easily recover this
information later on.

> +		if (commit_positions)
> +			commit_positions[i] = commit_pos;

This one I'm not as sure about. It would be nice to not have
write_selected_commits_v1() be responsible for writing this down, too.
And I think it's easy enough to recover later on, since we're just doing
a search over "index" (see above the "oid_pos" call).

I think that oid_pos() call could be hidden behind a function that takes
an object_id pointer, an index (double pointer) of pack_idx_entry
structs, and a length.

Its implementation would be something like:

    static int commit_bitmap_writer_pos(struct object_id *oid,
                                        struct pack_idx_entry **index,
                                        uint32_t index_nr)
    {
        return oid_pos(oid, index, index_nr, oid_access);
    }

and then we could replace any calls like commit_positions[i] with one
that first takes `i` to the appropriate object_id in selected commit
order.

That would be strictly less efficient, but not in a way that I think
matters, and it would definitely be cleaner to not rely on a side-effect
of write_selected_commits_v1().

Something in the middle there would be to have write_lookup_table()
assemble that list of commit_positions itself, something like:

    uint32_t *commit_positions;

    ALLOC_ARRAY(commit_positions, writer.selected_nr);

    for (i = 0; i < writer.selected_nr; i++) {
        int pos = oid_pos(&writer.selected[i].commit->object.oid,
                          index, index_nr);
        if (pos < 0)
            BUG("trying to write commit not in index");
        commit_positions[i] = pos;
    }

    ...

    free(commit_positions);

That at least removes a side-effect from the implementation of
write_selected_commits_v1() and brings the creation of the
commit_positions array closer to where it's being used, while still
maintaining the constant-time lookups. So that may be a good
alternative, but I'm curious of your thoughts.

> +static int table_cmp(const void *_va, const void *_vb, void *commit_positions)

OK, so this is sorting the table in order of the commit positions. I
would rename the commit_positions parameter to something like "void
*_data", and then have commit_positions be the result of the cast, like
"uint32_t *commit_positions = _data";

> +{
> +	int8_t result = 0;

int8_t isn't an often used type in Git's codebase, but we can get rid of
this variable altogether and just return immediately from each case,
e.g.:

    if (a < b)
        return -1;
    else if (a > b)
        return 1;
    return 0;

or similar.

> +	uint32_t *positions = (uint32_t *) commit_positions;

Explicit cast isn't need here since you're going up from void*.

> +static void write_lookup_table(struct hashfile *f,
> +			       uint64_t *offsets,
> +			       uint32_t *commit_positions)
> +{
> +	uint32_t i;
> +	uint32_t *table, *table_inv;
> +
> +	ALLOC_ARRAY(table, writer.selected_nr);
> +	ALLOC_ARRAY(table_inv, writer.selected_nr);
> +
> +	for (i = 0; i < writer.selected_nr; i++)
> +		table[i] = i;
> +
> +	QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);

I think the construction of table and table_inv could definitely benefit
from a comment here indicating what they're used for and what they
contain (e.g., "table maps abc to xyz").

> +	for (i = 0; i < writer.selected_nr; i++)
> +		table_inv[table[i]] = i;
> +
> +	for (i = 0; i < writer.selected_nr; i++) {
> +		struct bitmapped_commit *selected = &writer.selected[table[i]];
> +		uint32_t xor_offset = selected->xor_offset;
> +
> +		hashwrite_be32(f, commit_positions[table[i]]);
> +		hashwrite_be64(f, offsets[table[i]]);
> +		hashwrite_be32(f, xor_offset ?
> +				table_inv[table[i] - xor_offset]: 0xffffffff);

Nit: missing space before ':'.

Thanks,
Taylor