Re: [PATCH v1 1/4] fastindex: speed up index load through parallelization

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 10, 2017, 04:46 UTC
Message-ID: <xmqqbmkahhar.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20171109141737.47976-2-benpeart@microsoft.com>

Ben Peart <benpeart@microsoft.com> writes:

Show 5 quoted lines

> To make this work for V4 indexes, when writing the index, it periodically
> "resets" the prefix-compression by encoding the current entry as if the
> path name for the previous entry is completely different and saves the
> offset of that entry in the IEOT.  Basically, with V4 indexes, it
> generates offsets into blocks of prefix-compressed entries.

You specifically mentioned about this change in your earlier correspondence on this series, and it reminds me of Shawn's reftable proposal that also is heavily depended on prefix compression with occasional reset to allow scanning from an entry in the middle. I find it a totally sensible design choice.

> To enable reading the IEOT extension before reading all the variable
> length cache entries and other extensions, the IEOT is written last,
> right before the trailing SHA1.

OK, we have already closed the door for further enhancements to place something other than the index extensions after this block by mistakenly made it the rule that the end of the series of extended sections must coincide with the beginning of the trailing checksum, so it does not sound all that bad to insist on this particular one to be the last, I guess. But see below...

> The format of that extension has the signature bytes and size at the
> beginning (like a normal extension) as well as at the end in reverse
> order to enable parsing the extension by seeking back from the end of
> the file.

I think this is a reasonable workaround to allow a single extension that needs to be read before the main index is loaded.

But I'd suggest taking this approach one step further. Instead, what if we introduce a new extension EOIE ("end of index entries") whose sole purpose is to sit at the end of the series of extensions and point at the beginning of the index extension section of the file, to tell you where to seek in order to skip the main index?

That way, you can

 - seek to the end of the index file;

 - go backward skiping the trailing file checksum;

 - now you might be at the end of the EOIE extension.  seek back
   necessary number of bytes and verify EOIE header, pick up the
   recorded file offset of the beginning of the extensions section.

 - The 4-byte sequence you found may happen to match EOIE but that
   is not enough to be sure that you indeed have such an extension.
   So the following must be done carefully, allowing the possibility
   that there wasn't any EOIE extension at the end.
   Seek back to that offset, and repeat these three steps to skip
   over all extensions:

   - read the (possible) 4-byte header
   - read the (possible) extsize (validate that this is a sane value)
   - skip that many bytes

   until you come back to the location you assumed that you found
   your EOIE header, to make sure you did not get fooled by bytes
   that happened to look like one.  Some "extsize" you picked up
   during that process may lead you beyond the end of the index
   file, which would be a sure sign that what you found at the end
   of the index file was *not* the EOIE extension but a part of
   some other extension who happened to have these four bytes at the
   right place.

which would be a lot more robust way to allow any extensions to be read before the main body of the index.

And a lot more importantly, we will leave the door open to allow more than one index extensions that we would prefer to read before reading the main body if we do it this way, because we can easily skip things over without spending cycles once we have a robust way to find where the end of the main index is. After all, the reason you placed IEOT at the end is not because you wanted to have it at the very end. You only wanted to be able to find where it is without having to parse the variable-length records of the main index. And there may be other index extensions that wants to be readable without reading the main part just like IEOT, and we do not want to close the door for them.

Hmm?