{"thread":{"id":"7194","subject":"A tracking tree for the active work space","startedAt":"2007-03-11T14:06:11Z","lastAt":"2007-03-12T01:39:24Z","messageCount":7,"participants":["Jon Smirl","Junio C Hamano","Johannes Schindelin","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"36805","messageId":"9e4733910703110706m14abae25r2a965b644d8c3bbb@mail.gmail.com","threadId":"7194","inReplyTo":null,"subject":"A tracking tree for the active work space","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-03-11T14:06:11Z","receivedAt":"2007-03-11T14:06:11Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Reading the other thread on tracking temporary changes made me think\nof using inotify with git. The basic idea would be to a daemon running\nthat uses inotify to listen for changes in the working tree. As these\nchanges happen they get committed to a tracking tree.\n\nThe tracking tree serves two purposes. First it is a good way to\nrecover from programmer error. I have definitely written big chunks of\ncode, discarded them, and then realized later that they were the right\nsolution and had to write them again.\n\nThe tracking tree also makes a 'git grep' for uncommitted changes\neasier to implement since the changes are always committed with this\nmodel. For dual processors the inverted index can be computed in\nparallel with editing.\n\nOf course this daemon needs some smarts. You don't want it generating\na delta the hard way from a git check out of a different workspace It\nwill also make real check-ins instant since you just copy the tip of\nthe tacking tree.\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"36849","messageId":"7vhcsrwn8d.fsf@assigned-by-dhcp.cox.net","threadId":"7194","inReplyTo":"9e4733910703110706m14abae25r2a965b644d8c3bbb@mail.gmail.com","subject":"Re: A tracking tree for the active work space","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-11T20:15:30Z","receivedAt":"2007-03-11T20:15:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jon Smirl\" writes:\n\n> Reading the other thread on tracking temporary changes made me think\n> of using inotify with git. The basic idea would be to a daemon running\n> that uses inotify to listen for changes in the working tree. As these\n> changes happen they get committed to a tracking tree.\n\nI think it is an interesting idea, but can be used with any SCM\nnot just git ;-).\n"},{"id":"36856","messageId":"9e4733910703111335j20c0acf4wa12c2d410580898b@mail.gmail.com","threadId":"7194","inReplyTo":"7vhcsrwn8d.fsf@assigned-by-dhcp.cox.net","subject":"Re: A tracking tree for the active work space","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-03-11T20:35:50Z","receivedAt":"2007-03-11T20:35:50Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 3/11/07, Junio C Hamano wrote:\n> \"Jon Smirl\" writes:\n>\n> > Reading the other thread on tracking temporary changes made me think\n> > of using inotify with git. The basic idea would be to a daemon running\n> > that uses inotify to listen for changes in the working tree. As these\n> > changes happen they get committed to a tracking tree.\n>\n> I think it is an interesting idea, but can be used with any SCM\n> not just git ;-).\n\nAs for the part about 'git grep' Shawn and I have been talking off\nand on about experimenting with an inverted index for a packfile\nformat. The basic idea is that you tokenize the input and turn a\nsource file into a list of tokens. You diff with the list of tokens\nlike you would normally do with text. There is a universal dictionary\nfor tokens, a token's id is it's position in the dictionary.\n\nTokenized text is one of the most compact compression schemes known.\nIt can get even more compact by tokenizing common phrases and using\nvariable length token ids. Compression schemes like this are used in\nweb search engines. Of course you keep a check in place for input that\ndoesn't tokenize (binary) and fallback to gzip.\n\nTo build 'git grep' you make a bitmap index for each token in the\ndictionary and put a one in it if the file has the token. Gzip these\nindexes and then there are algorithms for doing and/or operations on\nthe zipped indexes without expanding them. grep is almost instant over\ngigabytes of text if indexes like this are available.\n\nKeeping everything up to date on a dual core system is pretty much\nfree since that second core is rarely doing anything while you are\nediting.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"36865","messageId":"Pine.LNX.4.63.0703112209160.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7194","inReplyTo":"9e4733910703111335j20c0acf4wa12c2d410580898b@mail.gmail.com","subject":"Re: A tracking tree for the active work space","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-11T21:31:58Z","receivedAt":"2007-03-11T21:31:58Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 11 Mar 2007, Jon Smirl wrote:\n\n> As for the part about 'git grep' Shawn and I have been talking off and \n> on about experimenting with an inverted index for a packfile format. The \n> basic idea is that you tokenize the input and turn a source file into a \n> list of tokens. You diff with the list of tokens like you would normally \n> do with text. There is a universal dictionary for tokens, a token's id \n> is it's position in the dictionary.\n\nAll in all, this is an interesting idea.\n\nHowever, I see some problems I'd like to know solutions for:\n\n- how to determine the optimal length of the tokens? (It is easy if you \n tokenize on the word level, but you suggested that it is more efficient \n to have longer phrases.)\n\n- the search terms can be _part of_ the tokens. In fact, a search term can \n be the postfix of one token, then a list of other tokens, and then a \n prefix of yet another token. It might not be really cheap to construct \n _all_ possible combinations of tokens which make up the search term...\n\n- how do you want to cope with regular expressions? (The previous problem \n only addresses simple, constant search terms, i.e. no true regular \n expressions.)\n\n- at the moment, most objects which are contained by a pack are relatively \n cheaply transported via the pack protocol. IIUC your new pack format \n would need _exactly_ the same dictionary to be transmitted as-is. IOW\n how do you want to make on-the-fly pack generation cheap again?\n\nDon't get me wrong: I don't want to discourage you, but it is too easy to \noptimize for the wrong use cases (I expact a repack, or a fetch, to happen \nmuch more often than a grep). If you can address above-mentioned issues, \nI see no reason why the new pack format should not be used instead of the \ncurrent one.\n\nCiao,\nDscho\n"},{"id":"36867","messageId":"20070311214011.GA21155@coredump.intra.peff.net","threadId":"7194","inReplyTo":"Pine.LNX.4.63.0703112209160.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: A tracking tree for the active work space","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-03-11T21:40:11Z","receivedAt":"2007-03-11T21:40:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 11, 2007 at 10:31:58PM +0100, Johannes Schindelin wrote:\n\n> - how do you want to cope with regular expressions? (The previous problem \n> only addresses simple, constant search terms, i.e. no true regular \n> expressions.)\n\nI expect you could extract any obvious tokens from the regex, and then\nrun the regex only over the files which contain those tokens. Obviously\nyour worst case performance will be the same as the original grep (plus\nthe overhead of looking up the tokens), but in practice, I expect you\ncould end up searching through only a fraction of the files (depending\non your regexp and how diverse the data set is).\n\nOf course, I have never had a complaint about the speed of git-grep, so\nmaybe it's not all that compelling. :)\n\n-Peff\n"},{"id":"36880","messageId":"Pine.LNX.4.63.0703120017450.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"7194","inReplyTo":"9e4733910703111335j20c0acf4wa12c2d410580898b@mail.gmail.com","subject":"Re: A tracking tree for the active work space","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-03-11T23:18:27Z","receivedAt":"2007-03-11T23:18:27Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 11 Mar 2007, Jon Smirl wrote:\n\n> On 3/11/07, Junio C Hamano wrote:\n> > \"Jon Smirl\" writes:\n> > \n> > > Reading the other thread on tracking temporary changes made me think\n> > > of using inotify with git. The basic idea would be to a daemon running\n> > > that uses inotify to listen for changes in the working tree. As these\n> > > changes happen they get committed to a tracking tree.\n> > \n> > I think it is an interesting idea, but can be used with any SCM\n> > not just git ;-).\n\nI just stumbled over this:\n\n\thttp://arcs.unixtreaty.com/\n\nwhich might or might not do what you want, judging by the description.\n\nCiao,\nDscho\n"},{"id":"36881","messageId":"9e4733910703111839jca1eef5l70c097deb241b602@mail.gmail.com","threadId":"7194","inReplyTo":"Pine.LNX.4.63.0703112209160.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: A tracking tree for the active work space","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-03-12T01:39:24Z","receivedAt":"2007-03-12T01:39:24Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 3/11/07, Johannes Schindelin wrote:\n> Hi,\n>\n> On Sun, 11 Mar 2007, Jon Smirl wrote:\n>\n> > As for the part about 'git grep' Shawn and I have been talking off and\n> > on about experimenting with an inverted index for a packfile format. The\n> > basic idea is that you tokenize the input and turn a source file into a\n> > list of tokens. You diff with the list of tokens like you would normally\n> > do with text. There is a universal dictionary for tokens, a token's id\n> > is it's position in the dictionary.\n>\n> All in all, this is an interesting idea.\n>\n> However, I see some problems I'd like to know solutions for:\n>\n> - how to determine the optimal length of the tokens? (It is easy if you\n> tokenize on the word level, but you suggested that it is more efficient\n> to have longer phrases.)\n>\n> - the search terms can be _part of_ the tokens. In fact, a search term can\n> be the postfix of one token, then a list of other tokens, and then a\n> prefix of yet another token. It might not be really cheap to construct\n> _all_ possible combinations of tokens which make up the search term...\n>\n> - how do you want to cope with regular expressions? (The previous problem\n> only addresses simple, constant search terms, i.e. no true regular\n> expressions.)\n\nI just described a simple scheme. This is an area where a lot of\nresearch has been done and the previous three problems have been\naddressed by many papers. For example there are more complicated index\nforms which support queries like find hat within ten words of cat.\nAnother feature is word stemming which can be used to do regular\nexpression searching. Let's get a basic version working first and then\ngo for the fancier ones.\n\n> - at the moment, most objects which are contained by a pack are relatively\n> cheaply transported via the pack protocol. IIUC your new pack format\n> would need _exactly_ the same dictionary to be transmitted as-is. IOW\n> how do you want to make on-the-fly pack generation cheap again?\n\nYou can either copy down an entire pack including the dictionaries; or\nexpand the tokenized text back into normal text, gzip it and send it\ndown the wire. Dictionaries are only a few MB so everything fits into\nRAM.\n\n> Don't get me wrong: I don't want to discourage you, but it is too easy to\n> optimize for the wrong use cases (I expact a repack, or a fetch, to happen\n> much more often than a grep). If you can address above-mentioned issues,\n\nWhen I am working on other people's code in the kernel I do greps all\nof the time. When working on your own code you don't need it as much\nsince you know where everything is.\n\nSupport like this could also be the basis for future IDE integration.\nThe indexes would allow an IDE to quickly do refactoring operations\nlike renames. Mozilla is doing some major refactoring currently and\nthey are writing custom programs to do it since they lack efficient\ntools.\n\nThe indexes don't have to be simple word lists. I've used systems\nwhere the index is closer to being a parse tree of the C code. In\nthose systems refactoring is trivial to do, it's more like doing\noperations on a database of code than using a normal text editor. You\ncan also easily query things like all users of a variable, the\ndefinition, etc. Operations like these aren't a problem on small\nprojects but trying doing them when there are 20M lines of source.\n\nAlso note that these are just indexes and pack formats. I can chose to\nconvert my git db to this form and you don't have to follow my choice.\n\n> I see no reason why the new pack format should not be used instead of the\n> current one.\n>\n> Ciao,\n> Dscho\n>\n>\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"}]}