{"thread":{"id":"34381","subject":"expanding pack idx fanout table","startedAt":"2013-07-08T15:54:24Z","lastAt":"2013-07-09T04:19:13Z","messageCount":4,"participants":["Shawn Pearce","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"222840","messageId":"CAJo=hJsto1ik=GTC8c3+2_jBuUqcAPL0UWp-1uoYYMpgbLB+qg@mail.gmail.com","threadId":"34381","inReplyTo":null,"subject":"expanding pack idx fanout table","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-07-08T15:54:24Z","receivedAt":"2013-07-08T15:54:24Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Has anyone studied the impact of converting the pack idx fanout table\nfrom 256 entries to 65536 entries?\n\nBack of the envelope estimates for 3.1M objects in linux.git suggests\na 2^16 fanout table would decrease the number of binary search\niterations from ~14 to ~6. The increased table costs an extra 255 KiB\nof disk. On a 70M idx file this is noise.\n\nI'm starting to wonder if increasing the fanout table once the object\ncount is above a certain threshold is a reasonable optimization for\nlarger repositories.\n"},{"id":"222849","messageId":"7vsizpymuy.fsf@alter.siamese.dyndns.org","threadId":"34381","inReplyTo":"CAJo=hJsto1ik=GTC8c3+2_jBuUqcAPL0UWp-1uoYYMpgbLB+qg@mail.gmail.com","subject":"Re: expanding pack idx fanout table","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-07-08T17:37:09Z","receivedAt":"2013-07-08T17:37:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Has anyone studied the impact of converting the pack idx fanout table\n> from 256 entries to 65536 entries?\n>\n> Back of the envelope estimates for 3.1M objects in linux.git suggests\n> a 2^16 fanout table would decrease the number of binary search\n> iterations from ~14 to ~6. The increased table costs an extra 255 KiB\n> of disk. On a 70M idx file this is noise.\n>\n> I'm starting to wonder if increasing the fanout table once the object\n> count is above a certain threshold is a reasonable optimization for\n> larger repositories.\n\nYeah, and I do not think we have to be worried too much about\nbackward compatibility for .idx files, as they are local and can be\nregenerated if an older version cannot read it.\n\nI also wonder if we can generate a finer-grained fan-out table on\nthe fly, perhaps lazily, without changing the on-disk format ;-)\n"},{"id":"222851","messageId":"CAJo=hJu2WgVfWhBGozxgPf9QT=9TydP55-Hqjfis6bhMLEPQag@mail.gmail.com","threadId":"34381","inReplyTo":"7vsizpymuy.fsf@alter.siamese.dyndns.org","subject":"Re: expanding pack idx fanout table","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2013-07-08T17:58:28Z","receivedAt":"2013-07-08T17:58:28Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Mon, Jul 8, 2013 at 10:37 AM, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n>> Has anyone studied the impact of converting the pack idx fanout table\n>> from 256 entries to 65536 entries?\n>>\n>> Back of the envelope estimates for 3.1M objects in linux.git suggests\n>> a 2^16 fanout table would decrease the number of binary search\n>> iterations from ~14 to ~6. The increased table costs an extra 255 KiB\n>> of disk. On a 70M idx file this is noise.\n>>\n>> I'm starting to wonder if increasing the fanout table once the object\n>> count is above a certain threshold is a reasonable optimization for\n>> larger repositories.\n>\n> Yeah, and I do not think we have to be worried too much about\n> backward compatibility for .idx files, as they are local and can be\n> regenerated if an older version cannot read it.\n>\n> I also wonder if we can generate a finer-grained fan-out table on\n> the fly, perhaps lazily, without changing the on-disk format ;-)\n\nHeh. Yes. The reader at runtime could expand the 256 fanout table to a\n65536 fanout table without changing the on disk format. Unfortunately\ndoing the expansion will require O(N) time as the 2nd byte of each\nSHA-1 must be examined from every bucket. If you are going to perform\nO(N) lookups this expansion might save time as it lowers the \"log N\"\nbound of the O(N log N) algorithm for N lookups. It doesn't help\nenough when doing only N/20 lookups.\n"},{"id":"222874","messageId":"20130709041913.GB27903@sigill.intra.peff.net","threadId":"34381","inReplyTo":"CAJo=hJsto1ik=GTC8c3+2_jBuUqcAPL0UWp-1uoYYMpgbLB+qg@mail.gmail.com","subject":"Re: expanding pack idx fanout table","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-07-09T04:19:13Z","receivedAt":"2013-07-09T04:19:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 08, 2013 at 08:54:24AM -0700, Shawn O. Pearce wrote:\n\n> Has anyone studied the impact of converting the pack idx fanout table\n> from 256 entries to 65536 entries?\n> \n> Back of the envelope estimates for 3.1M objects in linux.git suggests\n> a 2^16 fanout table would decrease the number of binary search\n> iterations from ~14 to ~6. The increased table costs an extra 255 KiB\n> of disk. On a 70M idx file this is noise.\n\nNo, I hadn't considered it, but I think your analysis is correct that it\nwould decrease the lookup cost. Having run \"perf\" on git a lot of times,\nI do see find_pack_entry_one turn up as a noticeable hot spot, but\nusually not more than a few percent.\n\nWhich kind of makes sense, because of the way we cache objects in\nmemory. If you are doing something like `rev-list --objects`, you are\ngoing to do O(n) packfile lookups, but you end up doing _way_ more\nlookups in the object hash. Not just one per tree entry, but one per\ntree entry for each commit in which the entry was untouched.\n\nI tried (maybe a year or so ago) to make the object hash faster using a\nsimilar fan-out trick, but I don't remember it having any real impact\n(because we keep our hash tables relatively collision free already). I\nthink I also tried a full prefix-trie, with no luck.\n\nObviously the exact results would depend on your workload, but in\ngeneral I'd expect the object hash to take the brunt of the load for\nrepeated lookups, and for non-repeated lookups to be dominated by the\ntime to actually access the object, as opposed to saving a few hashcmps.\nThat may change as we start using the pack .idx for more clever things\nthan simply accessing the objects, though (e.g., it might make a\ndifference when coupled with my commit cache patches).\n\n-Peff\n"}]}