{"thread":{"id":"23924","subject":"Libgit2 on the Summer of Code","startedAt":"2010-05-27T16:25:32Z","lastAt":"2010-06-02T18:42:21Z","messageCount":7,"participants":["Vicent Marti","Ilari Liusvaara","Shawn O. Pearce","Alex Riesen","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"142455","messageId":"AANLkTil-M3kQGbRZIacItlwr37Lf3lso7FspftLr43_F@mail.gmail.com","threadId":"23924","inReplyTo":null,"subject":"Libgit2 on the Summer of Code","fromName":"Vicent Marti","fromEmail":"tanoku@gmail.com","sentAt":"2010-05-27T16:25:32Z","receivedAt":"2010-05-27T16:25:32Z","isPatch":false,"sender":{"key":"tanoku@gmail.com","avatar":"https://gravatar.com/avatar/271386991cb4c2b8f1e1ed1d059f3422cc3485de7a598f65043f70be021d095b?d=mp&s=160"},"body":"Hello fine gentlemen,\n\nI believe a short introduction is due. My name is Vicent Marti and I'm\nthe Google Summer of Code student who will be working on libgit2 this\nyear. If you haven't heard of it before, libgit2 [1] is a C library\nwhich intents to re implement all of Git's core in a saner, reentrant\nmanner, with proper error handling and all the usual stuff you'd\nexpect from an actual library (including a less restrictive license).\n\nI'm being kindly mentored by Scott Chacon on this task, and it seems I\nmight have been a *tad* too much mentored (;d), because I've spent so\nmuch time discussing things with Scott and the other libgit2\ndevelopers that Sverre Rabbelier had to remind me that there's an\nactual Git mailing list and I haven't even introduced myself to it\nyet.\n\nWell, fear do not. I'm here (a couple weeks late, but here after all)\nand although I have been slacking on the community interaction part of\nthe Summer of Code, the actual project is well under tracks:\n\nAll the milestones for the first coding period are mostly finished\n(yay for that) and you can find the code and follow my progress on my\npublic github repo [2]. There is some documentation in place, and\nthere are some tests in place. In the following days I'll aim for\nabout 90% code coverage on the tests, to finish the documentation, and\nthen prepare the patch series for review on this list.\n\nMeanwhile, you are very much welcome to start flaming away before the\npatch series are ready. We have roughly one month and a half to fix up\nmy code to the project's standards; hopefully it won't be *that* bad\nand I will be able to implement some extra features before the\nevaluation.\n\nOh, and before I forget, my awesome mentor Scott is writing some Ruby\nbindings for the library [3], which at the moment are mostly in-sync\nwith all the new functionality I've added. Those will come in handy if\nyou want to try out the new features of Libgit2 with a more friendly\ninterface... as friendly as Ruby can be, that is. ;/\n\nThanks for your time, I'm looking forward to your input and I promise\nI'll be much more active on this list from now on.\n\nCheers,\nVicent Martí\nhttp://www.bellverde.org\n\n[1]: http://repo.or.cz/w/libgit2.git\n[2]: http://github.com/tanoku/libgit2-gsoc2010\n[3]: http://github.com/schacon/ribbit\n"},{"id":"142458","messageId":"20100527174636.GB9909@LK-Perkele-V2.elisa-laajakaista.fi","threadId":"23924","inReplyTo":"AANLkTil-M3kQGbRZIacItlwr37Lf3lso7FspftLr43_F@mail.gmail.com","subject":"Re: Libgit2 on the Summer of Code","fromName":"Ilari Liusvaara","fromEmail":"ilari.liusvaara@elisanet.fi","sentAt":"2010-05-27T17:46:36Z","receivedAt":"2010-05-27T17:46:36Z","isPatch":false,"sender":{"key":"ilari.liusvaara@elisanet.fi","avatar":null},"body":"On Thu, May 27, 2010 at 06:25:32PM +0200, Vicent Marti wrote:\n> \n> All the milestones for the first coding period are mostly finished\n> (yay for that) and you can find the code and follow my progress on my\n> public github repo [2]. There is some documentation in place, and\n> there are some tests in place. In the following days I'll aim for\n> about 90% code coverage on the tests, to finish the documentation, and\n> then prepare the patch series for review on this list.\n> \n> Meanwhile, you are very much welcome to start flaming away before the\n> patch series are ready. We have roughly one month and a half to fix up\n> my code to the project's standards; hopefully it won't be *that* bad\n> and I will be able to implement some extra features before the\n> evaluation.\n\nI start the flaming... :->\n\n* I noticed that you seem to format if/while/for like this:\n\nif (foo)\n{\n something1;\n something2;\n}\nelse\n{\n something3;\n something4;\n}\n\nWhile the existing percedent seems to be:\n\nif (foo) {\n\tsomething1;\n\tsomething2;\n} else {\n\tsomething3;\n\tsomething4;\n}\n\n* Also, you appear to be using 4 spaces for indent, whereas the existing\npercedent appears to be indent by tab. Some functions appear to use mixed\nindents (sometimes even in one block construct).\n\n* There seems to be some trailing whitespace. I don't know the policies of\nlibgit2 on that, but I suppose it is not supposed to be there.\n\n* git_commit_list_push_back() fails silently if memory allocation fails. Is\nit supposed to? Same for git_commit_list_push_front().\n\n* Where algorithm in git_revpool_table__hash() is from? Since it appears to\nhash binary object IDs, wouldn't just simple sum/xor over words be sufficient\n(all SHA-1 output bits are very nearly independent). Or do you need to be\ncompatible with some other implementation (doesn't appear so, because hash\nis computed differently depending on endianess)?\n\n* gitrp_push() just returns if git_commit_parse_existing() fails. But causes\nof that failing seemingly can include ODB read errors, which are fairly\nserious...\n\n* Is gitrp__enroot() supposed to just ignore failures of\ngit_commit_parse_existing()? is 'commit->parents.head' valid even in this\ncase?\n\n* There are numerious cases where function that suspiciously lacks error\ncode is called (if error code is added, it presumably needs to be bubbled\nback to caller).\n\n-Ilari\n"},{"id":"142459","messageId":"20100527180554.GM16470@spearce.org","threadId":"23924","inReplyTo":"20100527174636.GB9909@LK-Perkele-V2.elisa-laajakaista.fi","subject":"Re: Libgit2 on the Summer of Code","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2010-05-27T18:05:54Z","receivedAt":"2010-05-27T18:05:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Ilari Liusvaara wrote:\n> * Where algorithm in git_revpool_table__hash() is from? Since it appears to\n> hash binary object IDs, wouldn't just simple sum/xor over words be sufficient\n> (all SHA-1 output bits are very nearly independent). Or do you need to be\n> compatible with some other implementation (doesn't appear so, because hash\n> is computed differently depending on endianess)?\n\nIf you need a hash value for a SHA-1, why not just cast the unsigned\nchar* to unsigned int* and load the first int as the hash code?\nThe output of SHA-1 is pretty evenly distributed, using the first\nfew bytes as an int should yield a sufficient distribution throughout\nthe hashtable.\n \n-- \nShawn.\n"},{"id":"142461","messageId":"AANLkTilE7UI3zg180U9GCB6DsByu3B9pwlG6xIyR8uiG@mail.gmail.com","threadId":"23924","inReplyTo":"20100527180554.GM16470@spearce.org","subject":"Re: Libgit2 on the Summer of Code","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2010-05-27T18:22:29Z","receivedAt":"2010-05-27T18:22:29Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Thu, May 27, 2010 at 20:05, Shawn O. Pearce wrote:\n> Ilari Liusvaara wrote:\n>> * Where algorithm in git_revpool_table__hash() is from? Since it appears to\n>> hash binary object IDs, wouldn't just simple sum/xor over words be sufficient\n>> (all SHA-1 output bits are very nearly independent). Or do you need to be\n>> compatible with some other implementation (doesn't appear so, because hash\n>> is computed differently depending on endianess)?\n>\n> If you need a hash value for a SHA-1, why not just cast the unsigned\n> char* to unsigned int* and load the first int as the hash code?\n> The output of SHA-1 is pretty evenly distributed, using the first\n> few bytes as an int should yield a sufficient distribution throughout\n> the hashtable.\n\nJust make sure the SHA1 data are properly aligned for your platform\n"},{"id":"142462","messageId":"20100527183534.GA10414@LK-Perkele-V2.elisa-laajakaista.fi","threadId":"23924","inReplyTo":"20100527180554.GM16470@spearce.org","subject":"Re: Libgit2 on the Summer of Code","fromName":"Ilari Liusvaara","fromEmail":"ilari.liusvaara@elisanet.fi","sentAt":"2010-05-27T18:35:34Z","receivedAt":"2010-05-27T18:35:34Z","isPatch":false,"sender":{"key":"ilari.liusvaara@elisanet.fi","avatar":null},"body":"On Thu, May 27, 2010 at 11:05:54AM -0700, Shawn O. Pearce wrote:\n> Ilari Liusvaara wrote:\n> > * Where algorithm in git_revpool_table__hash() is from? Since it appears to\n> > hash binary object IDs, wouldn't just simple sum/xor over words be sufficient\n> > (all SHA-1 output bits are very nearly independent). Or do you need to be\n> > compatible with some other implementation (doesn't appear so, because hash\n> > is computed differently depending on endianess)?\n> \n> If you need a hash value for a SHA-1, why not just cast the unsigned\n> char* to unsigned int* and load the first int as the hash code?\n> The output of SHA-1 is pretty evenly distributed, using the first\n> few bytes as an int should yield a sufficient distribution throughout\n> the hashtable.\n\nYeah, With pseudorandom function[*], all ways of reducing the output to n bits are\nat most as good as just taking first n bits. But if reducing output to [0, m),\nthe best way (distribution-wise, not speed-wise) is to take remainder of the whole\nvalue divided by m...\n\n[*] SHA-1 is not pseudorandom function, but for virtually all practical purposes\nit is.\n\n-Ilari\n"},{"id":"142476","messageId":"AANLkTillXInFUGR0tYqlPbdddfQKPbGDbjPEV0voaBev@mail.gmail.com","threadId":"23924","inReplyTo":"20100527183534.GA10414@LK-Perkele-V2.elisa-laajakaista.fi","subject":"Re: Libgit2 on the Summer of Code","fromName":"Vicent Marti","fromEmail":"tanoku@gmail.com","sentAt":"2010-05-28T00:15:43Z","receivedAt":"2010-05-28T00:15:43Z","isPatch":false,"sender":{"key":"tanoku@gmail.com","avatar":"https://gravatar.com/avatar/271386991cb4c2b8f1e1ed1d059f3422cc3485de7a598f65043f70be021d095b?d=mp&s=160"},"body":"Hey again,\n\nthanks for the bites, Ilari. I've fixed all the formatting issues in\nthe latest batch of commits [1], and improved the error handling quite\na bit.\n\nRegarding the hashing of OIDs, it's not a random hash, it's an\nadaptation of MurmurHash [2], which is made of win -- specially when\nit comes to dispersing stuff on hash tables. You are right however\nthat SHA1 raw bytes are already random enough, and probably not worth\nthe performance hit of hashing again on top of it -- I've dropped it\nfor the time being.\n\nMore work tomorrow,\n\nCheers,\nVicent Martí\nhttp://www.bellverde.org\n\n[1]: http://github.com/tanoku/libgit2-gsoc2010/commits/master\n[2]: http://sites.google.com/site/murmurhash/\n\nOn Thu, May 27, 2010 at 8:35 PM, Ilari Liusvaara\n wrote:\n> On Thu, May 27, 2010 at 11:05:54AM -0700, Shawn O. Pearce wrote:\n>> Ilari Liusvaara wrote:\n>> > * Where algorithm in git_revpool_table__hash() is from? Since it appears to\n>> > hash binary object IDs, wouldn't just simple sum/xor over words be sufficient\n>> > (all SHA-1 output bits are very nearly independent). Or do you need to be\n>> > compatible with some other implementation (doesn't appear so, because hash\n>> > is computed differently depending on endianess)?\n>>\n>> If you need a hash value for a SHA-1, why not just cast the unsigned\n>> char* to unsigned int* and load the first int as the hash code?\n>> The output of SHA-1 is pretty evenly distributed, using the first\n>> few bytes as an int should yield a sufficient distribution throughout\n>> the hashtable.\n>\n> Yeah, With pseudorandom function[*], all ways of reducing the output to n bits are\n> at most as good as just taking first n bits. But if reducing output to [0, m),\n> the best way (distribution-wise, not speed-wise) is to take remainder of the whole\n> value divided by m...\n>\n> [*] SHA-1 is not pseudorandom function, but for virtually all practical purposes\n> it is.\n>\n> -Ilari\n>\n"},{"id":"142835","messageId":"7vvda1cm42.fsf@alter.siamese.dyndns.org","threadId":"23924","inReplyTo":"AANLkTilE7UI3zg180U9GCB6DsByu3B9pwlG6xIyR8uiG@mail.gmail.com","subject":"Re: Libgit2 on the Summer of Code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-06-02T18:42:21Z","receivedAt":"2010-06-02T18:42:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alex Riesen writes:\n\n> On Thu, May 27, 2010 at 20:05, Shawn O. Pearce wrote:\n>> Ilari Liusvaara wrote:\n>>> * Where algorithm in git_revpool_table__hash() is from? Since it appears to\n>>> hash binary object IDs, wouldn't just simple sum/xor over words be sufficient\n>>> (all SHA-1 output bits are very nearly independent). Or do you need to be\n>>> compatible with some other implementation (doesn't appear so, because hash\n>>> is computed differently depending on endianess)?\n>>\n>> If you need a hash value for a SHA-1, why not just cast the unsigned\n>> char* to unsigned int* and load the first int as the hash code?\n>> The output of SHA-1 is pretty evenly distributed, using the first\n>> few bytes as an int should yield a sufficient distribution throughout\n>> the hashtable.\n>\n> Just make sure the SHA1 data are properly aligned for your platform\n\nAlso I'd prefer to see the code watch out for reproducibility across\nplatforms with different endianness and integer size.\n"}]}