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

[Derrick Stolee <derrickstolee@github.com>]

On 6/26/2022 9:10 AM, Abhradeep Chakraborty via GitGitGadget wrote:
> From: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>
> 
> The bitmap lookup table extension was documentated by an earlier

s/documentated/documented/

> change, but Git does not yet knowhow to write that extension.

s/knowhow/know how/

> +static int table_cmp(const void *_va, const void *_vb, void *commit_positions)
> +{
> +	int8_t result = 0;
> +	uint32_t *positions = (uint32_t *) commit_positions;

nit: drop the space between the cast and commit_positions.

> +	uint32_t a = positions[*(uint32_t *)_va];
> +	uint32_t b = positions[*(uint32_t *)_vb];
> +
> +	if (a > b)
> +		result = 1;
> +	else if (a < b)
> +		result = -1;
> +	else
> +		result = 0;
> +
> +	return result;
> +}

Ok, here you are sorting by commit OID (indirectly by the order in the
[multi-]pack-index). I suppose that I misunderstood in the previous
patch, so that could use some more specific language, maybe.

> +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);

At the end of this sort, table[j] = i means that the ith bitmap corresponds
to the jth bitmapped commit in lex order of OIDs.

> +	for (i = 0; i < writer.selected_nr; i++)
> +		table_inv[table[i]] = i;

And table_inv helps us discover that relationship (ith bitmap to jth commit
by j = table_inv[i]).

> +	for (i = 0; i < writer.selected_nr; i++) {
> +		struct bitmapped_commit *selected = &writer.selected[table[i]];
> +		uint32_t xor_offset = selected->xor_offset;

Here, xor_offset is "number of bitmaps in relationship to the current bitmap"

> +		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);

Which means that if "k = table[i] - xor_offset" that the xor base is the kth
bitmap. table_inv[k] gets us the position in this table of that bitmap's
commit.

(It's also strange to me that the offset is being _subtracted_, but I guess
the bitmap format requires the xor base to appear first so the offset does
not need to be a negative number ever.)

This last line is a bit complex.

	uint32_t xor_offset = selected->xor_offset;
	uint32_t xor_row = 0xffffffff;

	if (xor_offset) {
		uint32_t xor_order = table[i] - xor_offset;
		xor_row = table_inf[xor_order];
	}

...then we can "hashwrite_be32(f, xor_row);" when necessary. I'm not sure
that we need the "uint32_t xor_order" inside the "if (xor_offset)" block,
but splitting it helps add clarity to the multi-step computation.

>  enum pack_bitmap_opts {
> -	BITMAP_OPT_FULL_DAG = 1,
> -	BITMAP_OPT_HASH_CACHE = 4,
> +	BITMAP_OPT_FULL_DAG = 0x1,
> +	BITMAP_OPT_HASH_CACHE = 0x4,
> +	BITMAP_OPT_LOOKUP_TABLE = 0x10,
>  };

Excellent.

Thanks,
-Stolee