Multi-row `find`, `find_all` and `mask_matching` slow down with the needle's height; `contains` does not
Maintainers usually reply within 1 day
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 78/100
- Issue type
- Bug
- Clarity
- Clearly specified
- Activity status
- Active
- Tech stack
- rust
- Domain
- performance, testing-qa
Research direction
Start in screen.rs around for_each_multirow_match (lines 1691–1730) and trace how masked_multiline uses searchable rows. Compare the multirow search path with the joined-text path used by contains, then add a timing test shaped like #584's. Done means find stays within a small factor of contains as the needle height grows.
Written by the indexing model from the issue text.
Description
What happens. On a 1000x1000 screen where every row is a, with the needle "a\n" * k + "b" (release build):
| k | contains |
find |
|---|---|---|
| 10 | 4.9 ms | 23 ms |
| 100 | 4.8 ms | 176 ms |
| 400 | 4.4 ms | 565 ms |
A reviewer measured mask_matching at 690 ms for k = 500.
Cause. for_each_multirow_match (screen.rs:1691-1730) rebuilds searchable_row for every row it compares, for every candidate start row. Its cost grows as rows × needle rows × columns. contains searches the joined text once.
Why it matters. #584 removed the quadratic behaviour from single-row search. Multi-row needles still have it. The impact is small, since the worst case needs a needle hundreds of rows tall.
Fix. Compute each row's searchable form once per call, as Vec<(String, Vec<u16>)>, and share it with masked_multiline.
Done when find stays within a small factor of contains as k grows, with a timing test in the shape of #584's.
- Dominant language
- Rust
- Stars
- 28
- Forks
- 24
- Avg merge
- 11h 23m
- Merged PRs (30d)
- 42
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing guide
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 vyncint/termlens
-
documentation good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
Maintainers usually reply within 1 day
-
documentation good first issue
Difficulty 1/5 Under an hour Newbie friendliness 95/100
Maintainers usually reply within 1 day
-
Release notes show a broken link: `extract-changelog.sh` copies a reference but not its definitionOpenbug good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
Maintainers usually reply within 1 day
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 67/100
Maintainers usually reply within 1 day
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day
All issues in vyncint/termlens
Similar issues
-
priority middle
Difficulty 1/5 Under an hour Newbie friendliness 62/100
KATO-Hiro/AtCoderClans#12940 ·
Maintainers usually reply within 1 day
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 83/100
Maintainers usually reply within 1 day
-
o8 next debug build aborts on Glass to Dark appearance switch (nil identifier messaged before check)Openbug
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
hurttlocker/o8#5112 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 79/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 1 day