{"thread":{"id":"8974","subject":"What happened with git-note?","startedAt":"2007-07-10T23:17:35Z","lastAt":"2007-07-11T01:17:05Z","messageCount":2,"participants":["Alberto Bertogli","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"46991","messageId":"20070710231735.GZ1813@gmail.com","threadId":"8974","inReplyTo":null,"subject":"What happened with git-note?","fromName":"Alberto Bertogli","fromEmail":"albertito@gmail.com","sentAt":"2007-07-10T23:17:35Z","receivedAt":"2007-07-10T23:17:35Z","isPatch":false,"sender":{"key":"albertito@gmail.com","avatar":null},"body":"\nHi!\n\nThere was a very long thread about a proposed feature, git-note\n(http://thread.gmane.org/gmane.comp.version-control.git/46770/focus=48540),\naround May this year.\n\nI was wondering what happened to it, because some issues were brought up\nbut then everything seem to have stalled.\n\nIs someone working on it? Is there a clear list of the pending issues\nsomewhere?\n\nThanks,\n\t\tAlberto\n"},{"id":"46994","messageId":"Pine.LNX.4.64.0707110153280.4047@racer.site","threadId":"8974","inReplyTo":"20070710231735.GZ1813@gmail.com","subject":"Re: What happened with git-note?","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-07-11T01:17:05Z","receivedAt":"2007-07-11T01:17:05Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\n[Johan, I Cc'ed you, since you were the person pushing for git-notes \noriginally. Junio, I Cc'ed you, because you correctly pointed out the \nflaws in my approach.]\n\nOn Tue, 10 Jul 2007, Alberto Bertogli wrote:\n\n> There was a very long thread about a proposed feature, git-note \n> (http://thread.gmane.org/gmane.comp.version-control.git/46770/focus=48540), \n> around May this year.\n> \n> I was wondering what happened to it, because some issues were brought up\n> but then everything seem to have stalled.\n> \n> Is someone working on it? Is there a clear list of the pending issues\n> somewhere?\n\nOkay, I seem to be at fault for the stalling.  So I better speak up about \nwhat my proof-of-concept did:\n\nIt creates a new ref, \"refs/notes/commits\", which had a tree object in it. \nThe tree entries were actually fan-out directories a la .git/objects/??/. \nSo if you added a not to commit abcdef01234..., it created a \"file\" named \nrefs/notes/commits:ab/cdef01234...\n\nThe advantages of this approach, as compared to an external list, or even \nSQLite database were, amongst others:\n\n- you can use most of the existing framework (storage, pruning, etc.),\n\n- there is an obvious way how to fetch the notes from someone else,\n\n- there is an obvious way how to deal with conflicts when merging notes\n  from someone else,\n\n- it is conceptually trivial.\n\nHowever, the biggest disadvantage was pointed out by Junio:\n\nThe tree objects under refs/notes/commits:??/ can get pretty large, in \ntheory.  Suppose you have a rate of a couple of hundred commits a day, and \nyou want to use the notes framework, amongst others, to be able to add \nAcked-by's all over the place.  Pretty soon we are in the hundreds of \nentries in the tree objects.\n\nI thought that this is not a problem, since the names all have the same \nlength.  Alas, Git is general purpose, so it does not, and cannot, assume \na certain filename format.  Git might be considered a stupid content \ntracker, but it is not quite that stupid.\n\nSince the tree objects just contain lists of tree entries, and each tree \nentry is variable length, you have to look through half of the entries on \naverage, before you find the one you look for.\n\nPossible solutions I can come up with:\n\nThere was a lot of talk, and quite a few good ideas, in the packv4 side \nbranch, which was undertaken by Nico and Shawn.  The basic idea, IIUC, is \nto store objects differently, by having nice things like a filename table \ncontaining the most common names, sorted, which are then not only \naddressed much more efficiently (by a 16-bit index), but reverse indexing \nis also much more efficient, since you do not have to expand and compare \nthe full filenames, but instead compare 16-bin numbers.\n\nThis format would help with the approach I presented above.\n\nAnother idea which just crossed my mind, is to add indexes which are \ngenerated locally, but not transmitted when fetching, much like the pack \nindices, which are generated from the pack while fetching it.\n\nThere are a couple of possible technical ways to do that efficiently, such \nas mmap()ed rbtrees, or hashtables.  Of course, Git's own history suggests \nto prefer hashtables over other data structures, when your keys are \nalready pretty good hashes, which they are.  However, I have not thought \nit through, what with the issue of growing the data structure, or \nthrashing the I/O caches.\n\nOf course, one does not have to go with the approach of storing the things \nas blobs.  There might well be a genius coming along, reading this mail, \nand proposing the uber-solution.  But dammit, I am pretty sure that we \nhave a real good framework, and that a proper solution is just a stone's \nthrow away.\n\nCiao,\nDscho\n"}]}