Adding multiple stub files is O(n**2) in fine-grained incremental mode

Open
#4,453 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
38/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
python
Domain
performance, tooling

Research direction

Start by tracing the fine-grained incremental update path for adding multiple stub files, focusing on where all remaining new files are parsed for each processed file. Reproduce or profile an update with several new files, then verify that each file is parsed only once and that the update no longer performs quadratic parsing.

Written by the indexing model from the issue text.

Description

performance priority-2-low topic-fine-grained-incremental

When adding multiple files in a single fine-grained incremental update, we process each new file separately. As we parse all remaining new files for each processed file, this is very slow -- we perform parse O(n**2) times when adding n files.

A potential fix would be to cache the parsed files so that all files are processed only once when we process the first file.

Dominant language
Python
Stars
20.6k
Forks
3.3k
Avg merge
1d 18h
Merged PRs (30d)
54

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/mypy

All issues in python/mypy

Similar issues

More Python issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.