Re: Re Question About Sorting the Index

From: Jon Forrest <nobozo@gmail.com>
Date: May 17, 2025, 17:20 UTC
Message-ID: <49226f81-08df-4d35-861d-eca76fffa449@gmail.com>
In-Reply-To: <20250517034625.9100-1-jayatheerthkulkarni2005@gmail.com>

First of all, thanks for the very thoughtful response.

On 5/16/25 8:46 PM, K Jayatheerth wrote:

> Correct the index maintains `struct cache_entry` entries in sorted
> order by the file name. This is essential for fast lookup, diffing, and
> pathspec-based operations.

Somehow I hadn't realized that the index was also stored in memory. However, my concerns about index lookups where each entry in the index, in memory or on disk, isn't the same size still apply. How can you do a binary search if you don't know where the middle of the index is? Maybe I'd understand if I had studied the source code in more detail.

> Not exactly. Git keeps the index in memory as a sorted array, so adding
> a new entry doesn't require a full resort just a binary search to find
> the right insertion point. Only when the index is written to disk does
> it serialize the in-memory array, which is already sorted.

I see. However, my comment above still applies.

Show 7 quoted lines

>> If so, this seems like a lot of
>> work, especially since not all the entries
>> are the same size.
> 
> That's true in principle, but in practice, the memory layout of
> `cache_entry` objects and memory mapping makes it quite efficient,
> especially since typical index sizes are modest.

I guess you're right since the Git universe isn't clamoring about poor performance when accessing the index.

> you're describing a secondary structure
> like a sparse index or log-structured merge pattern. It has its appeal,
> particularly for large repositories with high-churn working trees.

Right. I would think it would also add some degree of safety since the index file would only be rewritten when garbage collection is done. The "index index" would be much more volatile but since it could be easily and quickly recreated any time, there would be no added danger.

> many Git operations rely on the index being sorted. Reads would
> have to scan or use your "index index", which introduces more I/O and
> complexity.

I'm not convinced it would result in more I/O. The "index index" file would be written more often, true, but each entry in it is much smaller than the in the regular index.

Maybe a better approach would only keep the "index index" in memory. This would result in less memory being used, with access to entries in the regular index being fast since the "index index" entries contain enough data to do random access to the desired entry in the on-disk index.

On the third hand, all this might be unnecessary since the way Git currently works is good enough for most (maybe all) people most (maybe all) of the time.

> This assumes laziness in cleanup, which is reasonable for append-only
> systems. But Git today avoids keeping dead entries around for clarity
> and correctness (especially under concurrent access).

If Postgres can do it, so could Git.

> Agreed but it's worth noting that sorting a relatively small
> in-memory structure (as Git does now) is often cheaper than
> maintaining two files in sync (your full index and index index).

With my in memory "index index", this would become easier.

Show 5 quoted lines

> You’re not missing much in fact, Git has features like the "split index",
> "untracked cache", and "index v4" that address similar performance issues
> through other means. Your idea would likely help in edge cases (very large
> repos, massive parallelism), but the added complexity and I/O overhead of
> maintaining multiple files likely outweighs the benefits for the common case.

That is indeed the question. I admittedly have no data either about how large a repo would have to be for a change like this to have any effect, or how many such repos exist. I notice that the currrent Git repo has 4638 entries, which I suppose really isn't all that large.

Thanks again, Jon