Main thread contributes poorly to parallel tasks in v8 |
||
Issue descriptionThe way initial task index assignment is computed for workers overflows the array, which results in many tasks having the same assignment (e.g. the last workers can get assigned to index 0,1,2 which means that by the time to main thread gets going on index 0, it's merely failing compare-and-swap and contending with other workers already ahead of it). This has the effect of the main thread poorly contributing to parallel work (GC): https://docs.google.com/document/d/1bdlWAWeP3j2yo2DYfeok6URqFCrt57yx-nucGMybGGQ/edit#heading=h.kfnmzwdqichh This is the logic: const size_t num_tasks = tasks_.size(); const size_t num_items = items_.size(); const size_t items_per_task = (num_items + num_tasks - 1) / num_tasks; for (size_t i = 0; i < num_tasks; i++, start_index += items_per_task) { if (start_index >= num_items) { start_index -= num_items; } .... } Example input: 33 items 8 tasks items_per_task = (33+8-1)/8 = 5 0 5 15 20 25 30 35 => 2 (this worker will steal most of the main thread's work -- and add contention) 7 (this worker fights with the 2nd one) Better distribution (proposal): items_per_task = 33/8 = 4 items_remainder = 33%8 = 1 0 5 (give an extra task to previous worker) 9 (no more remainder, take next 4) 13 17 21 25 29
,
Jan 30 2018
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/76195d9e08ac1f2df28883bb048da3243bd171d5 commit 76195d9e08ac1f2df28883bb048da3243bd171d5 Author: Gabriel Charette <gab@chromium.org> Date: Tue Jan 30 11:58:24 2018 Smoother distribution of worker assignment in parallel task array. This is a merge of https://chromium-review.googlesource.com/c/v8/v8/+/888704 and https://chromium-review.googlesource.com/c/v8/v8/+/887084 Which implements the fix in CL 887084 correctly in a world where there can be more tasks_ than items_ ( crbug.com/806237 ). Bug: chromium:805932 Change-Id: I05401be4fdce442644a8973281a9d88bd959b271 Reviewed-on: https://chromium-review.googlesource.com/892883 Commit-Queue: Gabriel Charette <gab@chromium.org> Reviewed-by: Michael Lippautz <mlippautz@chromium.org> Cr-Commit-Position: refs/heads/master@{#50956} [modify] https://crrev.com/76195d9e08ac1f2df28883bb048da3243bd171d5/src/heap/item-parallel-job.h [modify] https://crrev.com/76195d9e08ac1f2df28883bb048da3243bd171d5/test/unittests/heap/item-parallel-job-unittest.cc
,
Jan 30 2018
,
Jan 30 2018
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/396e7bc80182927046f6db841df4bf7a64a78af5 commit 396e7bc80182927046f6db841df4bf7a64a78af5 Author: Gabriel Charette <gab@chromium.org> Date: Tue Jan 30 16:33:36 2018 Revert "Smoother distribution of worker assignment in parallel task array." This reverts commit 76195d9e08ac1f2df28883bb048da3243bd171d5. Reason for revert: New parallel tests timeout on the waterfall (I think because it's configured to use less worker threads and TaskProcessingOneItem is currently designed to steal a worker but only process one item...). Original change's description: > Smoother distribution of worker assignment in parallel task array. > > This is a merge of https://chromium-review.googlesource.com/c/v8/v8/+/888704 > and https://chromium-review.googlesource.com/c/v8/v8/+/887084 > > Which implements the fix in CL 887084 correctly in a world where > there can be more tasks_ than items_ ( crbug.com/806237 ). > > Bug: chromium:805932 > Change-Id: I05401be4fdce442644a8973281a9d88bd959b271 > Reviewed-on: https://chromium-review.googlesource.com/892883 > Commit-Queue: Gabriel Charette <gab@chromium.org> > Reviewed-by: Michael Lippautz <mlippautz@chromium.org> > Cr-Commit-Position: refs/heads/master@{#50956} TBR=gab@chromium.org,hpayer@chromium.org,mlippautz@chromium.org Change-Id: Icf52eb3afeb9467557c1e0db6922d590466943f0 No-Presubmit: true No-Tree-Checks: true No-Try: true Bug: chromium:805932 Reviewed-on: https://chromium-review.googlesource.com/893462 Reviewed-by: Hannes Payer <hpayer@chromium.org> Commit-Queue: Gabriel Charette <gab@chromium.org> Cr-Commit-Position: refs/heads/master@{#50965} [modify] https://crrev.com/396e7bc80182927046f6db841df4bf7a64a78af5/src/heap/item-parallel-job.h [modify] https://crrev.com/396e7bc80182927046f6db841df4bf7a64a78af5/test/unittests/heap/item-parallel-job-unittest.cc
,
Jan 30 2018
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/de49b57404a9e7f264d318f09ae0854d57afc15e commit de49b57404a9e7f264d318f09ae0854d57afc15e Author: Gabriel Charette <gab@chromium.org> Date: Tue Jan 30 20:03:53 2018 Reland "Smoother distribution of worker assignment in parallel task array." This is a reland of 76195d9e08ac1f2df28883bb048da3243bd171d5. It was reverted because the new parallel tasks (with higher number of workers) hang on client.v8.ports bots. Since each test task steals the worker thread it's assigned but only processes one item before waiting for completion by others: I think the problem is that there aren't enough workers in client.v8.ports' config. There aren't any try bots for this config... reduce the tests to use 4 tasks and hope for the best (i.e. a 4 core machine that uses "num cores")... Original change's description: > Smoother distribution of worker assignment in parallel task array. > > This is a merge of https://chromium-review.googlesource.com/c/v8/v8/+/888704 > and https://chromium-review.googlesource.com/c/v8/v8/+/887084 > > Which implements the fix in CL 887084 correctly in a world where > there can be more tasks_ than items_ ( crbug.com/806237 ). > > Bug: chromium:805932 > Change-Id: I05401be4fdce442644a8973281a9d88bd959b271 > Reviewed-on: https://chromium-review.googlesource.com/892883 > Commit-Queue: Gabriel Charette <gab@chromium.org> > Reviewed-by: Michael Lippautz <mlippautz@chromium.org> > Cr-Commit-Position: refs/heads/master@{#50956} Reverted-on: https://chromium-review.googlesource.com/893462 Bug: chromium:805932 Change-Id: I4d0bda3b9f52e9160e613a8f34a95e48b814bb9e Reviewed-on: https://chromium-review.googlesource.com/893362 Reviewed-by: Hannes Payer <hpayer@chromium.org> Commit-Queue: Gabriel Charette <gab@chromium.org> Cr-Commit-Position: refs/heads/master@{#50967} [modify] https://crrev.com/de49b57404a9e7f264d318f09ae0854d57afc15e/src/heap/item-parallel-job.h [modify] https://crrev.com/de49b57404a9e7f264d318f09ae0854d57afc15e/test/unittests/heap/item-parallel-job-unittest.cc
,
Jan 31 2018
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/16e3f6362d872b455307102f68bd9536ce165e8c commit 16e3f6362d872b455307102f68bd9536ce165e8c Author: Michael Achenbach <machenbach@chromium.org> Date: Wed Jan 31 12:05:06 2018 [test] Skip tests that timeout on chromebooks TBR=gab@chromium.org NOTRY=true Bug: chromium:805932 Change-Id: I76e5acb5f2e749f7240abb0cb0596fdf8b72badf Reviewed-on: https://chromium-review.googlesource.com/895602 Commit-Queue: Michael Achenbach <machenbach@chromium.org> Reviewed-by: Michael Achenbach <machenbach@chromium.org> Cr-Commit-Position: refs/heads/master@{#50988} [modify] https://crrev.com/16e3f6362d872b455307102f68bd9536ce165e8c/test/unittests/unittests.status
,
Feb 1 2018
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/18c194237125976885926d59ed1337b815debb46 commit 18c194237125976885926d59ed1337b815debb46 Author: Gabriel Charette <gab@chromium.org> Date: Thu Feb 01 09:09:29 2018 Do not block in non-main thread tasks in ItemParallelJobTests. Otherwise bots with a low number of cores will hang trying to schedule a mere 4 tasks. This change allowing scheduling of an arbitrary number of test tasks, the count was also augmented to better stress test the system. Bug: chromium:805932 Change-Id: Ia10cd583c0675c256b4fd5d2765b50855d77a7f9 Reviewed-on: https://chromium-review.googlesource.com/895584 Commit-Queue: Gabriel Charette <gab@chromium.org> Reviewed-by: Michael Lippautz <mlippautz@chromium.org> Cr-Commit-Position: refs/heads/master@{#51019} [modify] https://crrev.com/18c194237125976885926d59ed1337b815debb46/test/unittests/heap/item-parallel-job-unittest.cc [modify] https://crrev.com/18c194237125976885926d59ed1337b815debb46/test/unittests/unittests.status
,
Feb 1 2018
📍 Pinpoint job started. https://pinpoint-dot-chromeperf.appspot.com/job/12b0f68e840000
,
Feb 1 2018
📍 Couldn't reproduce a difference. https://pinpoint-dot-chromeperf.appspot.com/job/12b0f68e840000 |
||
►
Sign in to add a comment |
||
Comment 1 by gab@chromium.org
, Jan 26 2018