{"thread":{"id":"36436","subject":"Store refreshed stat info in a separate file?","startedAt":"2014-04-18T14:20:31Z","lastAt":"2014-04-25T05:18:08Z","messageCount":3,"participants":["Duy Nguyen","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"239069","messageId":"CACsJy8CzZ7H4pffNccBBpvpn5oT5tud-Tx=Nu1c=q2SB7Zi8eg@mail.gmail.com","threadId":"36436","inReplyTo":null,"subject":"Store refreshed stat info in a separate file?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-18T14:20:31Z","receivedAt":"2014-04-18T14:20:31Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"With git status, writing refreshed index takes 252ms per total 1s,\n361s/1.4s, 86ms/360ms on gentoo-x86, webkit and linux-2.6 respectively\n(*). It's takes a significant amount of time from \"git status\". And\nthis happens whenever you touch a single tracked file, then do \"git\nstatus\". We tried to solve this with index v5, but it's been years(?)\nsince its start as a GSoC project. So I'm thinking of another way\naround..\n\nThe major cost of writing an index is the SHA-1 hashing. The bigger\nthe written part is, the higher cost we pay. So what if we write\nstat-only data to a separate file? Think of it as an index extension,\nonly it stays outside the index. On webkit with 182k files, the stat\ndata size would be about 6MB (its index v4 is 15M for comparison). But\nwith stat-only we could employ some cheap but efficient compressing,\nsd_dev, sd_uid and sd_gid are likely the same for every entry. And we\ncould store the stat data of updated entries only. So I'm hoping to\nget that 6MB down to a few hundred KBs. That makes hashing lightning\nfast.\n\nSo the idea is, when we do refresh, we note what entry has stat\nupdated. Then we write $GIT_DIR/index.stat (and leave $GIT_DIR/index\nalone), which is a valid index except that it has zero entries and a\nonly one (new) extension storing (maybe compressed) stat data of\nupdated entries. The extension also contains the trailing SHA-1 of\n$GIT_DIR/index for verification later. When we read $GIT_DIR/index, we\ncheck for the existence of index.stat. If it does and its attached\nSHA-1 matches, we overwrite some stat data with the info from\nindex.stat.\n\nBack to the original question, I'm hoping to reduce some significant\nnumbers above to less than 10ms with this. So I see all good points\nbut no bad ones. Time to ask git@vger to give some. I'm actually\ntrying this idea in my untracked cache because I can't afford to lose\n50% of the gain from untracked cache, just because I have to save some\nbits in the giant $GIT_DIR/index and take the cost of rehashing.\n\n(*) this is with the \"untracked cache\" enabled and total time is about\n40% less than upstream \"git status\". The numbers against upstream \"git\nstatus\" are actually less signficant. But I have to think positive\nthat one day untracked cache may be merged :)\n-- \nDuy\n"},{"id":"239075","messageId":"xmqq4n1qcz3d.fsf@gitster.dls.corp.google.com","threadId":"36436","inReplyTo":"CACsJy8CzZ7H4pffNccBBpvpn5oT5tud-Tx=Nu1c=q2SB7Zi8eg@mail.gmail.com","subject":"Re: Store refreshed stat info in a separate file?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-18T17:43:50Z","receivedAt":"2014-04-18T17:43:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> The major cost of writing an index is the SHA-1 hashing. The bigger\n> the written part is, the higher cost we pay. So what if we write\n> stat-only data to a separate file? Think of it as an index extension,\n> only it stays outside the index. On webkit with 182k files, the stat\n> data size would be about 6MB (its index v4 is 15M for comparison). But\n> with stat-only we could employ some cheap but efficient compressing,\n> sd_dev, sd_uid and sd_gid are likely the same for every entry. And we\n> could store the stat data of updated entries only. So I'm hoping to\n> get that 6MB down to a few hundred KBs. That makes hashing lightning\n> fast.\n\nIt is perfectly OK to store your verbose stat data after deflating\nit in the index as an index extension, so \"storing 6MB that can be\ncompressed efficiently without compressing is dumb\" applies whether\nthe result is stored in the index or in a separate file, I would\nthink.\n\nHaving said that, I do not think there is a fundamental reason why\nthe stat data has to live inside the same index file.  A separate\nfile is just fine, as long as you can reliably detect that they went\nout of sync for whatever reason (e.g. \"the index proper updated, a\nstale stat file left beind\"), and storing the trailer checksum from\nthe corresponding index in this new file is an obvious and good\nsolution.\n\nI am not sure if that should be called index.stat, though.  It is\nmore about untracked files.  The stat data for cached paths are in\nthe index proper, so what you are adding is not what we would call\n\"stat info\" when we talk about the index.\n"},{"id":"239628","messageId":"CACsJy8AV0yQNWnxu+J09UNEEsd6nSad90ZcOzB4GbfZtpYzZaA@mail.gmail.com","threadId":"36436","inReplyTo":"xmqq4n1qcz3d.fsf@gitster.dls.corp.google.com","subject":"Re: Store refreshed stat info in a separate file?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2014-04-25T05:18:08Z","receivedAt":"2014-04-25T05:18:08Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Apr 19, 2014 at 12:43 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Having said that, I do not think there is a fundamental reason why\n> the stat data has to live inside the same index file.  A separate\n> file is just fine, as long as you can reliably detect that they went\n> out of sync for whatever reason (e.g. \"the index proper updated, a\n> stale stat file left beind\"), and storing the trailer checksum from\n> the corresponding index in this new file is an obvious and good\n> solution.\n\nI've gone further and store index updates (including entry removals\nand additions) to the second index file so that index I/O cost is now\nproportional to the number of changed entries, not the work tree size\n(sort of). Which makes it scale much better when the work tree is\nhuge. There is one flaw though. I'm expecting many \"yuck\" responses\nfrom people. So let's try to settle it now, or drop the idea.\n\nThe idea is we can support another mode, where index content is stored\nin two files, the small $GIT_DIR/index and large $GIT_DIR/index.base.\n\"index\" contains changes that should be applied to \"index.base\".\nWhenever you do something to the index, \"index\" records those actions.\nGit reads both index.base and index, then replay the action to have\nthe final index in memory. \"index.base\" contains full worktree data\nand remains unchanged until \"index\" becomes too big/slow that changes\nshould be merged back to \"index.base\". This works great (my prototype\npassed the test suite), and even greater than index v5 because v5\nstill rewrites the whole index file when an entry is added or removed.\n\nBut there is a problem with atomic update. The good old rename() does\nnot work well with 2 files. This is not a problem with the C part, I\ncan still make atomic update work. Scripts, on the other hand, may\nrely on \"mv\" or similar commands/functions to prepare a temp index and\nmove it to $GIT_DIR/index. The workaround is merge back two files into\na single index file so that scripts can \"mv $temp_index\" as before and\npay the whole-index I/O penalty. An alternative is store two files in\none, the one index file actually consists two subfiles. We avoid the\natomic update problem, but we pay I/O cost for writing 10MB every time\nan index is updated (but not hashing 10MB file) and introduce a new\nindex format. This is even yuckier in my opinion.\n\nShould I continue, or drop it?\n-- \nDuy\n"}]}