Re: [PATCH v2 2/6] pack-bitmap-write.c: write lookup table extension
- From
Derrick Stolee <derrickstolee@github.com>
- Date
- Jun 27, 2022, 14:35 UTC
- Message-ID
- <560d1802-8565-04eb-9faf-0f821861d321@github.com>
- In-Reply-To
- <d118f1d45e6202925d4efd5435acdd08545bf132.1656249017.git.gitgitgadget@gmail.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.
Show 12 quoted lines
> + 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.
Show 14 quoted lines
> +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.
Show 7 quoted lines
> 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