perf: optimize nested foldl in Glushkov/Matcher.lean step/initialStep (O(n²) → O(n log n))
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Stale
- Domain
- compilers, performance
Research direction
Start in Lck/Regex/Glushkov/Matcher.lean, focusing on step and initialStep at the cited lines and tracing their nested foldl operations. Compare candidate state-set data structures against the current behavior; done means preserving matching results while reducing the per-step complexity from O(n²) toward O(n log n).
Written by the indexing model from the issue text.
Description
Problem
The step and initialStep functions in Lck/Regex/Glushkov/Matcher.lean (lines 45-55, 65-75) use nested foldl operations that produce O(n²) complexity for large NFAs.
Impact
For a pattern with n positions, each step scans all active states and for each computes a set union — resulting in O(n²) per character of input.
Suggested Fix
Consider using a more efficient data structure (e.g., a bitset or sorted set with efficient union) to bring the per-step cost to O(n log n).
References
Raised in AI code review.
- Dominant language
- Lean
- Stars
- 2
- Forks
- 1
- PR merge metrics
- No merged PRs in 30d
Contributor guide
No contributing guide indexed for this repository
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 lambdaclass/lambda_compiler_kit
-
Difficulty 1/5 Under an hour Newbie friendliness 72/100
-
Difficulty 1/5 Under an hour Newbie friendliness 68/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
enhancement
Difficulty 4/5 3-5 days Newbie friendliness 48/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 50/100
All issues in lambdaclass/lambda_compiler_kit
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
-
internal.h中，漏掉了1个定义。 Open
Difficulty 1/5 Under an hour Newbie friendliness 95/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
oxc-project/oxc#26944 ·