New submission from Vilnis Termanis:
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.
----------
components: Library (Lib)
files: mp_sync_condition.patch
keywords: patch
messages: 253403
nosy: vilnis.termanis
priority: normal
severity: normal
status: open
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
versions: Python 2.7, Python 3.2, Python 3.3, Python 3.4, Python 3.5, Python 3.6
Added file: http://bugs.python.org/file40853/mp_sync_condition.patch
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue25469>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
