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

Open
#69,655 6 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Quiet
Tech stack
python
Domain
backend

Research direction

Start with the multiprocessing Condition.notify and notify_all implementation, then read the attached condition_test.py, which demonstrates the performance issue. Compare the proposed mp_sync_condition.patch and mp_sync_condition_with_test.patch, and confirm done when the regression test passes without the reported O(N) notification cost.

Written by the indexing model from the issue text.

Description

3.12 performance stdlib topic-multiprocessing
BPO 25469
Nosy @applio
Files
  • mp_sync_condition.patch: Patch based on in in-development branch
  • condition_test.py: illustrates performance of the proposed change as well as demonstrate the issue
  • mp_sync_condition_with_test.patch: Patch based on in-development branch with regression test
    		•

    Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = None
closed_at = None
created_at = <Date 2015-10-24.10:09:55.278>
labels = ['library', 'performance']
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'
updated_at = <Date 2015-11-06.03:20:20.418>
user = 'https://bugs.python.org/vilnistermanis'

    bugs.python.org fields:

    activity = <Date 2015-11-06.03:20:20.418>
actor = 'davin'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2015-10-24.10:09:55.278>
creator = 'vilnis.termanis'
dependencies = []
files = ['40853', '40854', '40958']
hgrepos = []
issue_num = 25469
keywords = ['patch']
message_count = 4.0
messages = ['253403', '253427', '253685', '254145']
nosy_count = 4.0
nosy_names = ['jnoller', 'vilnis.termanis', 'sbt', 'davin']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue25469'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6']

    Dominant language
    Python
    Stars
    77.2k
    Forks
    36k
    Avg merge
    1d 9h
    Merged PRs (30d)
    558

    Contributor guide

    Open the contributing guide

    First steps

    1. Read the whole issue, then the project's contributing guide.
    2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
    3. Fork the repository and make your change on a branch.
    4. Open a pull request that references the issue number.

    More from python/cpython

    All issues in python/cpython

    Similar issues

    More Python issues

    Get new issues in your inbox

    A short digest of beginner-friendly GitHub issues.