{"thread":{"id":"7309","subject":"Why are ref_lists sorted?","startedAt":"2007-03-19T03:38:03Z","lastAt":"2007-03-19T17:03:10Z","messageCount":7,"participants":["Julian Phillips","Junio C Hamano","Shawn O. Pearce","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37457","messageId":"Pine.LNX.4.64.0703190321370.28570@beast.quantumfyre.co.uk","threadId":"7309","inReplyTo":null,"subject":"Why are ref_lists sorted?","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-03-19T03:38:03Z","receivedAt":"2007-03-19T03:38:03Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"Having got a C implementation of fetch far enough to be able to tell me \nthat I'm up-to-date (when using git:// and not using remotes or branches \nfiles) I thought I'd compare performance with the fetch--tool based \nversion. I was a bit surprised at what I saw.\n\nHot-cache time went from ~30s to ~3s, which didn't seem too bad. However \nwhat did puzzle me was where the C version was spending it's time. Being \na work in progress it's a bit chatty in places, but there is an up-front \ndelay of just over 1s (i.e. before my first message, which is the name of \nthe remote to fetch).\n\nA bit of investigation showed this to be due to the first attempt to read \na ref causing the packed refs to be loaded. In my test repo the \npacked-refs file has over 9000 entries, but I still thought that it would \nload faster than that. It turns out that the overhead is from sorting the \nrefs when building the ref_list. If I remove the code for sorting the \nentries I lose that initial 1s delay, without appearing to break anything \nin the fetch. However I assume that it's there for a reason ...\n\nSo my questions are:\n\n1) what have I broken by removing the sort?\n2) is it worth trying to optimise the sort?\n\n-- \nJulian\n\n ---\n http://www.ananova.com/news/story/sm_806582.html?menu=news.quirkies\n SpanKY: my life would have been much improved without that\n link.\n"},{"id":"37466","messageId":"7vodmpltvb.fsf@assigned-by-dhcp.cox.net","threadId":"7309","inReplyTo":"Pine.LNX.4.64.0703190321370.28570@beast.quantumfyre.co.uk","subject":"Re: Why are ref_lists sorted?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-19T04:50:16Z","receivedAt":"2007-03-19T04:50:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Julian Phillips writes:\n\n> So my questions are:\n>\n> 1) what have I broken by removing the sort?\n\nSee do_for_each_ref(). We walk packed and loose refs in\nparallel, preferring loose ref if exists (so that after packing,\nupdating a ref does not have to remove entry from packed-refs\nfile).\n\n> 2) is it worth trying to optimise the sort?\n\nIf you have 9,000 entries, it probably is worth doing. Also you\nmight want to use an expanding array of pointers instead of\nlinked list.\n\nCurrently add_ref() is shared between packed and loose refs, and\nthe order loose refs are discovered depends on readdir() order,\nso we cannot do without sorting on that side. But I suspect\nreading them in in the order they are discovered and then\nsorting at the end just once might be a good thing to do.\n\nIf we write packed refs _after_ sorting, we should be able to\noptimize on the side that reads packed-refs even better. As you\nread one new line from the file, you make sure that it sorts\nlater than the last entry you saw, and append to the end of\nlist; if you find an unorderd entry, remember that the list is\nnot sorted, and sort at the very end after reading all the refs.\n\nOr something like that...\n"},{"id":"37467","messageId":"20070319045452.GK20658@spearce.org","threadId":"7309","inReplyTo":"Pine.LNX.4.64.0703190321370.28570@beast.quantumfyre.co.uk","subject":"Re: Why are ref_lists sorted?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-19T04:54:52Z","receivedAt":"2007-03-19T04:54:52Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Julian Phillips wrote:\n> A bit of investigation showed this to be due to the first attempt to read \n> a ref causing the packed refs to be loaded. In my test repo the \n> packed-refs file has over 9000 entries, but I still thought that it would \n> load faster than that. It turns out that the overhead is from sorting the \n> refs when building the ref_list. If I remove the code for sorting the \n> entries I lose that initial 1s delay, without appearing to break anything \n> in the fetch. However I assume that it's there for a reason ...\n> \n> So my questions are:\n> \n> 1) what have I broken by removing the sort?\n> 2) is it worth trying to optimise the sort?\n\nOh gawd, that thing is an O(n**2) insertion. Ouch.\n\nThe entire reason its sorted is just to allow us to find the\nexisting ref entry, if one exists, and replace it. This way\na loose (unpacked) ref will shadow/override its packed version.\n\nI think the other reason is to provide predictable behavior.\nBy making the list sorted, refs always appear at the same relative\nposition to other refs within that repository. This makes it easier\nto write the packed-refs file and yet keep the ordering within the\nfile predictable.\n\nI think this could probably be better done as a hash, not as a\nlinked list, and that only the packed-refs writer needs to pay\nany sort of sorting costs.\n\n-- \nShawn.\n"},{"id":"37469","messageId":"Pine.LNX.4.64.0703190520150.24247@beast.quantumfyre.co.uk","threadId":"7309","inReplyTo":"Pine.LNX.4.64.0703190321370.28570@beast.quantumfyre.co.uk","subject":"Re: Why are ref_lists sorted?","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-03-19T05:22:39Z","receivedAt":"2007-03-19T05:22:39Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Mon, 19 Mar 2007, Julian Phillips wrote:\n\n> A bit of investigation showed this to be due to the first attempt to read a \n> ref causing the packed refs to be loaded. In my test repo the packed-refs \n> file has over 9000 entries, but I still thought that it would load faster \n> than that. It turns out that the overhead is from sorting the refs when \n> building the ref_list. If I remove the code for sorting the entries I lose \n> that initial 1s delay, without appearing to break anything in the fetch. \n> However I assume that it's there for a reason ...\n>\n\nActually, it's worse than that ... I forgot about the other end. If I \npoint fetch at an upload-pack with the sorted removed the time goes down \nby another second. So that sorting accounts for 2 of the 3s ...\n\n-- \nJulian\n\n ---\nKnow thyself. If you need help, call the C.I.A.\n"},{"id":"37470","messageId":"20070319053331.GA22534@spearce.org","threadId":"7309","inReplyTo":"Pine.LNX.4.64.0703190520150.24247@beast.quantumfyre.co.uk","subject":"Re: Why are ref_lists sorted?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-19T05:33:31Z","receivedAt":"2007-03-19T05:33:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Julian Phillips wrote:\n> On Mon, 19 Mar 2007, Julian Phillips wrote:\n> \n> >A bit of investigation showed this to be due to the first attempt to read \n> >a ref causing the packed refs to be loaded. In my test repo the \n> >packed-refs file has over 9000 entries, but I still thought that it would \n> >load faster than that. It turns out that the overhead is from sorting the \n> >refs when building the ref_list. If I remove the code for sorting the \n> >entries I lose that initial 1s delay, without appearing to break anything \n> >in the fetch. However I assume that it's there for a reason ...\n\nI have to say, I'm looking at the refs.c code and I'm not seeing\nany reason why these need to be sorted. Granted, the current code\nexpects that as it walks both get_packed_refs() and get_loose_refs()\n(as Junio pointed out), but change that code to toss both into a\nsingle refs hash table, with the elements being the current contents\nof struct ref_list.\n\nWe already have the ISPACKED flag in the flags field to tell us if\nthe ref is loose or not. When inserting a ref into the hash table\nyou keep the loose version (either if its in the table, or the one\nbeing inserted).\n\n-- \nShawn.\n"},{"id":"37471","messageId":"7vd535lrgc.fsf@assigned-by-dhcp.cox.net","threadId":"7309","inReplyTo":"20070319053331.GA22534@spearce.org","subject":"Re: Why are ref_lists sorted?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-19T05:42:27Z","receivedAt":"2007-03-19T05:42:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> We already have the ISPACKED flag in the flags field to tell us if\n> the ref is loose or not. When inserting a ref into the hash table\n> you keep the loose version (either if its in the table, or the one\n> being inserted).\n\nAs long as you are careful enough not to break the unwrapped\nentries, repacking and re-reading of refs (I think these three\nare the reasons we have separate lists), I am fine with that\nchange. I also think some callers of do_for_each_refs (this\nincludes the userland that use git-for-each-ref and/or\ngit-show-ref) expect the traversal to be sorted, so I would like\nto keep that sorted output behaviour.\n\nAn additional hash to speed up look-up operation is probably a\ngood thing to have.\n"},{"id":"37523","messageId":"Pine.LNX.4.64.0703190935360.6730@woody.linux-foundation.org","threadId":"7309","inReplyTo":"Pine.LNX.4.64.0703190321370.28570@beast.quantumfyre.co.uk","subject":"Re: Why are ref_lists sorted?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-19T17:03:10Z","receivedAt":"2007-03-19T17:03:10Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Mar 2007, Julian Phillips wrote:\n> \n> So my questions are:\n> \n> 1) what have I broken by removing the sort?\n\nThe big thing is probably consistency.\n\nI *really* think we need to sort these things. Otherwise you'll see two \ntotally identical repositories giving different results to something as \nfundamental as \"git ls-remote\" just because they didn't get sorted.\n\nSo I think sorting is absolutely required, perhaps not so much because it \nis necessarily \"incorrect\" without the sorting, but because I think \nconsistency in this area is too important *not* to sort it.\n\nAnd sorting it really is simple. The fact that we use a O(n**2) list \ninsertion thing that is also probably pessimal for the case of \"already \nsorted\" input is just a \"hey, it was easy, we never actually hit it in \npractice\" issue. \n\n> 2) is it worth trying to optimise the sort?\n\nAbsolutely. It might involve changing the \"ref_list *\" thing into an array \nof ref_entries, and that will cause a lot of (fairly trivial) changes, but \nit should all be entirely internal to refs.c, so it's hopefully not \npainful, just some boring grunt-work.\n\n\t\tLinus\n"}]}