{"thread":{"id":"58217","subject":"Pre-computed similarity indexes","startedAt":"2022-07-24T14:24:22Z","lastAt":"2022-07-26T07:32:03Z","messageCount":2,"participants":["Philip","Elijah Newren"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"459850","messageId":"CAJ6X7_UNOMusKKbFzS12DRhrOkVXAEgED8djA2kxjfFmbv4GwA@mail.gmail.com","threadId":"58217","inReplyTo":null,"subject":"Pre-computed similarity indexes","fromName":"Philip","fromEmail":"philip.c.peterson@gmail.com","sentAt":"2022-07-24T14:23:41Z","receivedAt":"2022-07-24T14:24:22Z","isPatch":false,"sender":{"key":"philip.c.peterson@gmail.com","avatar":"https://gravatar.com/avatar/2dfa9764cb8e5ce07b180670c62dc3fc643e4f8e2f2afafcb7220ac10ea4b4ca?d=mp&s=160"},"body":"Hello all,\n\nI noticed that Git LFS-tracked files cannot correctly detect renames,\nprobably because Git is not doing a similarity check on the content.\nDoing so would require having the content (instead of just the LFS\npointer), and that would require running the smudge filter, which\ncould take a very long time due to network requests, very expensive if\ndone on every file in the repo. When doing a `git log` for example, it\nwould need to run the smudge filter on all LFS files in all revisions,\npotentially pulling down all the content from the LFS server, just to\ndecide if there were any renames.\n\nI wonder if there has been any thought given to whether a similarity\nindex can be pre-computed somewhere? (Maybe upon commit with each of\nthe commit's ancestors.) Or if this limitation has been discussed\nbefore here.\n\nThank you,\nPhilip Peterson\n"},{"id":"459963","messageId":"CABPp-BFFir4iM1y3=Fjfcj3OVT0sgSW49796aKvTNWbWoK+LGg@mail.gmail.com","threadId":"58217","inReplyTo":"CAJ6X7_UNOMusKKbFzS12DRhrOkVXAEgED8djA2kxjfFmbv4GwA@mail.gmail.com","subject":"Re: Pre-computed similarity indexes","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2022-07-26T07:27:27Z","receivedAt":"2022-07-26T07:32:03Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Sun, Jul 24, 2022 at 7:29 AM Philip <philip.c.peterson@gmail.com> wrote:\n>\n> Hello all,\n>\n> I noticed that Git LFS-tracked files cannot correctly detect renames,\n\n\"correctly\"?  I was expecting you to say that it just wouldn't detect\nrenames at all for LFS files.  Does the wording of your question imply\nthat Git is detecting LFS files as renames that aren't actually\nrenames?\n\nYou got me curious.  It appears the LFS pointer files are three lines\nlong (unless I'm misreading the spec; I have virtually no experience\nwith LFS).  The first line appears to always be the same for practical\npurposes, the second line holds the hash, and the third line holds the\nreal file length.  What counts as far as rename detection isn't the\nnumber of matching lines, though, but the number of matching\ncharacters from matching lines.  So if one pointer file had e.g.\n\n    version https://git-lfs.github.com/spec/v1\n    oid sha256:4d7a214614ab2935c943f9e0ff69d22eadbb8f32b1258daaa5e2ca24d17e2393\n    size 12345\n\nand you have another that looks like\n\n    version https://git-lfs.github.com/spec/v1\n    oid sha256:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa24d17e2393\n    size 12345\n\nthen, since git splits lines into 64-byte chunks, then our \"matching lines\" are:\n    version https://git-lfs.github.com/spec/v1\n    24d17e2393\n    size 12345\n(for a total of 66 bytes, including newline characters), and the\n\"unmatching lines\" are\n    oid sha256:4d7a214614ab2935c943f9e0ff69d22eadbb8f32b1258daaa5e2ca\n    oid sha256:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\n(neither of which has a trailing newline)\n\nThe longest of these two pointer files is 130 bytes (actually, both\nfiles are 130 bytes).  Since the matching bytes from matching lines is\n66, we check that 66/130.0 > 0.5, so Git will consider this a rename\nusing the default similarity threshold of 50%.\n\nSo, for LFS files to be detected as a rename, the real file size has\nto be at least 100 bytes (so that the real file size has at least\nthree digits), the real files have to be the same size (e.g. in our\nexample they were both 12345 bytes), and the last 10 hex digits of\ntheir sha256 must match.\n\nThe first condition is probably trivial to satisfy.  The second is a\nlittle unlikely, but it's pretty easy to imagine random matches.\nHowever, you'd have to have an awful lot of LFS files in a repository\nbefore there's any realistic chance of meeting the third condition,\nthough.  Somewhere on the order of a million of them (based on\nbirthday paradox approximations) -- all with the same underlying file\nsize on the third line.  (Or, if you had lots of different underlying\nfile sizes, then dramatically more LFS files would be required to get\na collision.)  Given that each file is large, that'd have to be a\nginormous repository if fully checked out.  So, is this actually an\nissue in practice?  (Perhaps there's a risk of a dedicated disgruntled\nemployee generating trailing hash collisions just to make git log show\nmisleading rename output for LFS files...but if so, that seems pretty\ntame for the amount of effort put in?)\n\nOr did I read too much into your \"correctly\" wording, and were you\nsimply not getting any LFS files detected as renames despite knowing\nsome of the underlying large files are actually renames?\n\n> probably because Git is not doing a similarity check on the content.\n> Doing so would require having the content (instead of just the LFS\n> pointer), and that would require running the smudge filter, which\n> could take a very long time due to network requests, very expensive if\n> done on every file in the repo.\n\n...and it probably wouldn't return meaningful results anyway since the\n'L' in \"LFS\" stands for 'Large' and Git's rename detection only works\nfor small to medium sized files.  (I mean, it'll technically operate\non large files, at least those smaller than core.bigFileThreshold, but\nthe quality of its answers degrades linearly with file size until it's\nessentially meaningless at about 8MB...with the exception that it does\nnotice that files with dissimilar sizes can't be renames.)\n\n> When doing a `git log` for example, it\n> would need to run the smudge filter on all LFS files in all revisions,\n> potentially pulling down all the content from the LFS server, just to\n> decide if there were any renames.\n>\n> I wonder if there has been any thought given to whether a similarity\n> index can be pre-computed somewhere? (Maybe upon commit with each of\n> the commit's ancestors.)\n\nComputing for each commit relative to each of its ancestors would only\nhelp with 'git log'; it wouldn't help with\ndiff/merge/rebase/revert/etc.  If you want rename handling it to work\nin general for these files, you'd have to precompute it for each\ncommit with each other commit in history.  And for it to be reliable,\nyou'd have to update it with every new commit.  That'd make `git\ncommit` take time relative to the number of commits in history.  It'd\nmake `git pull` and such take an amount of time relative to the number\nof commits in history multiplied by the number of commits being\ndownloaded.  And, of course, that \"relative\" consideration in both\nthose places includes a factor scaled by the average sizes of the\nlarge files being compared, so the \"constant\" is pretty big too.\n\n> Or if this limitation has been discussed\n> before here.\n\nI did a quick search and didn't see anything.  However, I have thought\nabout the idea of precomputing similarities in general before, but\nrealized that it ends up just shifting performance problems elsewhere\nand quite likely making them worse overall.  So, I think you'd need a\ndifferent solution of some sort here if you want rename detection for\nLFS files.\n"}]}