{"thread":{"id":"48972","subject":"[PATCH] pack-objects: document about thread synchronization","startedAt":"2018-07-29T15:36:12Z","lastAt":"2018-08-04T07:04:14Z","messageCount":6,"participants":["Nguyễn Thái Ngọc Duy","Duy Nguyen","Jeff King","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"353825","messageId":"20180729153605.27298-1-pclouds@gmail.com","threadId":"48972","inReplyTo":null,"subject":"[PATCH] pack-objects: document about thread synchronization","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2018-07-29T15:36:05Z","receivedAt":"2018-07-29T15:36:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"These extra comments should be make it easier to understand how to use\nlocks in pack-objects delta search code. For reference, see\n\n8ecce684a3 (basic threaded delta search - 2007-09-06)\n384b32c09b (pack-objects: fix threaded load balancing - 2007-12-08)\n50f22ada52 (threaded pack-objects: Use condition... - 2007-12-16)\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n builtin/pack-objects.c | 19 +++++++++++++++++++\n 1 file changed, 19 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ebc8cefb53..6270f74c0b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1852,18 +1852,30 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,\n \n #ifndef NO_PTHREADS\n \n+/* Protect access to object database */\n static pthread_mutex_t read_mutex;\n #define read_lock()\t\tpthread_mutex_lock(&read_mutex)\n #define read_unlock()\t\tpthread_mutex_unlock(&read_mutex)\n \n+/* Protect delta_cache_size */\n static pthread_mutex_t cache_mutex;\n #define cache_lock()\t\tpthread_mutex_lock(&cache_mutex)\n #define cache_unlock()\t\tpthread_mutex_unlock(&cache_mutex)\n \n+/*\n+ * Protect object list partitioning (e.g. struct thread_param) and\n+ * progress_state\n+ */\n static pthread_mutex_t progress_mutex;\n #define progress_lock()\t\tpthread_mutex_lock(&progress_mutex)\n #define progress_unlock()\tpthread_mutex_unlock(&progress_mutex)\n \n+/*\n+ * Access to struct object_entry is unprotected since each thread owns\n+ * a portion of the main object list. Just don't access object entries\n+ * ahead in the list because they can be stolen and would need\n+ * progress_mutex for protection.\n+ */\n #else\n \n #define read_lock()\t\t(void)0\n@@ -2245,12 +2257,19 @@ static void try_to_free_from_threads(size_t size)\n static try_to_free_t old_try_to_free_routine;\n \n /*\n+ * The main object list is split into smaller lists, each is handed to\n+ * one worker.\n+ *\n * The main thread waits on the condition that (at least) one of the workers\n * has stopped working (which is indicated in the .working member of\n * struct thread_params).\n+ *\n * When a work thread has completed its work, it sets .working to 0 and\n * signals the main thread and waits on the condition that .data_ready\n * becomes 1.\n+ *\n+ * The main thread steals half of the work from the worker that has\n+ * most work left to hand it to the idle worker.\n */\n \n struct thread_params {\n-- \n2.18.0.656.gda699b98b3\n\n"},{"id":"353826","messageId":"CACsJy8AKHo4g5607GdiuLVBy1746gEEFbsYjB2RLwvQvE24Sgg@mail.gmail.com","threadId":"48972","inReplyTo":"20180729153605.27298-1-pclouds@gmail.com","subject":"Re: [PATCH] pack-objects: document about thread synchronization","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-07-29T15:46:17Z","receivedAt":"2018-07-29T15:51:44Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"tOn Sun, Jul 29, 2018 at 5:36 PM Nguyễn Thái Ngọc Duy wrote:\n>\n> These extra comments should be make it easier to understand how to use\n> locks in pack-objects delta search code. For reference, see\n\nSide note. I wonder if we could take progress_lock() less often in\nfind_deltas() to reduce contention. Right now we take the lock every\ntime we check out one object_entry but we could pull like 16 items out\nof the list per lock. I don't know how much actual contention on this\nlock though so maybe not worth doing.\n-- \nDuy\n"},{"id":"354311","messageId":"20180802193518.GA29084@sigill.intra.peff.net","threadId":"48972","inReplyTo":"20180729153605.27298-1-pclouds@gmail.com","subject":"Re: [PATCH] pack-objects: document about thread synchronization","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-02T19:35:18Z","receivedAt":"2018-08-02T19:35:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 29, 2018 at 05:36:05PM +0200, Nguyễn Thái Ngọc Duy wrote:\n\n> These extra comments should be make it easier to understand how to use\n> locks in pack-objects delta search code. For reference, see\n> \n> 8ecce684a3 (basic threaded delta search - 2007-09-06)\n> 384b32c09b (pack-objects: fix threaded load balancing - 2007-12-08)\n> 50f22ada52 (threaded pack-objects: Use condition... - 2007-12-16)\n\nThanks, I think this is an improvement.\n\n-Peff\n"},{"id":"354312","messageId":"20180802193912.GB29084@sigill.intra.peff.net","threadId":"48972","inReplyTo":"CACsJy8AKHo4g5607GdiuLVBy1746gEEFbsYjB2RLwvQvE24Sgg@mail.gmail.com","subject":"Re: [PATCH] pack-objects: document about thread synchronization","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-02T19:39:13Z","receivedAt":"2018-08-02T19:39:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 29, 2018 at 05:46:17PM +0200, Duy Nguyen wrote:\n\n> tOn Sun, Jul 29, 2018 at 5:36 PM Nguyễn Thái Ngọc Duy wrote:\n> >\n> > These extra comments should be make it easier to understand how to use\n> > locks in pack-objects delta search code. For reference, see\n> \n> Side note. I wonder if we could take progress_lock() less often in\n> find_deltas() to reduce contention. Right now we take the lock every\n> time we check out one object_entry but we could pull like 16 items out\n> of the list per lock. I don't know how much actual contention on this\n> lock though so maybe not worth doing.\n\nI doubt it really matters that much, since we hold it for such a small\namount of time (basically just a few pointer/integer tweaks). Compared\nto the heavy lifting of actually loading objects, you're not likely to\nsee a huge amount of contention, since at any given moment most threads\nwill be doing that work (or actually computing deltas).\n\nOf course I could be wrong. If you hit a point where many threads are\nskipping work (e.g., because they are considering deltas from objects in\nthe same pack, and skip forward without actually doing any work), then\nthey'd be ripping through the find_deltas() loop pretty quickly.\n\nOTOH, in cases like that (and the ultimate case would just be running\n\"git repack -ad\" twice in a row), the compression phase seems to go\nquite quickly, implying we're not spending a lot of time there.\n\n-Peff\n"},{"id":"354479","messageId":"CACsJy8DRQqTTV_vqxxV5dG_+UnONWNit76VMqb0=MdXsvH+2-Q@mail.gmail.com","threadId":"48972","inReplyTo":"20180802193912.GB29084@sigill.intra.peff.net","subject":"Re: [PATCH] pack-objects: document about thread synchronization","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-08-04T05:56:09Z","receivedAt":"2018-08-04T05:56:38Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Aug 2, 2018 at 9:39 PM Jeff King wrote:\n>\n> On Sun, Jul 29, 2018 at 05:46:17PM +0200, Duy Nguyen wrote:\n>\n> > tOn Sun, Jul 29, 2018 at 5:36 PM Nguyễn Thái Ngọc Duy wrote:\n> > >\n> > > These extra comments should be make it easier to understand how to use\n> > > locks in pack-objects delta search code. For reference, see\n> >\n> > Side note. I wonder if we could take progress_lock() less often in\n> > find_deltas() to reduce contention. Right now we take the lock every\n> > time we check out one object_entry but we could pull like 16 items out\n> > of the list per lock. I don't know how much actual contention on this\n> > lock though so maybe not worth doing.\n>\n> I doubt it really matters that much, since we hold it for such a small\n> amount of time (basically just a few pointer/integer tweaks). Compared\n> to the heavy lifting of actually loading objects, you're not likely to\n> see a huge amount of contention, since at any given moment most threads\n> will be doing that work (or actually computing deltas).\n\nThat was also my assumption when I added the lock to that\noe_get_delta_size() but it seemed to slow lots-of-core system\nsignificantly. My theory is when we do small deltas, turnaround time\ncould be very quick so if you have lots of threads we'll end up racing\nto hold the lock.\n\nWhat I missed here though, is that we do try_delta() on the whole\nwindow in a thread before we would need progress_lock again, so it's a\nlot more work than a single try_delta() and likely less contention.\n\n>\n> Of course I could be wrong. If you hit a point where many threads are\n> skipping work (e.g., because they are considering deltas from objects in\n> the same pack, and skip forward without actually doing any work), then\n> they'd be ripping through the find_deltas() loop pretty quickly.\n>\n> OTOH, in cases like that (and the ultimate case would just be running\n> \"git repack -ad\" twice in a row), the compression phase seems to go\n> quite quickly, implying we're not spending a lot of time there.\n>\n> -Peff\n-- \nDuy\n"},{"id":"354484","messageId":"20180804070410.GD55869@aiede.svl.corp.google.com","threadId":"48972","inReplyTo":"20180802193518.GA29084@sigill.intra.peff.net","subject":"Re: [PATCH] pack-objects: document about thread synchronization","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2018-08-04T07:04:10Z","receivedAt":"2018-08-04T07:04:14Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jeff King wrote:\n> On Sun, Jul 29, 2018 at 05:36:05PM +0200, Nguyễn Thái Ngọc Duy wrote:\n\n>> These extra comments should be make it easier to understand how to use\n>> locks in pack-objects delta search code. For reference, see\n>>\n>> 8ecce684a3 (basic threaded delta search - 2007-09-06)\n>> 384b32c09b (pack-objects: fix threaded load balancing - 2007-12-08)\n>> 50f22ada52 (threaded pack-objects: Use condition... - 2007-12-16)\n>\n> Thanks, I think this is an improvement.\n\nYes,\nReviewed-by: Jonathan Nieder \nas well.\n\nUsually I would prefer to see comments about what lock protects some\nstate where the state is defined, but here the state is normally not\nprotected by any lock, since Git is single-threaded except in limited\nplaces (like pack-objects). So the documentation you added is in the\nright place today, even though it's an unusual place.\n\nLonger term, if we start using more multithreading in Git, we'll have\nto reconsider how to structure the locking anyway.\n\nThanks,\nJonathan\n"}]}