{"thread":{"id":"34534","subject":"[RFC] Faster git grep.","startedAt":"2013-07-25T18:29:05Z","lastAt":"2013-07-26T05:45:50Z","messageCount":6,"participants":["Ondřej Bílka","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"224085","messageId":"20130725182905.GA7664@domone.kolej.mff.cuni.cz","threadId":"34534","inReplyTo":null,"subject":"[RFC] Faster git grep.","fromName":"Ondřej Bílka","fromEmail":"neleai@seznam.cz","sentAt":"2013-07-25T18:29:05Z","receivedAt":"2013-07-25T18:29:05Z","isPatch":false,"sender":{"key":"neleai@seznam.cz","avatar":"https://avatars.githubusercontent.com/u/48067?v=4"},"body":"Hi, \n\nWhen I do git grep then with big codebase (gcc) it executes slowly.\nI am thinking to add option to speed up search time.\n\nOne solution would be to use same trick as was done in google code. \nBuild and keep database of trigraphs and which files contain how many of\nthem. When querry is made then check\nonly these files that have appropriate combination of trigraphs.\n\nUpdating database would be relatively inexpensive compared to disk\naccess we need to do anyway.\n\nA space usage might be problem so which is why I decided go option\nroute.\n\nComments, pointers?\n\nOndra\n"},{"id":"224090","messageId":"20130725200857.GB1225@sigill.intra.peff.net","threadId":"34534","inReplyTo":"20130725182905.GA7664@domone.kolej.mff.cuni.cz","subject":"Re: [RFC] Faster git grep.","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-25T20:08:57Z","receivedAt":"2013-07-25T20:08:57Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 25, 2013 at 08:29:05PM +0200, Ondřej Bílka wrote:\n\n> One solution would be to use same trick as was done in google code.\n> Build and keep database of trigraphs and which files contain how many of\n> them. When querry is made then check\n> only these files that have appropriate combination of trigraphs.\n\nThat seems like a sensible approach.\n\n> Updating database would be relatively inexpensive compared to disk\n> access we need to do anyway.\n\nYes, I think it can be quite cheap, since you would only need to\nre-index files that have changed (and git is very quick at telling you\nwhat those files are).\n\n> A space usage might be problem so which is why I decided go option\n> route.\n> \n> Comments, pointers?\n\nI think it is a good idea, but not need to be part of core git. It seems\nmore like you would want to glue together an existing code-indexing\nsolution (like codesearch) with git (which would provide the list of\nfiles to index and to search).\n\nIf that proves useful in practice, but the interface is clunky for\nwhatever reason, then a good follow-on project could be to build support\nfor updating and using the index via the usual \"git grep\".\n\n-Peff\n"},{"id":"224092","messageId":"7vli4u4bkm.fsf@alter.siamese.dyndns.org","threadId":"34534","inReplyTo":"20130725182905.GA7664@domone.kolej.mff.cuni.cz","subject":"Re: [RFC] Faster git grep.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-25T20:41:13Z","receivedAt":"2013-07-25T20:41:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ondřej Bílka <neleai@seznam.cz> writes:\n\n> One solution would be to use same trick as was done in google code. \n> Build and keep database of trigraphs and which files contain how many of\n> them. When querry is made then check\n> only these files that have appropriate combination of trigraphs.\n\nThis depends on how you go about trying to reducing the database\noverhead, I think.  For example, a very naive approach would be to\ncreate such trigraph hit index for each and every commit for all\npaths.  When \"git grep $commit $pattern\" is run, you would consult\nsuch table with $commit and potential trigraphs derived from the\n$pattern to grab the potential paths your hits _might_ be in.\n\nBut the contents of a path usually do not change in each and every\ncommit.  So you may want to instead index with the blob object names\n(i.e. which trigraphs appear in what blobs).  But once you go that\nroute, your \"git grep $commit $pattern\" needs to read and enumerate\nall the blobs that appear in $commit's tree, and see which blobs may\npotentially have hits.  Then you would need to build an index every\ntime you make a new commit for blobs whose trigraphs have not been\ncounted.\n\nNice thing is that once a blob (or a commit for that matter) is\ncreated and its object name is known, its contents will not change,\nso you can index once and reuse it many times.  But I am not yet\nconvinced if pre-indexing is an overall win, compared to the cost of\nmaintaining such a database.\n"},{"id":"224094","messageId":"20130725213100.GA28551@domone.kolej.mff.cuni.cz","threadId":"34534","inReplyTo":"7vli4u4bkm.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC] Faster git grep.","fromName":"Ondřej Bílka","fromEmail":"neleai@seznam.cz","sentAt":"2013-07-25T21:31:00Z","receivedAt":"2013-07-25T21:31:00Z","isPatch":false,"sender":{"key":"neleai@seznam.cz","avatar":"https://avatars.githubusercontent.com/u/48067?v=4"},"body":"On Thu, Jul 25, 2013 at 01:41:13PM -0700, Junio C Hamano wrote:\n> Ondřej Bílka <neleai@seznam.cz> writes:\n> \n> > One solution would be to use same trick as was done in google code. \n> > Build and keep database of trigraphs and which files contain how many of\n> > them. When querry is made then check\n> > only these files that have appropriate combination of trigraphs.\n> \n> This depends on how you go about trying to reducing the database\n> overhead, I think.  For example, a very naive approach would be to\n> create such trigraph hit index for each and every commit for all\n> paths.  When \"git grep $commit $pattern\" is run, you would consult\n> such table with $commit and potential trigraphs derived from the\n> $pattern to grab the potential paths your hits _might_ be in.\n>\nDo you think that git grep $commit $pattern is run in more than 1% \nof cases than git grep $pattern ?\n\nIf grepping random commit in history is important use case then keeping\ndb information in history makes sense. Otherwise just having database\nfor current version and updating it on the fly as version changes is\nenough.\n> But the contents of a path usually do not change in each and every\n> commit.  So you may want to instead index with the blob object names\n> (i.e. which trigraphs appear in what blobs).  But once you go that\n> route, your \"git grep $commit $pattern\" needs to read and enumerate\n> all the blobs that appear in $commit's tree, and see which blobs may\n> potentially have hits.  Then you would need to build an index every\n> time you make a new commit for blobs whose trigraphs have not been\n> counted.\n> \n> Nice thing is that once a blob (or a commit for that matter) is\n> created and its object name is known, its contents will not change,\n> so you can index once and reuse it many times.  But I am not yet\n> convinced if pre-indexing is an overall win, compared to the cost of\n> maintaining such a database.\n"},{"id":"224097","messageId":"7vhafi3y99.fsf@alter.siamese.dyndns.org","threadId":"34534","inReplyTo":"20130725213100.GA28551@domone.kolej.mff.cuni.cz","subject":"Re: [RFC] Faster git grep.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-26T01:28:50Z","receivedAt":"2013-07-26T01:28:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ondřej Bílka <neleai@seznam.cz> writes:\n\n> If grepping random commit in history is important use case then keeping\n> db information in history makes sense. Otherwise just having database\n> for current version and updating it on the fly as version changes is\n> enough.\n\nWill you reindex every time I do \"git checkout next; git checkout\nmaster\"?\n"},{"id":"224105","messageId":"20130726054550.GA23320@domone.kolej.mff.cuni.cz","threadId":"34534","inReplyTo":"7vhafi3y99.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC] Faster git grep.","fromName":"Ondřej Bílka","fromEmail":"neleai@seznam.cz","sentAt":"2013-07-26T05:45:50Z","receivedAt":"2013-07-26T05:45:50Z","isPatch":false,"sender":{"key":"neleai@seznam.cz","avatar":"https://avatars.githubusercontent.com/u/48067?v=4"},"body":"On Thu, Jul 25, 2013 at 06:28:50PM -0700, Junio C Hamano wrote:\n> Ondřej Bílka <neleai@seznam.cz> writes:\n> \n> > If grepping random commit in history is important use case then keeping\n> > db information in history makes sense. Otherwise just having database\n> > for current version and updating it on the fly as version changes is\n> > enough.\n> \n> Will you reindex every time I do \"git checkout next; git checkout\n> master\"?\n\nThis is separate issue as you would need to change index anyway, number\nof changes would be proportionate to size of diff so you would not gain\nmuch. Possible problem here is that you would end changing many files. \nA possible solution is do rebuilding in background.\n\nFor switching often to different branches that are vastly different a\nbest solution for me seems to keep separate index for each branch.\n\nAlso data structure is trigraph: list of files with counts.\n"}]}