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

[Taylor Blau <me@ttaylorr.com>]

Hi Abhradeep,

I just wanted to make absolutely sure that I understood what the
implementation in this patch was doing, since I think generating and
converting between all of these different orderings is by far the most
confusing component of this series.

On Mon, Jul 04, 2022 at 08:46:12AM +0000, Abhradeep Chakraborty via GitGitGadget wrote:
> From: Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>
>
> The bitmap lookup table extension was documented by an earlier
> change, but Git does not yet know how to write that extension.
> +static int table_cmp(const void *_va, const void *_vb, void *_data)
> +{
> +	uint32_t *commit_positions = _data;
> +	uint32_t a = commit_positions[*(uint32_t *)_va];
> +	uint32_t b = commit_positions[*(uint32_t *)_vb];
> +
> +	if (a > b)
> +		return 1;
> +	else if (a < b)
> +		return -1;
> +
> +	return 0;
> +}

Let's skip the above part for now, and just look at the implementation
of writing_lookup_table():

> +static void write_lookup_table(struct hashfile *f,
> +			       struct pack_idx_entry **index,
> +			       uint32_t index_nr,
> +			       off_t *offsets)
> +{
> +	uint32_t i;
> +	uint32_t *table, *table_inv, *commit_positions;
> +
> +	ALLOC_ARRAY(table, writer.selected_nr);
> +	ALLOC_ARRAY(table_inv, writer.selected_nr);
> +	ALLOC_ARRAY(commit_positions, writer.selected_nr);

Makes sense.

> +	/* store the index positions of the commits */
> +	for (i = 0; i < writer.selected_nr; i++) {
> +		int pos = commit_bitmap_writer_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;
> +	}

By the end of this loop, we have an array `commit_positions` which maps
the ith selected commit to its lexical position among all objects in the
bitmap. IOW, `commit_positions[i] = j` means the `i`th selected commit
can be found at index `j` among all objects in the pack/MIDX in their
lexical order.

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

At this point, table[i] = i.

> +	/*
> +	 * At the end of this sort table[j] = i means that the i'th
> +	 * bitmap corresponds to j'th bitmapped commit in lex order of
> +	 * OIDs.
> +	 */
> +	QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);

And then we sort table by treating its values as indexes into
`commit_positions`. Here's where I'm not sure that I follow what's going
on. You say above that `table[j] = i`, where `i` corresponds to the
order of selected commits, and `j` is in lexical order.

If that's the case, then I'd expect that printing `index[table[j]]` for
increasing `j` would output OIDs in increasing lexical order. But that
doesn't quite seem to be the case. From a debugger session that has a
breakpoint after computing and sorting table, along with building
`table_inv`:

    (gdb) p oid_to_hex(&index[table[0]]->oid)
    $17 = 0x555555983ea0 <hexbuffer> "0006763074748d43b539c1c8e8882c08034ab178"
    (gdb) p oid_to_hex(&index[table[1]]->oid)
    $18 = 0x555555983ee1 <hexbuffer+65> "001ce83dd43f03dcfc67f29d38922e4a9682aab0"
    (gdb) p oid_to_hex(&index[table[2]]->oid)
    $19 = 0x555555983f22 <hexbuffer+130> "002db882ece2ab6a240e495a169c6e06422289c8"
    (gdb) p oid_to_hex(&index[table[3]]->oid)
    $20 = 0x555555983f63 <hexbuffer+195> "0007a5feb040e1ff704f3ad636619ddca3e7382b"

that doesn't look like the OIDs are increasing in lexical order.

I'm not quite sure if I'm even looking at the right thing, or if this is
to be expected, or if the comment isn't quite accurate. If you could
help clarify what's going on here, that would be great.

> +	/* table_inv helps us discover that relationship (i'th bitmap
> +	 * to j'th commit by j = table_inv[i])
> +	 */
> +	for (i = 0; i < writer.selected_nr; i++)
> +		table_inv[table[i]] = i;

This part makes sense, as does the rest of the implementation.

Thanks,
Taylor