This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: multiprocessing .Condition.notify(_all) function has O(N) time complexity where N is the number of wait() calls with a timeout since the last notify(_all) call
Type: performance Stage:
Components: Library (Lib) Versions: Python 3.6, Python 3.5, Python 2.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: davin, jnoller, sbt, vilnis.termanis
Priority: normal Keywords: patch

Created on 2015-10-24 10:09 by vilnis.termanis, last changed 2022-04-11 14:58 by admin.

Files
File name Uploaded Description Edit
mp_sync_condition.patch vilnis.termanis, 2015-10-24 10:09 Patch based on in in-development branch review
condition_test.py vilnis.termanis, 2015-10-24 10:10 illustrates performance of the proposed change as well as demonstrate the issue
mp_sync_condition_with_test.patch vilnis.termanis, 2015-11-05 22:32 Patch based on in-development branch with regression test review
Messages (4)
msg253403 - (view) Author: Vilnis Termanis (vilnis.termanis) * Date: 2015-10-24 10:09
multiprocessing's Condition uses a couple of semaphores to keep track of
processes which are sleeping and have woken up whilst waiting for the
condition. These counters however are only ever decremented in the
notify(_all) functions, via a loop which results in somewhat unexpected
behaviour where said functions take longer to run than expected.

The proposed patch simplifies notify(_all) functions such that time complexity
is still O(N) but crucially N is the number of currently sleeping processes
only (rather than number of wait() calls since last notify(_all) call).

Note: This also affects Event.wait() & Event.set() in the same fashion since a
Condition is used under the hood.

I've attached mp_sync_condition.patch based on "in-development" branch as of
98840:2028aed246c0. I have run unit tests on said commit (via debug build)
using:

./python -bb -E -Wd -m test -r -v -uall\
    test_multiprocessing_fork\
    test_multiprocessing_fork\
    server test_multiprocessing_spawn

Additionally I've run condition_test.py before & after to illustrate performance
of the proposed change as well as demonstrate the issue.
msg253427 - (view) Author: Vilnis Termanis (vilnis.termanis) * Date: 2015-10-25 15:50
A few additional notes:

1) On an AMD E-450 under Ubuntu 14.04 x64 with a current in-development build, when running condition_test.py, Condition.notify_all() takes (measure using time.clock) 0.0003 with the patch and 0.3219 without it. Additionally the in-script timeit calls seem to suggest that the patch does not adversely affect Condition.wait().

2) Unit tests have also been run against test_multiprocessing_forkserver (typo in original message).

3) A scenario where this might become apparent would be to have many worker processes which have a loop along the lines of:

while not event.is_set():
  do_more_work()
  # Pause because the task is only supposed to happen every X seconds
  # or a wait is in effect due to an error. Do not want to use
  # time.sleep so loop is exited promptly rather than blindly sleeping.
  event.wait(some_amount)
other_work_or_shutdown()

If many processes call event.wait() with a timeout and the event is not set often (e.g. since it's a shutdown flag), a long-running program with many worker processes can end up having event.set() take a considerable amount of time.
msg253685 - (view) Author: Vilnis Termanis (vilnis.termanis) * Date: 2015-10-29 17:09
I realise that having type bug type of "performance" means it's less likely to be looked at than if I had marked is as "behaviour" or "resource usage" (which would not be completely unfair, I think).

Also, the patch should be applicable to 2.7 and 3.2 through to 3.5 (despite versions having been removed from the bug report).
msg254145 - (view) Author: Vilnis Termanis (vilnis.termanis) * Date: 2015-11-05 22:32
I've added a regression test for the proposed patch along the lines of the example script (i.e. fails before and passes with patch). Apologies if the test is a bit clumsy - maybe there is a more elegant way?
History
Date User Action Args
2022-04-11 14:58:23adminsetgithub: 69655
2015-11-06 03:20:20davinsetnosy: + davin

versions: + Python 2.7, Python 3.5
2015-11-05 22:32:38vilnis.termanissetfiles: + mp_sync_condition_with_test.patch

messages: + msg254145
2015-10-29 17:09:25vilnis.termanissetmessages: + msg253685
2015-10-25 16:55:10SilentGhostsetversions: - Python 2.7, Python 3.2, Python 3.3, Python 3.4, Python 3.5
2015-10-25 16:50:54SilentGhostsetnosy: + jnoller, sbt
2015-10-25 15:50:44vilnis.termanissetmessages: + msg253427
2015-10-24 10:10:49vilnis.termanissetfiles: + condition_test.py
2015-10-24 10:09:55vilnis.termaniscreate