{"thread":{"id":"18211","subject":"JGit server performance","startedAt":"2009-03-08T03:22:14Z","lastAt":"2009-03-09T15:27:50Z","messageCount":2,"participants":["Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"107371","messageId":"20090308032214.GU16213@spearce.org","threadId":"18211","inReplyTo":null,"subject":"JGit server performance","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-03-08T03:22:14Z","receivedAt":"2009-03-08T03:22:14Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"As Gerrit Code Review provides Gitosis-like functionality, but\nthat is implemented through JGit's pure Java implementation, the\nperformance of JGit's UploadPack matters to me.\n\nJGit is about 66% slower on my hardware when cloning the linux-2.6\nrepository, compared to git-core (jgit 2m21s, git-core 1m23s).\n\nThe bottlenecks are:\n\n  ~41.2% in ObjectLoader.getCachedBytes()\n\n    This is the tree objects being parsed out of the pack file.\n    The problem here (I believe) is we have horrible locality\n    when reading.  The delta base for a tree isn't in memory most\n    of the time, because its been evicted by other trees accessed\n    since the last time that tree was touched.\n\n    Conceptually this makes some sense, as ObjectWalk does a depth\n    first traversal through the tree of each commit, in most-recent\n    to least-recent commit order.  On a larger project like the\n    kernel we'll touch a lot more objects between two root trees,\n    and there isn't even any guarantee that two root trees that\n    appear near each other in the commit sequence have a delta\n    base relationship.\n\n  ~20.5% in AbstractTreeIterator.getEntryObjectId()\n\n    The bulk of the time here is really down in NB.decodeInt32().\n    We spend a lot of time converting an object id in a tree data\n    stream into an AnyObjectId (really a reused MutableObjectId)\n    so that we can probe the ObjectIdSubclassMap to see if we have\n    seen this object before.\n\n    The sad fact is, we need all 20 bytes to be converted into the 5\n    words, because the majority of the time, we have actually seen\n    the object before, and it exists in our hash table.  The only\n    way to know is to convert and compare all 5 words.  Any attempt\n    to lazily convert the 5 words would just make it slower.\n\n... and it falls off from there.\n\nI'm at a loss on how to improve the performance.  I don't think that\nwe can do anything about the 20% in getEntryObjectId() due to the\nway our data structures are organized around the 5-word ObjectId,\nand not a byte[].  That 20% is a penalty git-core doesn't have to\npay, and is most certainly one reason why JGit is so much slower.\n\nThe only thing that may work is to modify ObjectWalk to try and\ndeduce some delta-chain locality from the pack.  Buffer up objects\nthat it needs to parse in a queue, rank them by the delta base\nthey would need to use, and then try to unfold the base first,\nand then the children.\n\nThat is, do something like what IndexPack does, where we try to\nunpack each object exactly once, and recursively process the delta\nchain children after unpacking the parent.\n\nWe _might_ get better locality if we can queue up all root trees,\nprocess all of them, then process the first level children, etc,\nso go breadth first.\n\nBut that seems like a lot of code, and it probably wrecks the simple\nrecency ordering produced natively by ObjectWalk.  :-\\\n\n-- \nShawn.\n"},{"id":"107464","messageId":"20090309152750.GD11989@spearce.org","threadId":"18211","inReplyTo":"d411cc4a0903090801w7748d26pb821a7bfb3db660@mail.gmail.com","subject":"Re: JGit server performance","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-03-09T15:27:50Z","receivedAt":"2009-03-09T15:27:50Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"[+git]\n\nScott Chacon <schacon@gmail.com> wrote:\n> On Sat, Mar 7, 2009 at 8:22 PM, Shawn O. Pearce <spearce@spearce.org> wrote:\n> > As Gerrit Code Review provides Gitosis-like functionality, but\n> > that is implemented through JGit's pure Java implementation, the\n> > performance of JGit's UploadPack matters to me.\n> >\n> > JGit is about 66% slower on my hardware when cloning the linux-2.6\n> > repository, compared to git-core (jgit 2m21s, git-core 1m23s).\n> \n> What about packfile caching?  I thought I just saw someone propose\n> this for a GSOC project - it obviously wouldn't help with making the\n> first clone faster, but since it seems that you're talking about a\n> server that is probably recomputing the same packfile bits over and\n> over, perhaps caching the final output would be a simpler way to get\n> more aggregate time savings.  I remember there were some issues with\n> client capabilities and whatnot, but would that be a useful solution\n> to speeding up overall throughput?\n\nIndeed.\n\nI think over the weekend I came to the conclusion that the only\nway I can \"fix\" this is to implement some form of automatic caching\ninside of JGit.\n\nI came up with two ideas, but haven't tried either one yet:\n\nCache Object List:\n\n  The idea here is that JGit spends the majority of its server side\n  resources enumerating objects, doing the `git rev-list --objects\n  $wants --not $haves` computation.  Once you reach a certain point\n  on the DAG, that computation just isn't going to change much.\n\n  So, for example, if we tag a dump of the object listing for all\n  objects that are reachable from the most recently reachable\n  annotated tag, and cache that dump, we can reload it when we\n  encounter that tag again.  By restoring that dump, we can cut\n  off a huge part of the object evaluation.\n\n  Initial clones would always benefit from this dump, and we can\n  expand it to cover more of the DAG as new tags are produced.\n\n  The really recent commits still require enumeration, but this\n  is a small percentage of the total objects being processed,\n  and should go quite quickly.\n\n  We still need to select and serve ranges of existing packs,\n  based on the objects chosen for transmission.\n\nCache Packs:\n\n  As you point out above, do the GSoC project idea (but in JGit)\n  where we cache packs.\n\n  My problem with this approach is it doesn't help initial clones\n  very much once any one of the refs changes.  As soon as any\n  ref is updated in any way, that cached pack is invalid and must\n  be recomputed from scratch.\n\n  However, it probably would generalize nicely into supporting a\n  decent cache for incremental updates of clients.  In many cases\n  in a Linus/Junio single-push-a-day world, all clients would be\n  roughly asking for the same pack, and we'd get a decent return on\n  our investment by saving the thin pack to disk in some cache area.\n\n  But in a Gerrit Code Review world, its expected that the\n  branches will update hundreds of times per day, and clients\n  will be fetching off those multiple times throughout the day.\n  So the life span of any given cached pack is probably quite small.\n\n  However, I have no real proof to back this theory up with yet,\n  its just back of the envelope guessing on my part.\n\nHybrid:\n\n  I also considered some sort of hybrid approach.\n\n  E.g. create a cache pack for everything reachable from a stable\n  tag point (the object set in that pack is the same as the cached\n  object list).  When sending data to a client, we send the current\n  objects that aren't in the big cache pack, and then we tack the\n  pack onto the end of the data stream.  So we only need to \"read,\n  SHA-1, send\" through the entire length of the file (minus the 12\n  byte header, 20 byte footer).\n  \n  Really quite efficient.\n\n  My problem with this approach is you cannot duplicate an object\n  in a pack stream.  So I have to be very careful when using this\n  pack to complete a larger pack stream, as I need to avoid writing\n  any object in the front if it will appear in the pack I am tacking\n  onto the end.\n\n  That is more common that you might expect, e.g.  consider a\n  \"Documentation/SubmittingPatches\" file that hasn't been touched in\n  ages...  it would appear in the recent commit object enumeration,\n  but it also will appear in the big cache pack I want to tack on\n  the end, as it hasn't changed since the pack was created.\n\n\nRight now I am leaning towards caching the object enumeration\n(the first approach mentioned).\n\n-- \nShawn.\n"}]}