On Sun, Jun 26, 2022 at 01:10:13PM +0000, Abhradeep Chakraborty via GitGitGadget wrote:
> From: Abhradeep Chakraborty <chakrabortyabhradeep79@xxxxxxxxx>
>
> 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@xxxxxxxxxxxx>
> Mentored-by: Taylor Blau <me@xxxxxxxxxxxx>
> Co-mentored-by: Kaartic Sivaraam <kaartic.sivaraam@xxxxxxxxx>
> Signed-off-by: Abhradeep Chakraborty <chakrabortyabhradeep79@xxxxxxxxx>
> ---
> 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
