Re: [PATCH 12/14] rust: add a new binary loose object map format

> On 2025-10-28 at 09:18:32, Patrick Steinhardt wrote:
> > Doesn't this indicate that calling this "loose object map" is kind of a
> > misnomer? If we want to be able to store arbitrary objects regardless of
> > the way those are stored (or not stored) in the ODB then I think it's
> > overall quite confusing to have "loose" in the name.
> > 
> > This isn't something we can fix for the old loose object map. But
> > shouldn't we fix this now for the new format you're about to introduce?
> 
> Sure.  I will admit I'm terrible at naming things.  What do you think it
> should be called.

> > > +	* A table of 4-byte metadata values.
> > > +	* Zero or more chunks.  A chunk starts with a four-byte chunk identifier and
> > > +		a four-byte parameter (which, if unneeded, is all zeros) and an eight-byte
> > > +		size (not including the identifier, parameter, or size), plus the chunk
> > > +		data.
> > > +- Zero or more NUL bytes.
> > > +- Tables for subsequent object formats:
> > > +	* A sorted table of shortened object names.  These are prefixes of the names
> > > +		of all objects in this file, packed together without offset values to
> > > +		reduce the cache footprint of the binary search for a specific object name.
> > > +  * A table of full object names in the order specified by the first object format.
> > 
> > Interesting, why are these sorted by the first object format again?
> > Doesn't that mean that I have to do a linear search now to locate the
> > entry for the second object format?
> 
> No, it doesn't.  The full object names are always in the order of the
> first format.  The shortened names for second and subsequent formats
> point into an offset table that finds the offset in the first format.
> 
> Therefore, to look up an OID in the second format knowing its OID in the
> first format, you use the first format's prefixes to find its offset,
> verify its OID in the full object names, and then look up that offset in
> the list of full object names in the second format.
> 
> To go the other way, you find the prefix in the second format, find its
> corresponding offset in the mapping table, verify the full object ID in
> the second format, and then look up that offset in the full object names
> in the first format.

> > Overall you only have to store the full object ID for each hash exactly
> > once, and the mappings also only have to be stored once. But you can
> > look up an ID by each of its formats via its indices.
> 
> This is very similar to what we have now, except that it has mapping
> offsets for each algorithm instead of the second and subsequent
> algorithms and it re-orders the location of the full object IDs.
> 
> I also intentionally wanted to produce completely deterministic output,
> since in `git verify-pack` we verify that the output is byte-for-byte
> identical and I wanted to have the ability to do that here as well.  (It
> isn't implemented yet, but that's a goal.)  In order to do that, we need
> to write every part of the data in a fixed order, so we'd have to define
> the main table as being sorted by the first algorithm.

> > With some slight adjustments one could also adapt this format to become
> > streamable:
> 
> I don't think these formats are as streamable as you might like.  In
> order to create the tables, we need to sort the data for each algorithm
> to find the short name length, which requires knowing all of the data up
> front in order.
> 
> I, too, thought that might be a nice idea, but when I implemented pack
> index v3, I realized that effectively all of the data has to be computed
> up front.  Once you do that, computing the offsets isn't hard because
> it's just some addition and multiplication.