{"thread":{"id":"42396","subject":"run-command: output owner picking strategy","startedAt":"2016-05-20T13:11:50Z","lastAt":"2016-05-20T18:54:02Z","messageCount":5,"participants":["William Duclot","Stefan Beller","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"287082","messageId":"401208017.5792558.1463749910970.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42396","inReplyTo":"906110267.5791524.1463748828183.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"run-command: output owner picking strategy","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-20T13:11:50Z","receivedAt":"2016-05-20T13:11:50Z","isPatch":false,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"Hi,\nI stumbled upon this piece of code (run-command.c:pp_collect_finish()), picking the owner of the output amongst parallel processes (introduced by Stephan Beller in commit c553c72eed64b5f7316ce227f6d5d783eae6f2ed)\n\n/*\n * Pick next process to output live.\n * NEEDSWORK:\n * For now we pick it randomly by doing a round\n * robin. Later we may want to pick the one with\n * the most output or the longest or shortest\n * running process time.\n */\nfor (i = 0; i < n; i++)\n   if (pp->children[(pp->output_owner + i) % n].state == GIT_CP_WORKING)\n      break;\npp->output_owner = (pp->output_owner + i) % n;\n\n\nWould it be useful to improve this round-robin into something smarter (as stated by the NEEDSWORK)? It seems to be only used for submodules fetch/clone.\n\nThe options would be (as said in the comment):\n1 - pick the process with the longest running process time\n2 - pick the process with the shortest running process time\n3 - pick the process for which the output buffer is the longest\n\nBut with one of those strategies, wouldn't we lose the advantage of having the same output order as a non-parallelized version? Cf the commit message.\n\nWhat do you think ? \n"},{"id":"287108","messageId":"CAGZ79kZ1LTF4h_WVV9mMCAQCVtH667GU011LiRNtkTmi9ygUYw@mail.gmail.com","threadId":"42396","inReplyTo":"401208017.5792558.1463749910970.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"Re: run-command: output owner picking strategy","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-05-20T17:00:24Z","receivedAt":"2016-05-20T17:00:24Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, May 20, 2016 at 6:11 AM, William Duclot\n<william.duclot@ensimag.grenoble-inp.fr> wrote:\n> Hi,\n> I stumbled upon this piece of code (run-command.c:pp_collect_finish()), picking the owner\n> of the output amongst parallel processes (introduced by Stephan Beller in commit c553c72eed64b5f7316ce227f6d5d783eae6f2ed)\n>\n> /*\n>  * Pick next process to output live.\n>  * NEEDSWORK:\n>  * For now we pick it randomly by doing a round\n>  * robin. Later we may want to pick the one with\n>  * the most output or the longest or shortest\n>  * running process time.\n>  */\n> for (i = 0; i < n; i++)\n>    if (pp->children[(pp->output_owner + i) % n].state == GIT_CP_WORKING)\n>       break;\n> pp->output_owner = (pp->output_owner + i) % n;\n>\n>\n> Would it be useful to improve this round-robin into something smarter (as stated by the NEEDSWORK)? It seems to be only used for submodules fetch/clone.\n>\n> The options would be (as said in the comment):\n> 1 - pick the process with the longest running process time\n> 2 - pick the process with the shortest running process time\n> 3 - pick the process for which the output buffer is the longest\n>\n> But with one of those strategies, wouldn't we lose the advantage of having the same output order as a non-parallelized version? Cf the commit message.\n>\n> What do you think ?\n\nWhen running in parallel we already may be out of order\n(relative to serial processing). See the second example in the\ncommit message to produce a different order.\n\nConsider we scheduled tasks to be run in 3 parallel processes:\n(As we NEEDSWORK comment only addresses the ouput selection,\nlet's assume this is a fixes schedule, which we cannot alter.\nWhich is true if we only change the code you quoted. That picks\nthe process to output.)\n\n\n    process 1: |---A---||-E----------|\n\n    process 2: |-B-||-----------D----|\n\n    process 3: |-------C-------||-F-|\n\noutput order:    A, B, D, C, F, E\ntiming:        |---A---|{B}|------D----|{C,F,E}\n\nAll outputs with {braces} are instant from buffers,\nand output surrounded by |--dashes--| are live.\n\nThe output is produced by the current algorithm:\n(1) Start with process 1 (A) whose output will be live\n(2) Once A is done, flush all other done things, (B)\n(3) live output will be round robin, so process 2 (D)\n(4) Once D is done, flush all other done things (C, F, E)\n    in order of who finshed first\n\n\n(1) is uncontroversial. We have no information about tasks A,B,C,\n    so pick a random candidate. We hardcoded process 1 for now.\n\n(2) also uncontroversial IMHO. There is not much we can do different.\n\n(3) is what this NEEDSWORK comment is about. Instead of outputting D\n    we might have choosen C. (for $REASONS, e.g.: C is running longer than\n    D already, so we expect it to finish sooner, by assuming\n    any task takes the same expected time to finish. And as C\n    is expected to finish earlier than D, we may have smoother\n    output. \"Less buffered bursts\")\n\nThen the output looks like this:\n\noutput order: A B C D F E\ntiming:        |---A---|{B}|-C-||-D-|{F,E}\n(Same notation as above)\n\nThis seems to be better than the current behavior as we have more\ndifferent tasks with \"live\" output, i.e. you see stuff moving.\nI made up the data to make the point though. We would need to use\nlive data and experiment with different strategies to find a\ngood/better solution.\n\nAnother way to do output would be to not round robin but keep outputting\nprocess 1 live (different than current behavior, and not optimal IMHO)\n\noutput order: A B E C D F\ntiming:        |---A---|{B}|-----E----|{C,D,F}\n(Same notation as above)\n\nThanks,\nStefan\n"},{"id":"287122","messageId":"390486239.5813961.1463768960439.JavaMail.zimbra@ensimag.grenoble-inp.fr","threadId":"42396","inReplyTo":"CAGZ79kZ1LTF4h_WVV9mMCAQCVtH667GU011LiRNtkTmi9ygUYw@mail.gmail.com","subject":"Re: run-command: output owner picking strategy","fromName":"William Duclot","fromEmail":"william.duclot@ensimag.grenoble-inp.fr","sentAt":"2016-05-20T18:29:20Z","receivedAt":"2016-05-20T18:29:20Z","isPatch":false,"sender":{"key":"william.duclot@ensimag.grenoble-inp.fr","avatar":null},"body":"> When running in parallel we already may be out of order\n> (relative to serial processing). See the second example in the\n> commit message to produce a different order.\n\nRight, I could (should) have understood that by myself.\n \n> Consider we scheduled tasks to be run in 3 parallel processes:\n> (As we NEEDSWORK comment only addresses the ouput selection,\n> let's assume this is a fixes schedule, which we cannot alter.\n> Which is true if we only change the code you quoted. That picks\n> the process to output.)\n> \n> [...]\n \n> The output is produced by the current algorithm:\n> (1) Start with process 1 (A) whose output will be live\n> (2) Once A is done, flush all other done things, (B)\n> (3) live output will be round robin, so process 2 (D)\n> (4) Once D is done, flush all other done things (C, F, E)\n>     in order of who finshed first\n> \n> \n> (1) is uncontroversial. We have no information about tasks A,B,C,\n>     so pick a random candidate. We hardcoded process 1 for now.\n> \n> (2) also uncontroversial IMHO. There is not much we can do different.\n\nAgreed\n \n> (3) is what this NEEDSWORK comment is about. Instead of outputting D\n>     we might have choosen C. (for $REASONS, e.g.: C is running longer than\n>     D already, so we expect it to finish sooner, by assuming\n>     any task takes the same expected time to finish. And as C\n>     is expected to finish earlier than D, we may have smoother\n>     output. \"Less buffered bursts\")\n> \n> [...]\n> \n> This seems to be better than the current behavior as we have more\n> different tasks with \"live\" output, i.e. you see stuff moving.\n> I made up the data to make the point though. We would need to use\n> live data and experiment with different strategies to find a\n> good/better solution.\n\nWe should probably settle on what is the behavior we want to obtain, \nbefore trying to find a strategy to implement (or approximate) it:\n- Do we want to be as close as possible to a serial processing output? \n- Do we want to see as much live output as possible?\n\nI do not think that being close to serial processing is a relevant \nbehavior: we applied an arbitrary order to tasks when naming them for\nexplanations (A, B, C...), but the tasks aren't really sorted in any\nway (and that's why the parallelization is relevant).Neither the user\nnor git have any interest in getting these ouputs in a specific order.\n\nTherefore, a \"as much live output as possible\" behavior would be more\nsensible. But I wonder: is there a worthy benefit in optimizing the\noutput owner strategy? I'm not used to working with submodules, but I\ndon't think that having a great number of submodules is a common thing.\nBasically: we could solve a problem, but is there a problem?\nI'm not trying to bury this NEEDSWORK, I'd be happy to look into it if\nneed be!\n"},{"id":"287124","messageId":"CAGZ79kbTa-E3QTgGhzEPKnEHiOMq_On6h6RC8jrrQaot1YE94g@mail.gmail.com","threadId":"42396","inReplyTo":"390486239.5813961.1463768960439.JavaMail.zimbra@ensimag.grenoble-inp.fr","subject":"Re: run-command: output owner picking strategy","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2016-05-20T18:39:48Z","receivedAt":"2016-05-20T18:39:48Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, May 20, 2016 at 11:29 AM, William Duclot\n<william.duclot@ensimag.grenoble-inp.fr> wrote:\n>> When running in parallel we already may be out of order\n>> (relative to serial processing). See the second example in the\n>> commit message to produce a different order.\n>\n> Right, I could (should) have understood that by myself.\n>\n>> Consider we scheduled tasks to be run in 3 parallel processes:\n>> (As we NEEDSWORK comment only addresses the ouput selection,\n>> let's assume this is a fixes schedule, which we cannot alter.\n>> Which is true if we only change the code you quoted. That picks\n>> the process to output.)\n>>\n>> [...]\n>\n>> The output is produced by the current algorithm:\n>> (1) Start with process 1 (A) whose output will be live\n>> (2) Once A is done, flush all other done things, (B)\n>> (3) live output will be round robin, so process 2 (D)\n>> (4) Once D is done, flush all other done things (C, F, E)\n>>     in order of who finshed first\n>>\n>>\n>> (1) is uncontroversial. We have no information about tasks A,B,C,\n>>     so pick a random candidate. We hardcoded process 1 for now.\n>>\n>> (2) also uncontroversial IMHO. There is not much we can do different.\n>\n> Agreed\n>\n>> (3) is what this NEEDSWORK comment is about. Instead of outputting D\n>>     we might have choosen C. (for $REASONS, e.g.: C is running longer than\n>>     D already, so we expect it to finish sooner, by assuming\n>>     any task takes the same expected time to finish. And as C\n>>     is expected to finish earlier than D, we may have smoother\n>>     output. \"Less buffered bursts\")\n>>\n>> [...]\n>>\n>> This seems to be better than the current behavior as we have more\n>> different tasks with \"live\" output, i.e. you see stuff moving.\n>> I made up the data to make the point though. We would need to use\n>> live data and experiment with different strategies to find a\n>> good/better solution.\n>\n> We should probably settle on what is the behavior we want to obtain,\n> before trying to find a strategy to implement (or approximate) it:\n> - Do we want to be as close as possible to a serial processing output?\n> - Do we want to see as much live output as possible?\n>\n> I do not think that being close to serial processing is a relevant\n> behavior: we applied an arbitrary order to tasks when naming them for\n> explanations (A, B, C...), but the tasks aren't really sorted in any\n> way (and that's why the parallelization is relevant).Neither the user\n> nor git have any interest in getting these ouputs in a specific order.\n\nIIRC In serial processing the output was according to the sort order\nwithin the tree. I agree that this sorting property is of no value to the user.\n\n>\n> Therefore, a \"as much live output as possible\" behavior would be more\n> sensible.\n\nI choose \"as much live output\" as an approximation of \"least amount buffered\nover time, i.e. if you were to integrate the buffer size over time\nthat should be\nminimized. (c.f. users waiting for output: http://imgur.com/gallery/lhjhbB9)\nI am not sure if that is ultimate thing to optimize for though.\n\n> But I wonder: is there a worthy benefit in optimizing the\n> output owner strategy?\n\nEventually there are more users than just submodules for this\nparallel processing machinery, I would hope. They would also benefit\nof a good fundament?\n\n> I'm not used to working with submodules, but I\n> don't think that having a great number of submodules is a common thing.\n\n(Not yet, because of the chicken and egg problem: submodule UI is not\nas polished because very few people use it. And few people use it because\nof confusing UI. ;)\n\nAt his GitMerge2016 talk, Lars Schneider proposed a guideline to\nnot use more than 25 submodules as it \"doesn't scale\" IIRC.\nAnd that resentment seems to be all over the place.\n\n> Basically: we could solve a problem, but is there a problem?\n> I'm not trying to bury this NEEDSWORK, I'd be happy to look into it if\n> need be!\n\nWell Git as a community doesn't ask you to solve any problems. ;)\nSo if you have fun thinking about scheduling problems (and as you do\nit as part of a university project, if Matthieu is happy about this problem\nalso), go for it :)\n\nIf you find another more \"interesting\" problem (either as defined by\nyou personal interests or by the possible impact or by possible grading),\nchoose that?\n\nThanks,\nStefan\n"},{"id":"287125","messageId":"xmqqwpmod0hh.fsf@gitster.mtv.corp.google.com","threadId":"42396","inReplyTo":"CAGZ79kbTa-E3QTgGhzEPKnEHiOMq_On6h6RC8jrrQaot1YE94g@mail.gmail.com","subject":"Re: run-command: output owner picking strategy","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-05-20T18:54:02Z","receivedAt":"2016-05-20T18:54:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller <sbeller@google.com> writes:\n\n> I choose \"as much live output\" as an approximation of \"least amount buffered\n> over time, i.e. if you were to integrate the buffer size over time\n> that should be\n> minimized. (c.f. users waiting for output: http://imgur.com/gallery/lhjhbB9)\n> I am not sure if that is ultimate thing to optimize for though.\n\nIt might be interesting to optimize to minimize the time the user\nneeds to stare an inactive screen, i.e. make sure there always is\nsomething flowing.  That may involve throttling the output from a\nbuffer if that is the only buffer with any output, the foreground\nthing hasn't made any output yet, and expected to stay silent for a\nwhile, etc.\n"}]}