š sphinx-needs: NeedItem.add_backlink deduplicates in O(nĀ²), 27.6 s of a 38.9 s build at 2 000 needs with one links rule
Maintainers usually reply within 1 day
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 66/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Active
- Tech stack
- python
- Domain
- backend, performance
Research direction
Find NeedItem.add_backlink and inspect its duplicate check, then trace how sort_links preserves ordering. Add a timing-free unit test that counts membership checks as back links are added, or use a benchmark subset in tests/benchmarks. Done means deduplication scales linearly while preserving written order where it matters.
Written by the indexing model from the issue text.
Description
Measurement
A project of 2 000 needs with one links derive rule whose filter half the needs pass (every need linking the 1 000 open ones, ~2 M links, ~2 M back links) builds in 38.9 s, of which 27.6 s is NeedItem.add_backlink: each call checks the existing back links for a duplicate before appending, so adding k back links to one need costs O(kĀ²). Measured by the builder of #2191 (cProfile on the kinds series); the same shape costs ubCode 6 s in a debug binary, of which the rule is 0.18 s.
Nothing in the rule machinery causes it: the same cost arrives with 2 M literal links, or with [[links_from_filter(ā¦)]] on every need.
Fix shape
Deduplicate with a set (or seal once after all back links are added, as sort_links already does for the ordering), keeping the written order where it matters. A pin: a timing-free unit test that add_backlink of k entries makes O(k) membership checks, or a benchmark subset entry in tests/benchmarks.
Companion: a warning for a slow or dense rule (filed separately).
- Dominant language
- Python
- Stars
- 309
- Forks
- 103
- Avg merge
- 10h 41m
- Merged PRs (30d)
- 128
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up ā it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from useblocks/sphinx-needs
-
documentation pkg: sphinx-needs
Difficulty 1/5 Under an hour Newbie friendliness 82/100
useblocks/sphinx-needs#2255 Ā·
Maintainers usually reply within 1 day
-
bug pkg: sphinx-needs
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
useblocks/sphinx-needs#2253 Ā·
Maintainers usually reply within 1 day
-
bug pkg: sphinx-needs
Difficulty 2/5 1-3 hours Newbie friendliness 66/100
useblocks/sphinx-needs#2251 Ā·
Maintainers usually reply within 1 day
-
bug pkg: sphinx-needs
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
useblocks/sphinx-needs#2249 Ā·
Maintainers usually reply within 1 day
-
documentation pkg: sphinx-test-reports
Difficulty 2/5 1-3 hours Newbie friendliness 66/100
useblocks/sphinx-needs#2247 Ā·
Maintainers usually reply within 1 day
All issues in useblocks/sphinx-needs
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
UKGovernmentBEIS/control-arena#917 Ā·
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 88/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
debpalash/VoiceStudio#2937 Ā·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
aws-samples/sample-per-model-bedrock#261 Ā·
Maintainers usually reply within 1 day