Re: [PATCH v2 4/6] pack-bitmap: prepare to read lookup table extension

On 6/26/2022 9:10 AM, Abhradeep Chakraborty via GitGitGadget wrote:

I didn't check the previous patches, but your sign-off should be the last line of the message. (You are singing off on all previous content, and any later content is not covered by your sign-off.)

nit: This alignment should use four spaces at the end so the second phrase matches the start of the previous phrase. Like this:

		if (flags & BITMAP_OPT_LOOKUP_TABLE &&
		    git_env_bool("GIT_TEST_READ_COMMIT_TABLE", 1)) {

Perhaps it looked right in your editor because it renders tabs as 4 spaces instead of 8 spaces.

The 4- vs 8-space tab view would also explain the alignment here:

			size_t triplet_sz = st_add3(sizeof(uint32_t),  /* commit position */
						    sizeof(uint64_t),  /* offset */
						    sizeof(uint32_t)); /* xor offset */

(I also modified the comment alignment.)

Of course, since these values are constants and have no risk of overflowing, perhaps we can drop st_add3() here:

			size_t triplet_sz = sizeof(uint32_t) + /* commit position */
					    sizeof(uint64_t) +  /* offset */
					    sizeof(uint32_t); /* xor offset */

Here, we _do_ want to keep the st_mult(). Is the st_add() still necessary? It seems this is a leftover from the previous version that had the 4-byte flag data.

We set table_size to zero above. We could drop that initialization and instead have this after the "size_t triplet_sz" definition:

			size_t table_size = st_mult(ntohl(header->entry_count),
						    triplet_sz));

Please add "_(...)" around the error message so it can be translated.

If we are modifying this multi-line comment, then we should reformat it to match convention:

	/*
	 * The first sentence starts after the comment start
	 * so it has symmetry with the comment end which is on
	 * its own line.
	 */

Errors start with lowercase letters. Please add translation markers "_(...)"

This st_add() is not necessary since the constants will not overflow.

Strange wrapping. Perhaps

static uint32_t bsearch_pos(struct bitmap_index *bitmap_git,
			    struct object_id *oid,
			    uint32_t *result)

Here, we are doing a binary search on the entire list of packed objects, which could use quite a few more hops than a binary search on the bitmapped commits.

...

But I see, you are searching the pack-index for the position in the index, and _then_ searching the bitmap lookup table based on that position value.

I expected something different: binary search on the triplets where the comparison is made by looking up the OID from the [multi-]pack-index and comparing that OID to the commit OID we are looking for.

I'm not convinced that the binary search I had in mind is meaningfully faster than what you've implemented here, so I'm happy to leave it as you have it. We can investigate if that full search on the pack-index matters at all (it probably doesn't).

While there is potential that this is wasteful, it's probably not that huge, so we can start with the "maximum XOR depth" and then reconsider a smaller allocation in the future.

We should consider ensuring that also "size < bitmap_git->entry_count". Better yet, create an xor_positions_alloc variable that is initialized to the entry_count value.

"size" should probably be xor_positions_nr.

(at this point, "if (xor_positions_nr >= xor_positions_alloc)", then error out since the file must be malformed with an XOR loop.)

nit: ") {"

nit: ") {"

Since we are storing the bitmap here as we "pop" the stack, should we be looking for a stored bitmap while pushing to the stack in the previous loop? That would save time when using multiple bitmaps with common XOR bases.

(Of course, we want to be careful that we do not create a recursive loop, but instead _only_ look at the in-memory bitmaps that already exist.)

I'm happy with the structure of this iterative algorithm!

I'll pause my review here for now.

Thanks, -Stolee