{"thread":{"id":"63473","subject":"Question About Sorting the Index","startedAt":"2025-05-16T23:43:51Z","lastAt":"2025-05-28T02:34:05Z","messageCount":9,"participants":["Jon Forrest","K Jayatheerth","Junio C Hamano","Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"518315","messageId":"1008ijb$6j0$1@ciao.gmane.io","threadId":"63473","inReplyTo":null,"subject":"Question About Sorting the Index","fromName":"Jon Forrest","fromEmail":"nobozo@gmail.com","sentAt":"2025-05-16T23:43:37Z","receivedAt":"2025-05-16T23:43:51Z","isPatch":false,"sender":{"key":"nobozo@gmail.com","avatar":"https://gravatar.com/avatar/37c6a7b57f29b3f35c6a9016537907c52f15bbf98575617dc046bcec6bf06372?d=mp&s=160"},"body":"I've learned that entries in the index file \"are\nsorted in ascending order on the name field\".\n\nAm I right in thinking that this means that\nevery time a file is added to the index by\nrunning \"git add\" the whole index file must\nbe resorted? If so, this seems like a lot of\nwork, especially since not all the entries\nare the same size.\n\nHas any thought been made about improving this,\nsuch as perhaps having an \"index index\"? This\nwould be a separate file that contains the name\nfield of each entry, the location of where the entry\nstarts in the index, and the length of the entry.\nI'll call this a partial index entry.\nThe \"index index\" would also be sorted by the name field.\n\nWith this approach, running \"git add\" would simply\nappend a full index entry to the index, and\nappend the partial entry to the \"index index\", which\nwould then be sorted. The full index would not be\nsorted. I'm guessing this is the common path.\n\nTo delete a file from the index, I'd propose adding an\n\"deleted\" bit to the full cache entry. When \"git rm --cached\"\nis run, 2 things would happen:\n\n1) The \"deleted\" bit would be turned on in the full index\nentry for the file. The index itself will not be sorted.\nEvery so often, perhaps when \"git fsck\" is run, these\nentries could be deleted. The full index won't have\nto be resorted when this happens because it won't be\nassumed to be in sorted order any longer.\n\n2) The \"index index\" would be modified by removing the\npartial entry for the file. This could be done by\nwriting the partial entries up to the entry being\ndeleted, and then the entries following. No sort would\nbe necessary because the \"index index\" is already sorted.\n\nOne drawback of this approach would be that since the \"index index\"\nentries also won't be the same length, sorting it will still require\nextra work. However, this wouldn't be any harder then sorting the full\nindex, and a lot less data wouldn't have to be moved around.\n\nAll this is so simple that I suspect that it's been considered before.\nAm I missing something?\n\nCordially,\nJon Forrest\n\nP.S. I'm trying to read the Git source code to get a better handle\non what actually goes on in the index but this is taking some time.\n\n\n\n\n\n\n\n"},{"id":"518323","messageId":"20250517034625.9100-1-jayatheerthkulkarni2005@gmail.com","threadId":"63473","inReplyTo":"1008ijb$6j0$1@ciao.gmane.io","subject":"Re Question About Sorting the Index","fromName":"K Jayatheerth","fromEmail":"jayatheerthkulkarni2005@gmail.com","sentAt":"2025-05-17T03:46:22Z","receivedAt":"2025-05-17T03:46:31Z","isPatch":false,"sender":{"key":"jayatheerthkulkarni2005@gmail.com","avatar":"https://avatars.githubusercontent.com/u/148841023?v=4"},"body":"> I've learned that entries in the index file \"are\n> sorted in ascending order on the name field\".\n\nCorrect the index maintains `struct cache_entry` entries in sorted\norder by the file name. This is essential for fast lookup, diffing, and\npathspec-based operations.\n\n> Am I right in thinking that this means that\n> every time a file is added to the index by\n> running \"git add\" the whole index file must\n> be resorted?\n\nNot exactly. Git keeps the index in memory as a sorted array, so adding\na new entry doesn't require a full resort just a binary search to find\nthe right insertion point. Only when the index is written to disk does\nit serialize the in-memory array, which is already sorted.\n\n> If so, this seems like a lot of\n> work, especially since not all the entries\n> are the same size.\n\nThat's true in principle, but in practice, the memory layout of\n`cache_entry` objects and memory mapping makes it quite efficient,\nespecially since typical index sizes are modest.\n\n> Has any thought been made about improving this,\n> such as perhaps having an \"index index\"? This\n> would be a separate file that contains the name\n> field of each entry, the location of where the entry\n> starts in the index, and the length of the entry.\n> I'll call this a partial index entry.\n\nInteresting idea effectively you're describing a secondary structure\nlike a sparse index or log-structured merge pattern. It has its appeal,\nparticularly for large repositories with high-churn working trees.\n\n> With this approach, running \"git add\" would simply\n> append a full index entry to the index, and\n> append the partial entry to the \"index index\", which\n> would then be sorted. The full index would not be\n> sorted. I'm guessing this is the common path.\n\nThis would reduce write amplification for `git add`, but it comes at a\ncost: many Git operations rely on the index being sorted. Reads would\nhave to scan or use your \"index index\", which introduces more I/O and\ncomplexity.\n\n> To delete a file from the index, I'd propose adding an\n> \"deleted\" bit to the full cache entry. When \"git rm --cached\"\n> is run, 2 things would happen:\n>\n> 1) The \"deleted\" bit would be turned on in the full index\n> entry for the file.\n\nThis assumes laziness in cleanup, which is reasonable for append-only\nsystems. But Git today avoids keeping dead entries around for clarity\nand correctness (especially under concurrent access).\n\n> 2) The \"index index\" would be modified by removing the\n> partial entry for the file.\n\nThis makes sense for maintaining the primary lookup structure.\n\n> One drawback of this approach would be that since the \"index index\"\n> entries also won't be the same length, sorting it will still require\n> extra work. However, this wouldn't be any harder then sorting the full\n> index, and a lot less data wouldn't have to be moved around.\n\nAgreed but it's worth noting that sorting a relatively small\nin-memory structure (as Git does now) is often cheaper than\nmaintaining two files in sync (your full index and index index).\n\n> All this is so simple that I suspect that it's been considered before.\n> Am I missing something?\n\nYou’re not missing much in fact, Git has features like the \"split index\",\n\"untracked cache\", and \"index v4\" that address similar performance issues\nthrough other means. Your idea would likely help in edge cases (very large\nrepos, massive parallelism), but the added complexity and I/O overhead of\nmaintaining multiple files likely outweighs the benefits for the common case.\n\n> P.S. I'm trying to read the Git source code to get a better handle\n> on what actually goes on in the index but this is taking some time.\n\nYou’re in good company. The index code lives mostly in `read-cache.c`.\nDefinitely a dense but rewarding part of the Git source tree to explore.\n\nMaybe you can start from functions like read_index_from() do_write_index() \ndiscard_index(). I think that would be an amazing start.\n"},{"id":"518334","messageId":"49226f81-08df-4d35-861d-eca76fffa449@gmail.com","threadId":"63473","inReplyTo":"20250517034625.9100-1-jayatheerthkulkarni2005@gmail.com","subject":"Re: Re Question About Sorting the Index","fromName":"Jon Forrest","fromEmail":"nobozo@gmail.com","sentAt":"2025-05-17T17:20:29Z","receivedAt":"2025-05-17T17:20:31Z","isPatch":false,"sender":{"key":"nobozo@gmail.com","avatar":"https://gravatar.com/avatar/37c6a7b57f29b3f35c6a9016537907c52f15bbf98575617dc046bcec6bf06372?d=mp&s=160"},"body":"First of all, thanks for the very thoughtful response.\n\nOn 5/16/25 8:46 PM, K Jayatheerth wrote:\n\n> Correct the index maintains `struct cache_entry` entries in sorted\n> order by the file name. This is essential for fast lookup, diffing, and\n> pathspec-based operations.\n\nSomehow I hadn't realized that the index was also stored in\nmemory. However, my concerns about index lookups where each\nentry in the index, in memory or on disk, isn't the same size\nstill apply. How can you do a binary search if you don't know\nwhere the middle of the index is? Maybe I'd understand if I\nhad studied the source code in more detail.\n\n> Not exactly. Git keeps the index in memory as a sorted array, so adding\n> a new entry doesn't require a full resort just a binary search to find\n> the right insertion point. Only when the index is written to disk does\n> it serialize the in-memory array, which is already sorted.\n\nI see. However, my comment above still applies.\n\n>> If so, this seems like a lot of\n>> work, especially since not all the entries\n>> are the same size.\n> \n> That's true in principle, but in practice, the memory layout of\n> `cache_entry` objects and memory mapping makes it quite efficient,\n> especially since typical index sizes are modest.\n\nI guess you're right since the Git universe isn't clamoring\nabout poor performance when accessing the index.\n\n> you're describing a secondary structure\n> like a sparse index or log-structured merge pattern. It has its appeal,\n> particularly for large repositories with high-churn working trees.\n\nRight. I would think it would also add some degree of safety since\nthe index file would only be rewritten when garbage collection is\ndone. The \"index index\" would be much more volatile but since it\ncould be easily and quickly recreated any time, there would be no added\ndanger.\n\n> many Git operations rely on the index being sorted. Reads would\n> have to scan or use your \"index index\", which introduces more I/O and\n> complexity.\n\nI'm not convinced it would result in more I/O. The \"index index\" file\nwould be written more often, true, but each entry in it is much smaller\nthan the in the regular index.\n\nMaybe a better approach would only keep the \"index index\" in memory.\nThis would result in less memory being used, with access to entries\nin the regular index being fast since the \"index index\" entries\ncontain enough data to do random access to the desired entry\nin the on-disk index.\n\nOn the third hand, all this might be unnecessary since the way\nGit currently works is good enough for most (maybe all) people\nmost (maybe all) of the time.\n\n> This assumes laziness in cleanup, which is reasonable for append-only\n> systems. But Git today avoids keeping dead entries around for clarity\n> and correctness (especially under concurrent access).\n\nIf Postgres can do it, so could Git.\n\n> Agreed but it's worth noting that sorting a relatively small\n> in-memory structure (as Git does now) is often cheaper than\n> maintaining two files in sync (your full index and index index).\n\nWith my in memory \"index index\", this would become easier.\n\n> You’re not missing much in fact, Git has features like the \"split index\",\n> \"untracked cache\", and \"index v4\" that address similar performance issues\n> through other means. Your idea would likely help in edge cases (very large\n> repos, massive parallelism), but the added complexity and I/O overhead of\n> maintaining multiple files likely outweighs the benefits for the common case.\n\nThat is indeed the question. I admittedly have no data either about how\nlarge a repo would have to be for a change like this to have any effect,\nor how many such repos exist. I notice that the currrent Git repo has\n4638 entries, which I suppose really isn't all that large.\n\nThanks again,\nJon\n\n\n\n"},{"id":"518337","messageId":"xmqqfrh3qe2w.fsf@gitster.g","threadId":"63473","inReplyTo":"1008ijb$6j0$1@ciao.gmane.io","subject":"Re: Question About Sorting the Index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-05-17T18:36:39Z","receivedAt":"2025-05-17T18:36:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jon Forrest <nobozo@gmail.com> writes:\n\n> P.S. I'm trying to read the Git source code to get a better handle\n> on what actually goes on in the index but this is taking some time.\n\nDepending on the style of the learner, I often recommend reading the\nvery initial revision of Git, i.e.  e83c5163 (Initial revision of\n\"git\", the information manager from hell, 2005-04-07), to quickly\nget a feel of what various pieces there are and how they fit\ntogether, by doing\n\n    $ git checkout -b initial e83c5163316f89bfb\n\nThis would give you a mere 1244 lines spread across 11 files, which\nis something that can be read from cover to cover in a single\nsitting and see how various data structures relate to each other and\ninteract.  In the past 20 years, we of course have added features\nand auxiliary data structures, and the various details of the\nimplementation have changed, but the really core part of the concept\nhaven't drifted too far from the original.\n\nFor example, the fact that the index is first read into core, each\nentry is represented as a cache_entry in-core structure, and the\ncode accesses them via an array active_cache[], and that array is\nsorted per pathnames, haven't changed.  In the 3-4 months that\nfollowed that initial revision, we added higher-stage entries that\nare used to represent a merge in progress (together with sorting\nrules for them), and later we added prefix-compression for the\npathnames, but the basic structure of the index subsystem hasn't\nchanged all that much over the years.\n\n\n"},{"id":"518340","messageId":"e2a24cbb-1438-46b9-b546-82c9f6dc7ebf@gmail.com","threadId":"63473","inReplyTo":"xmqqfrh3qe2w.fsf@gitster.g","subject":"Re: Question About Sorting the Index","fromName":"Jon Forrest","fromEmail":"nobozo@gmail.com","sentAt":"2025-05-17T18:48:17Z","receivedAt":"2025-05-17T18:48:18Z","isPatch":false,"sender":{"key":"nobozo@gmail.com","avatar":"https://gravatar.com/avatar/37c6a7b57f29b3f35c6a9016537907c52f15bbf98575617dc046bcec6bf06372?d=mp&s=160"},"body":"\n\nOn 5/17/25 11:36 AM, Junio C Hamano wrote:\n> Jon Forrest <nobozo@gmail.com> writes:\n> \n>> P.S. I'm trying to read the Git source code to get a better handle\n>> on what actually goes on in the index but this is taking some time.\n> \n> Depending on the style of the learner, I often recommend reading the\n> very initial revision of Git, i.e.  e83c5163 (Initial revision of\n> \"git\", the information manager from hell, 2005-04-07), to quickly\n> get a feel of what various pieces there are and how they fit\n> together, by doing\n> \n>      $ git checkout -b initial e83c5163316f89bfb\n\nThanks for the suggestion. I'll do that.\n\nMeanwhile, do you see any merit to my idea?\n\nCordially,\nJon Forrest\n\n"},{"id":"518344","messageId":"CABPp-BGRxierdcqWz2ZNdvLLrSSSR937CgOvC19vQkeUeC1pFg@mail.gmail.com","threadId":"63473","inReplyTo":"e2a24cbb-1438-46b9-b546-82c9f6dc7ebf@gmail.com","subject":"Re: Question About Sorting the Index","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-05-18T05:13:49Z","receivedAt":"2025-05-18T05:14:00Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Sat, May 17, 2025 at 11:48 AM Jon Forrest <nobozo@gmail.com> wrote:\n>\n> On 5/17/25 11:36 AM, Junio C Hamano wrote:\n> > Jon Forrest <nobozo@gmail.com> writes:\n> >\n> >> P.S. I'm trying to read the Git source code to get a better handle\n> >> on what actually goes on in the index but this is taking some time.\n> >\n> > Depending on the style of the learner, I often recommend reading the\n> > very initial revision of Git, i.e.  e83c5163 (Initial revision of\n> > \"git\", the information manager from hell, 2005-04-07), to quickly\n> > get a feel of what various pieces there are and how they fit\n> > together, by doing\n> >\n> >      $ git checkout -b initial e83c5163316f89bfb\n>\n> Thanks for the suggestion. I'll do that.\n>\n> Meanwhile, do you see any merit to my idea?\n\nIsn't the idea essentially the split index we already have?  (See the\n\"SPLIT INDEX\" section of the git-update-index manual.)\n"},{"id":"518363","messageId":"6c05cf29-3fd5-44b9-910b-0baf435027b9@gmail.com","threadId":"63473","inReplyTo":"CABPp-BGRxierdcqWz2ZNdvLLrSSSR937CgOvC19vQkeUeC1pFg@mail.gmail.com","subject":"Re: Question About Sorting the Index","fromName":"Jon Forrest","fromEmail":"nobozo@gmail.com","sentAt":"2025-05-18T15:13:01Z","receivedAt":"2025-05-18T15:13:03Z","isPatch":false,"sender":{"key":"nobozo@gmail.com","avatar":"https://gravatar.com/avatar/37c6a7b57f29b3f35c6a9016537907c52f15bbf98575617dc046bcec6bf06372?d=mp&s=160"},"body":"\n\nOn 5/17/25 10:13 PM, Elijah Newren wrote:\n\n> Isn't the idea essentially the split index we already have?  (See the\n> \"SPLIT INDEX\" section of the git-update-index manual.)\n\nI admittedly hadn't read that before. Yes, it's similar.\nBut, I think I better become more familiar with this man\npage before I take up any more of this list's time.\n\nOne observation - wouldn't things be nice if the index entries\nwere (somehow) the same length.\n\nJon\n\n"},{"id":"519004","messageId":"9befdb3e-ff6e-4416-8735-1eea99dbbf01@gmail.com","threadId":"63473","inReplyTo":"xmqqfrh3qe2w.fsf@gitster.g","subject":"Re: Question About Sorting the Index","fromName":"Jon Forrest","fromEmail":"nobozo@gmail.com","sentAt":"2025-05-27T16:38:59Z","receivedAt":"2025-05-27T16:39:01Z","isPatch":false,"sender":{"key":"nobozo@gmail.com","avatar":"https://gravatar.com/avatar/37c6a7b57f29b3f35c6a9016537907c52f15bbf98575617dc046bcec6bf06372?d=mp&s=160"},"body":"\n\nOn 5/17/25 11:36 AM, Junio C Hamano wrote:\n\n> For example, the fact that the index is first read into core, each\n> entry is represented as a cache_entry in-core structure, and the\n> code accesses them via an array active_cache[], and that array is\n> sorted per pathnames, haven't changed.  \n\nI had a thought. What if the in-memory cache were stored in a hash,\nwhere the pathname is the key? That way nothing would have to be\nsorted in order to lookup a particular file.\n\nThe on-disk index could be in any order.\n\nI don't know how the overhead of creating the hash when a\ngit program starts compares to that of creating the\ncache_entry struct and then later doing the sorting.\nThis seems like the key question.\n\nJon\n\n\n"},{"id":"519039","messageId":"xmqqbjrdtqed.fsf@gitster.g","threadId":"63473","inReplyTo":"9befdb3e-ff6e-4416-8735-1eea99dbbf01@gmail.com","subject":"Re: Question About Sorting the Index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-05-28T02:34:02Z","receivedAt":"2025-05-28T02:34:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jon Forrest <nobozo@gmail.com> writes:\n\n> On 5/17/25 11:36 AM, Junio C Hamano wrote:\n>\n>> For example, the fact that the index is first read into core, each\n>> entry is represented as a cache_entry in-core structure, and the\n>> code accesses them via an array active_cache[], and that array is\n>> sorted per pathnames, haven't changed.  \n>\n> I had a thought. What if the in-memory cache were stored in a hash,\n> where the pathname is the key? That way nothing would have to be\n> sorted in order to lookup a particular file.\n\nThe index must be in sorted order in order to allow a set of tree\nobjects written out of it.  Hash may be good for looking up, but it\nis not the best data structure for stable and efficient enumeration.\n"}]}