{"thread":{"id":"51922","subject":"Common thread pool API in Git?","startedAt":"2019-09-26T00:33:13Z","lastAt":"2019-09-27T22:14:23Z","messageCount":3,"participants":["Jonathan Tan","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"382949","messageId":"20190926003300.195781-1-jonathantanmy@google.com","threadId":"51922","inReplyTo":null,"subject":"Common thread pool API in Git?","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-09-26T00:33:00Z","receivedAt":"2019-09-26T00:33:13Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Does anyone have ideas or plans for this? I know that (at least) \"grep\"\nand \"index-pack\" have their own implementations, and it would be great\nto just have one that all code can use.\n\nFor those who want to know, this question was motivated by a big delta\ntree occurring in [1]. index-pack does parallelize delta resolution, but\nit cannot split up trees into threads: each delta base root can go into\nits own thread, but when a delta base root is processed, all deltas on\nthat root (direct or indirect) is processed in the same thread. I took a\nlook to see if this could be parallelized, but thought that it might be\nbetter to standardize on a thread pool implementation first.\n\nSearching reveals [2], but I don't think it ever made it into Git.\n\n[1] git -c core.deltabasecachelimit=2g clone https://fuchsia.googlesource.com/third_party/vulkan-cts\n[2] https://public-inbox.org/git/1440121237-24576-2-git-send-email-sbeller@google.com/\n"},{"id":"382950","messageId":"20190926003523.197188-1-jonathantanmy@google.com","threadId":"51922","inReplyTo":"20190926003300.195781-1-jonathantanmy@google.com","subject":"Re: Common thread pool API in Git?","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-09-26T00:35:23Z","receivedAt":"2019-09-26T00:37:43Z","isPatch":false,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> For those who want to know, this question was motivated by a big delta\n> tree occurring in [1].\n\nForgot to mention: this is not an issue of the server not repacking with\na chain length limit. The tree in question is indeed not tall, but it is\nvery wide.\n"},{"id":"383073","messageId":"20190927221420.GA31237@sigill.intra.peff.net","threadId":"51922","inReplyTo":"20190926003300.195781-1-jonathantanmy@google.com","subject":"Re: Common thread pool API in Git?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-09-27T22:14:21Z","receivedAt":"2019-09-27T22:14:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 25, 2019 at 05:33:00PM -0700, Jonathan Tan wrote:\n\n> Does anyone have ideas or plans for this? I know that (at least) \"grep\"\n> and \"index-pack\" have their own implementations, and it would be great\n> to just have one that all code can use.\n> [..]\n> Searching reveals [2], but I don't think it ever made it into Git.\n\nI think that's correct. I had a recollection of this being discussed in\nthe past, but I'm pretty sure I was thinking of the patches you already\nlinked to. We didn't take it because the proposed callers actually were\nstarting sub-processes anyway, so we ended up instead with\nrun_processes_parallel():\n\n  https://public-inbox.org/git/1442012994-20374-1-git-send-email-sbeller@google.com/\n\nIn case it's useful, here's the latest version of the threaded version\nthat was posted to the list (I think):\n\n  https://public-inbox.org/git/1440724495-708-5-git-send-email-sbeller@google.com/\n\n> For those who want to know, this question was motivated by a big delta\n> tree occurring in [1]. index-pack does parallelize delta resolution, but\n> it cannot split up trees into threads: each delta base root can go into\n> its own thread, but when a delta base root is processed, all deltas on\n> that root (direct or indirect) is processed in the same thread. I took a\n> look to see if this could be parallelized, but thought that it might be\n> better to standardize on a thread pool implementation first.\n\nThis seems like a reasonable thing to want to do. It does mean that\nthreads have more potential to interact with each other. E.g., two might\nuse the same base now, so we'd have to make sure we don't throw away the\nbytes of that base until both are done. As you pointed out to me\noff-list, the bases are currently placed in a cache, but I think that\ncache is currently per-thread. I guess we could \"split\" it and copy the\nnew base into a thread's cache when we give it work to do.\n\nWhile thinking about this, an unrelated optimization occurred to me\n(that I don't see us doing). Right now we put every base we resolve into\nthe cache. But if it only has one child delta, after we resolve that\ndelta, we can definitely remove the base (even if we're still resolving\ndeltas against that child). Or more generally, once we've resolved the\n_final_ child that uses that base, we no longer need it. Here's an\nillustration (where \"<-\" means \"has delta child\"):\n\n  A <- B <- C\n         <- D <- E <- F ...\n\t      <- G <- H ...\n\nWe'd visit each column in a depth-first way, looking for children of\neach base we find. Once we've resolved C and D, we don't need to care\nabout the cache of B anymore. So freeing it puts more room in the cache\nwhile processing E, F, etc.\n\nAnd likewise, we can throw away D after finishing G. The strategy might\nhelp more if we did a breadth-first traversal, but then you have the\nopposite problem (instead of a deep tree busting your cache, a wide one\nwould).\n\nAnyway, that's all pretty far off your original point. But it might be\nworth thinking about it you have to touch this part of the code as part\nof your threading work.\n\n-Peff\n"}]}