On Wed, Oct 29, 2025 at 01:37:49AM +0000, brian m. carlson wrote:

On 2025-10-28 at 09:18:32, Patrick Steinhardt wrote:

quoted

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.

I think the name is quite descriptive despite the misleading "loose"
part. So can't we simply drop that part and call it "object map"?

[snip]

quoted

quoted

+	* 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.

Okay.

[snip]

quoted

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.

Okay.

quoted

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.

I guess you can make it streamable if you don't care about deterministic
output and if you're willing to have a separate ordered lookup table for
the first hash. But in any case you'd have to keep all object IDs in
memory regardless of that so that those can be sorted. I'm not sure that
this really buys us much.

So overall I'm fine with it not being streamable.

I personally like a header with offsets better than a trailer since it
makes parsing easier.  We can peek at the first 64 bytes of the file to
see if it meets our needs or has data we're interested in.

It's not all that bad -- we for example use this for reftables. Both for
reftables and also for your format we'd mmap anyway, and in order to
mmap you need to figure out the overall size of the file first. From
there on it shouldn't be hard to figure out whether the trailer starts
based on the number of hashes and their respective sizes announced in
the header.

But I remember that this led to some head scratching for myself when I
initially dived into the reftable library, so I very much acknowledge
that it at least adds _some_ complexity.

Anyway, thanks for these explanations! One suggestion: it helped me
quite a bit to draw the ASCII diagrams I had in my previous mail. How
about we add such a diagram to help readers a bit with the high-level
structure of the format?

Patrick